U ovom ćemo članku raspravljati o algoritmu sortiranja brojanjem. Sortiranje brojanjem je tehnika sortiranja koja se temelji na ključevima između određenih raspona. U programskim ili tehničkim intervjuima za softverske inženjere često se postavljaju pitanja o algoritmima sortiranja. Dakle, važno je razgovarati o temi.
Ova tehnika sortiranja ne izvodi sortiranje usporedbom elemenata. Izvodi razvrstavanje prebrojavanjem objekata koji imaju različite ključne vrijednosti poput raspršivanja. Nakon toga izvodi neke aritmetičke operacije kako bi izračunao poziciju indeksa svakog objekta u izlaznom nizu. Sortiranje brojanjem ne koristi se kao algoritam sortiranja opće namjene.
Sortiranje brojanjem učinkovito je kada raspon nije veći od broja objekata koji se sortiraju. Može se koristiti za sortiranje negativnih ulaznih vrijednosti.
do i while petlja u Javi
Pogledajmo sada algoritam sortiranja brojanjem.
Algoritam
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
Rad algoritma sortiranja brojanjem
Sada, da vidimo kako radi algoritam sortiranja brojanjem.
Da bismo razumjeli rad algoritma sortiranja brojanjem, uzmimo nesortirani niz. Razvrstavanje brojanjem bit će lakše razumjeti na primjeru.
Neka su elementi niza -
1. Pronađite najveći element iz zadanog niza. Neka max biti maksimalni element.
2. Sada inicijalizirajte polje duljine maksimalno + 1 imajući svih 0 elemenata. Ovaj niz će se koristiti za pohranjivanje broja elemenata u danom nizu.
3. Sada moramo pohraniti broj svakog elementa niza na odgovarajući indeks u nizu brojača.
Broj elementa bit će pohranjen kao - Pretpostavimo da se element polja '4' pojavljuje dva puta, tako da je broj elementa 4 2. Dakle, 2 je pohranjen na 4thpoložaj niza brojača. Ako bilo koji element nije prisutan u nizu, stavite 0, tj. pretpostavimo da element '3' nije prisutan u nizu, pa će 0 biti pohranjen na 3rdpoložaj.
Sada pohranite kumulativni zbroj od računati elementi niza. Pomoći će postaviti elemente na točan indeks sortiranog niza.
Slično tome, kumulativni broj niza brojanja je -
4. Sada pronađite indeks svakog elementa izvornog niza
Nakon postavljanja elementa na njegovo mjesto, smanjite njegov broj za jedan. Prije postavljanja elementa 2, njegov broj je bio 2, ali nakon postavljanja na ispravnu poziciju, novi broj za element 2 je 1.
Slično, nakon sortiranja, elementi niza su -
Sada je niz potpuno sortiran.
Brojanje složenosti sortiranja
Sada, da vidimo vremensku složenost sortiranja brojanja u najboljem slučaju, prosječnom slučaju iu najgorem slučaju. Također ćemo vidjeti složenost prostora sortiranja brojanjem.
1. Vremenska složenost
| Slučaj | Vrijeme | Složenost |
|---|---|---|
| Najbolji slučaj | O(n + k) | |
| Prosječan slučaj | O(n + k) | |
| Najgori slučaj | O(n + k) |
U svim gore navedenim slučajevima, vremenska složenost sortiranja brojanja je ista. To je zato što algoritam prolazi n+k puta, bez obzira na to kako su elementi postavljeni u nizu.
Sortiranje brojanjem je bolje od tehnika sortiranja temeljenih na usporedbi jer nema usporedbe između elemenata u sortiranju brojanjem. Ali, kada su cijeli brojevi jako veliki, sortiranje brojanjem je loše jer se moraju kreirati nizovi te veličine.
2. Složenost prostora
| Složenost prostora | O (maks.) |
| Stabilan | DA |
- Prostorna složenost sortiranja brojanjem je O(max). Što je veći raspon elemenata, to je veća složenost prostora.
Implementacija sortiranja brojanjem
Pogledajmo sada programe sortiranja brojanjem u različitim programskim jezicima.
Program: Napišite program za implementaciju sortiranja brojanjem u C jeziku.
#include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting Sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> Izlaz
kako ubaciti lažnu apstraktnu klasu
Dakle, to je sve o članku. Nadamo se da će vam članak biti koristan i informativan.
Ovaj članak nije bio ograničen samo na algoritam. Također smo razgovarali o brojanju složenosti sortiranja, radu i implementaciji u različitim programskim jezicima.