V tomto tutoriále sa dozviete, ako funguje počítanie zoradenia. Nájdete tiež pracovné príklady počítania tried v jazykoch C, C ++, Java a Python.
Počítanie zoradenia je algoritmus triedenia, ktorý triedi prvky poľa tak, že počíta počet výskytov každého jedinečného prvku v poli. Počet je uložený v pomocnom poli a triedenie sa vykonáva mapovaním počtu ako indexu pomocného poľa.
Ako funguje počítanie zoradenia?
- Zistite
maxpole (nech je to ) z daného poľa.
Dané pole - Inicializujte pole dĺžky
max+1so všetkými prvkami 0. Toto pole sa používa na ukladanie počtu prvkov v poli.
Počítať pole - Uložte počet každého prvku do ich príslušného indexu v
countpoli
Napríklad: ak je počet prvkov 3 rovný 2, potom sa 2 uloží na 3. pozíciu poľa počtu. Ak prvok „5“ nie je v poli prítomný, potom sa 0 uloží na 5. pozíciu.
Počet každého uloženého prvku - Uložte kumulatívny súčet prvkov počítacieho poľa. Pomáha pri umiestňovaní prvkov do správneho indexu zoradeného poľa.
Kumulatívny počet - Nájdite index každého prvku pôvodného poľa v poli počítania. Toto dáva kumulatívny počet. Vložte prvok do indexu vypočítaného podľa obrázka nižšie.
Počítanie druh - Po umiestnení každého prvku do správnej polohy znížte jeho počet o jeden.
Počítanie triediaceho algoritmu
counttingSort (pole, veľkosť) max <- vyhľadá najväčší prvok v poli inicializuje početné pole so všetkými nulami pre j <- 0 na veľkosť vyhľadá celkový počet každého jedinečného prvku a uloží počet na j-tom indexe do počítacieho poľa pre i <- 1 na maximum nájsť kumulatívny súčet a uložiť ho do samotného poľa count pre j <- veľkosť do 1 obnoviť prvky do poľa znížiť počet každého prvku obnoveného o 1
Príklady jazyka Python, Java a 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); )
Zložitosť
Časová zložitosť:
Existujú hlavne štyri hlavné slučky. (Najvyššiu hodnotu je možné nájsť mimo funkcie.)
| pre-slučku | čas počítania |
|---|---|
| 1 | O (max.) |
| 2 | O (veľkosť) |
| 3 | O (max.) |
| 4 | O (veľkosť) |
Zložitosť celého = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Najhoršia zložitosť prípadu:
O(n+k) - Najlepšia zložitosť prípadu:
O(n+k) - Priemerná zložitosť prípadu:
O(n+k)
Vo všetkých vyššie uvedených prípadoch je zložitosť rovnaká, pretože bez ohľadu na to, ako sú prvky umiestnené v poli, algoritmus prechádza n+kčasmi.
Medzi prvkami neexistuje žiadne porovnanie, takže je lepšia ako techniky triedenia založené na porovnaní. Je však zlé, ak sú celé čísla veľmi veľké, pretože by sa malo vytvoriť pole tejto veľkosti.
Zložitosť priestoru:
Komplexnosť počítania zoradenia je O(max). Čím väčší je rozsah prvkov, tým väčšia je priestorová zložitosť.
Počítanie aplikácií na zoradenie
Počítanie sa používa, keď:
- existujú menšie celé čísla s viacnásobným počtom.
- lineárna zložitosť je potreba.
