In diesem Artikel besprechen wir den Zählsortieralgorithmus. Zählsortierung ist eine Sortiertechnik, die auf den Schlüsseln zwischen bestimmten Bereichen basiert. In Codierungs- oder technischen Interviews für Softwareentwickler werden Sortieralgorithmen häufig gefragt. Daher ist es wichtig, das Thema zu diskutieren.
Diese Sortiertechnik führt keine Sortierung durch Vergleichen von Elementen durch. Es führt eine Sortierung durch, indem es Objekte zählt, die unterschiedliche Schlüsselwerte haben, wie z. B. Hashing. Anschließend werden einige arithmetische Operationen ausgeführt, um die Indexposition jedes Objekts in der Ausgabesequenz zu berechnen. Die Zählsortierung wird nicht als Allzweck-Sortieralgorithmus verwendet.
Die Zählsortierung ist wirksam, wenn der Bereich nicht größer ist als die Anzahl der zu sortierenden Objekte. Es kann verwendet werden, um die negativen Eingabewerte zu sortieren.
Sehen wir uns nun den Algorithmus zum Zählen und Sortieren an.
Algorithmus
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
Funktionsweise des Zählsortieralgorithmus
Sehen wir uns nun die Funktionsweise des Zählsortierungsalgorithmus an.
TCP-IP-Modell
Um die Funktionsweise des zählenden Sortieralgorithmus zu verstehen, nehmen wir ein unsortiertes Array. Anhand eines Beispiels lässt sich die Zählsortierung leichter verstehen.
Die Elemente des Arrays seien -
1. Finden Sie das maximale Element aus dem angegebenen Array. Lassen max sei das maximale Element.
array.sort in Java
2. Initialisieren Sie nun das Array mit der Länge max + 1 alle 0 Elemente haben. Dieses Array wird verwendet, um die Anzahl der Elemente im angegebenen Array zu speichern.
3. Jetzt müssen wir die Anzahl jedes Array-Elements an seinem entsprechenden Index im Count-Array speichern.
Die Anzahl eines Elements wird wie folgt gespeichert: Angenommen, das Array-Element „4“ erscheint zweimal, sodass die Anzahl von Element 4 2 beträgt. Daher wird 2 bei 4 gespeichertThPosition des Zählarrays. Wenn ein Element im Array nicht vorhanden ist, platzieren Sie 0, d. h. angenommen, Element „3“ ist im Array nicht vorhanden, sodass 0 unter 3 gespeichert wirdrdPosition.
Fizzbuzz Java
Speichern Sie nun die kumulative Summe von zählen Array-Elemente. Es hilft, die Elemente am richtigen Index des sortierten Arrays zu platzieren.
Ebenso ist die kumulative Anzahl des Zählarrays -
4. Suchen Sie nun den Index jedes Elements des ursprünglichen Arrays
Nachdem Sie das Element an seiner Stelle platziert haben, verringern Sie seine Anzahl um eins. Bevor Element 2 platziert wurde, betrug seine Anzahl 2, aber nachdem es an der richtigen Position platziert wurde, beträgt die neue Anzahl für Element 2 1.
Ebenso lauten die Array-Elemente nach dem Sortieren:
Jetzt ist das Array vollständig sortiert.
Websites wie bedpage
Sortierkomplexität zählen
Sehen wir uns nun die zeitliche Komplexität der Zählsortierung im besten Fall, im Durchschnittsfall und im schlechtesten Fall an. Wir werden auch die räumliche Komplexität der Zählsortierung sehen.
1. Zeitkomplexität
| Fall | Zeit | Komplexität |
|---|---|---|
| I'm besten fall | O(n + k) | |
| Durchschnittlicher Fall | O(n + k) | |
| Schlimmsten Fall | O(n + k) |
In allen oben genannten Fällen ist die zeitliche Komplexität der Zählsortierung gleich. Dies liegt daran, dass der Algorithmus durchläuft n+k unabhängig davon, wie die Elemente im Array platziert werden.
Die Zählsortierung ist besser als die vergleichsbasierten Sortiertechniken, da es bei der Zählsortierung keinen Vergleich zwischen Elementen gibt. Wenn die Ganzzahlen jedoch sehr groß sind, ist die Zählsortierung schlecht, da Arrays dieser Größe erstellt werden müssen.
2. Raumkomplexität
| Weltraumkomplexität | O(max) |
| Stabil | JA |
- Die räumliche Komplexität der Zählsortierung beträgt O(max). Je größer der Bereich der Elemente ist, desto größer ist die Raumkomplexität.
Implementierung der Zählsortierung
Sehen wir uns nun die Zählprogramme in verschiedenen Programmiersprachen an.
Programm: Schreiben Sie ein Programm zur Implementierung der Zählsortierung in der Sprache C.
#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;></=> Ausgabe
Das ist also alles über den Artikel. Ich hoffe, der Artikel ist hilfreich und informativ für Sie.
Shehzad Poonawala
Dieser Artikel beschränkte sich nicht nur auf den Algorithmus. Wir haben auch die Komplexität der Zählung, die Funktionsweise und die Implementierung in verschiedenen Programmiersprachen besprochen.