Štetje algoritma razvrščanja

V tej vadnici boste izvedeli, kako deluje štetje vrst. Prav tako boste našli delovne primere štetja v C, C ++, Java in Python.

Razvrščanje štetja je algoritem za razvrščanje, ki razvršča elemente polja s štetjem števila pojavitev vsakega unikatnega elementa v polju. Štetje je shranjeno v pomožni matriki, sortiranje pa se izvede tako, da se štetje preslika kot indeks pomožnega polja.

Kako deluje štetje razvrščanja?

Ugotovite največji element (naj bo max) iz dane matrike. Glede na matriko
Inicializirajte dolžinsko polje max+1z vsemi elementi 0. Ta matrika se uporablja za shranjevanje števila elementov v matriki. Številčna matrika
Shrani štetje vsakega elementa v ustrezni indeks v countmatriko.
Na primer: če je števec elementa 3 2, je 2 shranjen na 3. mestu matrike štetja. Če element "5" ni v matriki, je 0 shranjen na 5. mestu. Štetje vsakega shranjenega elementa
Shrani kumulativno vsoto elementov matrike štetja. Pomaga pri umestitvi elementov v pravi indeks razvrščenega polja. Kumulativno štetje
Poiščite indeks vsakega elementa izvirne matrike v matriki count. To daje skupno število. Element postavite na indeks, izračunan, kot je prikazano na spodnji sliki. Štetje
Po postavitvi vsakega elementa v njegov pravilen položaj zmanjšajte njegovo število za eno.

Štetje algoritma razvrščanja

 countingSort (matrika, velikost) max <- poišči največji element v matriki inicializira matriko count z vsemi ničlami za j <- 0, da velikost poišče skupno število vsakega unikatnega elementa in shrani štetje pri jth indeksu v matriko count za i <- 1 do maks. najti kumulativno vsoto in jo shraniti v samo matriko count za j <- velikost do 1 obnoviti elemente v matriko zmanjšati število elementov, obnovljenih za 1

Primeri Python, Java in 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); )

Kompleksnost

Časovne zapletenosti:

V glavnem so štiri glavne zanke. (Najti največjo vrednost lahko zunaj funkcije.)

za zanko	čas štetja
1.	O (največ)
2.	O (velikost)
3.	O (največ)
4.	O (velikost)

Celotna zapletenost = O(max)+O(size)+O(max)+O(size)=O(max+size)

Najslabša zapletenost primera: O(n+k)
Najboljši primer: O(n+k)
Povprečna zapletenost primera: O(n+k)

V vseh zgornjih primerih je zapletenost enaka, saj ne glede na to, kako so elementi postavljeni v matriko, gre algoritem skozi n+kčase.

Med nobenimi elementi ni primerjave, zato je boljša od tehnik razvrščanja na podlagi primerjave. Ampak, slabo je, če so cela števila zelo velika, ker je treba narediti matriko te velikosti.

Zapletenost vesolja:

Prostorska zahtevnost sortiranja štetja je O(max). Večji je nabor elementov, večja je zapletenost prostora.