In diesem Tutorial erfahren Sie, wie das Zählen der Sortierung funktioniert. Außerdem finden Sie Arbeitsbeispiele zum Zählen der Sortierung in C, C ++, Java und Python.
Counting Sort ist ein Sortieralgorithmus, der die Elemente eines Arrays sortiert, indem die Anzahl der Vorkommen jedes einzelnen Elements im Array gezählt wird. Die Zählung wird in einem Hilfsarray gespeichert, und die Sortierung erfolgt durch Zuordnung der Zählung als Index des Hilfsarrays.
Wie funktioniert das Zählen der Sortierung?
- Finden Sie das maximale Element (sei es
max) aus dem angegebenen Array heraus.
Gegebenes Array - Initialisieren Sie ein Array mit einer Länge
max+1mit allen Elementen 0. Dieses Array wird zum Speichern der Anzahl der Elemente im Array verwendet.
Array zählen - Speichern Sie die Anzahl jedes Elements an ihrem jeweiligen Index im
countArray
. Beispiel: Wenn die Anzahl von Element 3 2 ist, wird 2 an der 3. Position des Zählarrays gespeichert. Wenn das Element "5" nicht im Array vorhanden ist, wird 0 an fünfter Stelle gespeichert.
Anzahl jedes gespeicherten Elements - Speichern Sie die kumulative Summe der Elemente des Zählarrays. Es hilft beim Platzieren der Elemente im richtigen Index des sortierten Arrays.
Kumulative Anzahl - Suchen Sie den Index jedes Elements des ursprünglichen Arrays im Zählarray. Dies ergibt die kumulative Anzahl. Platzieren Sie das Element an dem Index, der wie in der folgenden Abbildung dargestellt berechnet wurde.
Sortierung zählen - Nachdem Sie jedes Element an der richtigen Position platziert haben, verringern Sie seine Anzahl um eins.
Sortieralgorithmus zählen
countSort (Array, Größe) max <- größtes Element im Array finden Zählarray mit allen Nullen für j <- 0 initialisieren, um die Gesamtzahl jedes eindeutigen Elements zu ermitteln und die Anzahl am j-ten Index im Zählarray für i <- 1 zu speichern Um die kumulative Summe maximal zu finden und sie im Zählarray selbst für j <- Größe bis 1 zu speichern, stellen Sie die Anzahl der Elemente des wiederhergestellten Elements jedes Arrays um 1 wieder her
Beispiele für Python, Java und 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); )
Komplexität
Zeitkomplexität:
Es gibt hauptsächlich vier Hauptschleifen. (Das Finden des größten Werts kann außerhalb der Funktion erfolgen.)
| for-Schleife | Zeit des Zählens |
|---|---|
| 1 | O (max) |
| 2 .. | O (Größe) |
| 3 .. | O (max) |
| 4 .. | O (Größe) |
Gesamtkomplexität = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Worst-Case-Komplexität:
O(n+k) - Best-Case-Komplexität:
O(n+k) - Durchschnittliche Fallkomplexität:
O(n+k)
In allen oben genannten Fällen ist die Komplexität gleich, da der Algorithmus unabhängig von der Platzierung der Elemente im Array n+kZeiten durchläuft .
Es gibt keinen Vergleich zwischen Elementen, daher ist dies besser als vergleichsbasierte Sortiertechniken. Es ist jedoch schlecht, wenn die Ganzzahlen sehr groß sind, da das Array dieser Größe erstellt werden sollte.
Raumkomplexität:
Die räumliche Komplexität von Counting Sort ist O(max). Je größer der Bereich der Elemente ist, desto größer ist die Komplexität des Raums.
Sortieranwendungen zählen
Die Zählsortierung wird verwendet, wenn:
- Es gibt kleinere Ganzzahlen mit mehreren Zählungen.
- lineare Komplexität ist die Notwendigkeit.
