Mengira Algoritma Menyusun

Dalam tutorial ini, anda akan belajar bagaimana cara mengira berfungsi. Anda juga akan dapati contoh-contoh yang berfungsi untuk mengira jenis di C, C ++, Java dan Python.

Counting sort adalah algoritma penyortiran yang menyusun unsur-unsur array dengan mengira jumlah kejadian setiap elemen unik dalam array. Kiraan disimpan dalam susunan tambahan dan penyortiran dilakukan dengan memetakan kiraan sebagai indeks susunan tambahan.

Bagaimana Pengiraan Mengira Berfungsi?

  1. Ketahui elemen maksimum (biarkan max) dari larik yang diberikan. Diberi tatasusunan
  2. Memulakan susunan panjang max+1dengan semua elemen 0. Susunan ini digunakan untuk menyimpan jumlah unsur dalam larik. Kira array
  3. Simpan kiraan setiap elemen pada indeksnya masing-masing dalam countsusunan
    Contohnya: jika kiraan elemen 3 adalah 2 maka, 2 disimpan di kedudukan ke 3 susunan kiraan. Sekiranya elemen "5" tidak terdapat dalam larik, maka 0 disimpan di kedudukan ke-5. Kira setiap elemen yang disimpan
  4. Simpan jumlah kumulatif dari unsur-unsur kiraan kiraan. Ini membantu meletakkan elemen ke dalam indeks susunan yang disusun dengan betul. Kiraan kumulatif
  5. Cari indeks setiap elemen dari array asal dalam tatasusunan kiraan. Ini memberikan kiraan kumulatif. Letakkan elemen pada indeks yang dikira seperti dalam gambar di bawah. Mengira jenis
  6. Setelah meletakkan setiap elemen pada kedudukan yang betul, kurangkan kiraannya satu.

Mengira Algoritma Menyusun

 hitungSort (susunan, ukuran) maks untuk mendapatkan maksimum jumlah kumulatif dan menyimpannya dalam kiraan array itu sendiri untuk ukuran j <- turun hingga 1 pulihkan elemen ke susunan pengurangan setiap elemen yang dipulihkan sebanyak 1

Contoh Python, Java dan C / C ++

Python Java C C ++ 
 # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)
 // Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )
 // Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )

Kerumitan

Kerumitan Masa:

Terdapat terutamanya empat gelung utama. (Mencari nilai terbesar dapat dilakukan di luar fungsi.)

untuk-gelung masa mengira
1hb O (maks)
Ke-2 O (saiz)
Ke-3 O (maks)
Ke-4 O (saiz)

Kerumitan keseluruhan = O(max)+O(size)+O(max)+O(size)=O(max+size)

  • Kerumitan Kes Terburuk: O(n+k)
  • Kerumitan Kes Terbaik: O(n+k)
  • Kerumitan Kes Purata: O(n+k)

Dalam semua kes di atas, kerumitannya sama kerana tidak kira bagaimana elemen diletakkan dalam larik, algoritma melalui n+kmasa.

Tidak ada perbandingan antara elemen apa pun, jadi lebih baik daripada teknik penyortiran berdasarkan perbandingan. Tetapi, adalah buruk jika bilangan bulatnya sangat besar kerana susunan ukuran itu harus dibuat.

Kerumitan Ruang:

Kerumitan ruang Counting Sort adalah O(max). Semakin besar julat elemen, semakin besar kerumitan ruang.

Aplikasi Pengiraan Mengira

Jenis pengiraan digunakan apabila:

  • terdapat bilangan bulat yang lebih kecil dengan pelbagai kiraan.
  • kerumitan linear adalah keperluan.

Artikel menarik...