Dalam tutorial ini, Anda akan mempelajari cara kerja penghitungan urutan. Selain itu, Anda akan menemukan contoh kerja penghitungan sortir dalam C, C ++, Java dan Python.
Counting sort adalah algoritma pengurutan yang mengurutkan elemen-elemen sebuah array dengan menghitung jumlah kemunculan setiap elemen unik dalam array. Hitungan disimpan dalam array tambahan dan pengurutan dilakukan dengan memetakan jumlah sebagai indeks dari array tambahan.
Bagaimana Menghitung Urutan Bekerja?
- Temukan elemen maksimum (biarlah
max) dari larik yang diberikan.
Array yang diberikan - Inisialisasi array panjang
max+1dengan semua elemen 0. Array ini digunakan untuk menyimpan jumlah elemen dalam array.
Hitung array - Menyimpan jumlah setiap elemen pada indeksnya masing-masing dalam
countarray
Contoh: jika jumlah elemen 3 adalah 2, maka 2 disimpan di posisi ke-3 dari array hitungan. Jika elemen "5" tidak ada dalam array, maka 0 disimpan di posisi ke-5.
Hitungan setiap elemen yang disimpan - Simpan jumlah kumulatif elemen larik hitungan. Ini membantu dalam menempatkan elemen ke dalam indeks yang benar dari array yang diurutkan.
Hitungan kumulatif - Temukan indeks setiap elemen dari array asli dalam array hitungan. Ini memberikan jumlah kumulatif. Tempatkan elemen pada indeks yang dihitung seperti yang ditunjukkan pada gambar di bawah.
Menghitung jenis - Setelah menempatkan setiap elemen pada posisi yang benar, kurangi hitungannya satu.
Menghitung Algoritma Sortir
countSort (array, size) max <- temukan elemen terbesar dalam array menginisialisasi array hitungan dengan semua nol untuk j <- 0 untuk ukuran menemukan jumlah total setiap elemen unik dan menyimpan hitungan pada indeks ke j dalam array hitungan untuk i <- 1 untuk menemukan jumlah kumulatif secara maksimal dan menyimpannya dalam larik hitungan itu sendiri untuk j <- ukuran turun ke 1 mengembalikan elemen ke larik, jumlah penurunan setiap elemen dipulihkan oleh 1
Contoh Python, Java dan C / C ++
Python Java 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); )
Kompleksitas
Kompleksitas Waktu:
Terutama ada empat loop utama. (Menemukan nilai terbesar dapat dilakukan di luar fungsi.)
| for-loop | waktu penghitungan |
|---|---|
| 1st | O (maks) |
| 2nd | O (ukuran) |
| 3 | O (maks) |
| 4th | O (ukuran) |
Kompleksitas keseluruhan = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Kompleksitas Kasus Terburuk:
O(n+k) - Kompleksitas Kasus Terbaik:
O(n+k) - Kompleksitas Kasus Rata-rata:
O(n+k)
Dalam semua kasus di atas, kompleksitasnya sama karena tidak peduli bagaimana elemen ditempatkan dalam array, algoritme melewati n+kwaktu.
Tidak ada perbandingan antar elemen, jadi ini lebih baik daripada teknik penyortiran berbasis perbandingan. Namun, buruk jika bilangan bulatnya sangat besar karena harus dibuat larik sebesar itu.
Kompleksitas Ruang:
Kompleksitas ruang dari Counting Sort adalah O(max). Semakin besar rentang elemen, semakin besar kompleksitas ruang.
Menghitung Aplikasi Sortir
Jenis penghitungan digunakan ketika:
- ada bilangan bulat yang lebih kecil dengan beberapa hitungan.
- kompleksitas linier adalah kebutuhan.
