logo

TechCodeview

Zählsortierung – Tutorials zu Datenstrukturen und Algorithmen

Was ist Zählsortierung?

Zählsortierung ist ein nicht vergleichsbasiert Sortieralgorithmus, der gut funktioniert, wenn der Bereich der Eingabewerte begrenzt ist. Dies ist besonders effizient, wenn der Bereich der Eingabewerte im Vergleich zur Anzahl der zu sortierenden Elemente klein ist. Die Grundidee dahinter Zählsortierung ist das zu zählen Frequenz jedes einzelnen Elements im Eingabearray und verwenden Sie diese Informationen, um die Elemente an ihren korrekten sortierten Positionen zu platzieren.

Wie funktioniert der Zählsortieralgorithmus?

Schritt 1 :



  • Finden Sie es heraus maximal Element aus dem angegebenen Array.

Maximales Element in inputArray[] finden

Schritt 2:

  • Initialisieren Sie a countArray[] der Länge max+1 mit allen Elementen als 0 . Dieses Array wird zum Speichern der Vorkommen der Elemente des Eingabearrays verwendet.

countArray[] initialisieren



Schritt 3:

  • Im countArray[] Speichern Sie die Anzahl jedes eindeutigen Elements des Eingabearrays in den jeweiligen Indizes.
  • Zum Beispiel: Die Anzahl der Elemente 2 im Eingabearray ist 2. Also, speichern 2 am Index 2 im countArray[] . Ebenso die Anzahl der Elemente 5 im Eingabearray ist 1 , daher speichern 1 am Index 5 im countArray[] .

Behalten Sie die Anzahl jedes Elements in countArray[] bei.

Schritt 4:



  • Speichern Sie die kumulierte Summe oder Präfixsumme der Elemente der countArray[] indem man es tut countArray[i] = countArray[i – 1] + countArray[i]. Dies hilft dabei, die Elemente des Eingabearrays am richtigen Index im Ausgabearray zu platzieren.

Speichern Sie die kumulative Summe in countArray[]

Schritt 5:

  • Iterieren Sie vom Ende des Eingabearrays und da beim Durchlaufen des Eingabearrays vom Ende aus die Reihenfolge gleicher Elemente erhalten bleibt, ergibt sich letztendlich dieser Sortieralgorithmus stabil .
  • Aktualisieren OutputArray[ countArray[ InputArray[i] ] – 1] = InputArray[i] .
  • Außerdem aktualisieren countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

5

Schritt 6: Für i = 6 ,

jdbc jdbc

Aktualisieren OutputArray[ countArray[ InputArray[6] ] – 1] = InputArray[6]
Außerdem aktualisieren countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

EingabeArray[6] an der richtigen Position in AusgabeArray[] platzieren

Schritt 7: Für i = 5 ,

Aktualisieren OutputArray[ countArray[ InputArray[5] ] – 1] = InputArray[5]
Außerdem aktualisieren countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

EingabeArray[5] an der richtigen Position in AusgabeArray[] platzieren

Schritt 8: Für i = 4 ,

Aktualisieren OutputArray[ countArray[ InputArray[4] ] – 1] = InputArray[4]
Außerdem aktualisieren countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

EingabeArray[4] an der richtigen Position in AusgabeArray[] platzieren

Schritt 9: Für i = 3 ,

Aktualisieren OutputArray[ countArray[ InputArray[3] ] – 1] = InputArray[3]
Außerdem aktualisieren countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

EingabeArray[3] an der richtigen Position in AusgabeArray[] platzieren

Schritt 10: Für i = 2 ,

Aktualisieren OutputArray[ countArray[ InputArray[2] ] – 1] = InputArray[2]
Außerdem aktualisieren countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

EingabeArray[2] an der richtigen Position in AusgabeArray[] platzieren

Schritt 11: Für i = 1 ,

Aktualisieren OutputArray[ countArray[ InputArray[1] ] – 1] = InputArray[1]
Außerdem aktualisieren countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

EingabeArray[1] an der richtigen Position in AusgabeArray[] platzieren

Schritt 12: Für i = 0,

Aktualisieren OutputArray[ countArray[ InputArray[0] ] – 1] = InputArray[0]
Außerdem aktualisieren countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

EingabeArray[0] an der richtigen Position in AusgabeArray[] platzieren

Zählsortieralgorithmus:

  • Deklarieren Sie ein Hilfsarray countArray[] der Größe max(inputArray[])+1 und initialisiere es mit 0 .
  • Array durchqueren EingabeArray[] und ordne jedes Element von zu EingabeArray[] als Index von countArray[] Array, d. h. ausführen countArray[inputArray[i]]++ für 0 <= i < N .
  • Berechnen Sie die Präfixsumme an jedem Index des Arrays EingabeArray [].
  • Erstellen Sie ein Array AusgabeArray[] der Größe N .
  • Array durchqueren EingabeArray[] vom Ende und Update OutputArray[ countArray[ InputArray[i] ] – 1] = InputArray[i] . Außerdem aktualisieren countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Unten ist die Implementierung des obigen Algorithmus:

Java




import> java.util.Arrays;> public> class> CountSort {> >public> static> int>[] countSort(>int>[] inputArray) {> >int> N = inputArray.length;> >int> M =>0>;> >for> (>int> i =>0>; i M = Math.max(M, inputArray[i]); } int[] countArray = new int[M + 1]; for (int i = 0; i countArray[inputArray[i]]++; } for (int i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } int[] outputArray = new int[N]; for (int i = N - 1; i>= 0; i--) { inputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return OutputArray; } public static void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9}; int[]outputArray = countSort(inputArray); for (int i = 0; i System.out.print(outputArray[i] + ' '); } } }> 

>

>

C#




using> System;> using> System.Collections.Generic;> class> GFG> {> >static> List<>int>>CountSort(Liste<>int>>inputArray)> >{> >int> N = inputArray.Count;> >// Finding the maximum element of the array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = Math.Max(M, inputArray[i]); // Initializing countArray[] with 0 List countArray = neue Liste (neues int[M + 1]); // Jedes Element von inputArray[] als Index // des Arrays countArray[] abbilden for (int i = 0; i countArray[inputArray[i]]++; // Präfixsumme an jedem Index // des Arrays countArray berechnen [] für (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List OutputArray = neue Liste (neues int[N]); for (int i = N - 1; i>= 0; i--) { inputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return OutputArray; } // Treibercode static void Main() { // Eingabearray-Liste inputArray = neue Liste { 4, 3, 12, 1, 5, 5, 3, 9 }; // Array-Liste ausgeben OutputArray = CountSort(InputArray); for (int i = 0; i Console.Write(outputArray[i] + ' '); Console.WriteLine(); } }> 

>

>

Javascript




function> countSort(inputArray) {> >const N = inputArray.length;> >// Finding the maximum element of inputArray> >let M = 0;> >for> (let i = 0; i M = Math.max(M, inputArray[i]); } // Initializing countArray with 0 const countArray = new Array(M + 1).fill(0); // Mapping each element of inputArray as an index of countArray for (let i = 0; i countArray[inputArray[i]]++; } // Calculating prefix sum at every index of countArray for (let i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } // Creating outputArray from countArray const outputArray = new Array(N); for (let i = N - 1; i>= 0; i--) { inputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return OutputArray; } // Treibercode const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Sortieren des Eingabearrays const outputArray = countSort(inputArray); // Drucken des sortierten Arrays console.log(outputArray.join(' ')); //Dieser Code wurde von Utkarsh beigesteuert>

So wählen Sie Spalten aus verschiedenen Tabellen in SQL aus 

>

>

C++14




#include> using> namespace> std;> vector<>int>>countSort(vector<>int>>& inputArray)> {> >int> N = inputArray.size();> >// Finding the maximum element of array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = max(M, inputArray[i]); // Initializing countArray[] with 0 vector countArray(M + 1, 0); // Jedes Element von inputArray[] als Index // des Arrays countArray[] abbilden for (int i = 0; i countArray[inputArray[i]]++; // Präfixsumme an jedem Index // des Arrays countArray berechnen [] für (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector AusgabeArray(N); for (int i = N - 1; i>= 0; i--) { inputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return OutputArray; } // Treibercode int main() { // Eingabe-Array-Vektor inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // Array-Vektor ausgeben OutputArray = countSort(inputArray); for (int i = 0; i cout<< outputArray[i] << ' '; return 0; }> 

>

>

Python3




def> count_sort(input_array):> ># Finding the maximum element of input_array.> >M>=> max>(input_array)> ># Initializing count_array with 0> >count_array>=> [>0>]>*> (M>+> 1>)> ># Mapping each element of input_array as an index of count_array> >for> num>in> input_array:> >count_array[num]>+>=> 1> ># Calculating prefix sum at every index of count_array> >for> i>in> range>(>1>, M>+> 1>):> >count_array[i]>+>=> count_array[i>-> 1>]> ># Creating output_array from count_array> >output_array>=> [>0>]>*> len>(input_array)> >for> i>in> range>(>len>(input_array)>-> 1>,>->1>,>->1>):> >output_array[count_array[input_array[i]]>-> 1>]>=> input_array[i]> >count_array[input_array[i]]>->=> 1> >return> output_array> # Driver code> if> __name__>=>=> '__main__'>:> ># Input array> >input_array>=> [>4>,>3>,>12>,>1>,>5>,>5>,>3>,>9>]> ># Output array> >output_array>=> count_sort(input_array)> >for> num>in> output_array:> >print>(num, end>=>' '>)> 

>

>

Ausgabe 

1 3 3 4 5 5 9 12>

Komplexitätsanalyse der Zählsortierung:

  • Zeitkomplexität : O(N+M), wo N Und M sind die Größe von EingabeArray[] Und countArray[] jeweils.
    • Im schlimmsten Fall: O(N+M).
    • Durchschnittsfall: O(N+M).
    • Bester Fall: O(N+M).
  • Hilfsraum: O(N+M), wo N Und M sind der Platz, der von eingenommen wird AusgabeArray[] Und countArray[] jeweils.

Vorteil der Zählsortierung:

  • Zählsortierung ist im Allgemeinen schneller als alle vergleichsbasierten Sortieralgorithmen, wie z. B. Zusammenführungssortierung und Schnellsortierung, wenn der Eingabebereich in der Größenordnung der Anzahl der Eingaben liegt.
  • Die Zählsortierung ist einfach zu codieren
  • Zählsortierung ist eine stabiler Algorithmus .

Nachteil der Zählsortierung:

  • Die Zählsortierung funktioniert nicht bei Dezimalwerten.
  • Die Zählsortierung ist ineffizient, wenn der zu sortierende Wertebereich sehr groß ist.
  • Zählsortierung ist keine Sortieren vor Ort Algorithmus. Er verwendet zusätzlichen Platz zum Sortieren der Array-Elemente.