Java Entwickler Experte
Counting sort – Zählende Sortierung in Java
Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten benötigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erklären und sie in Java programmieren. Heute befassen wir uns mit der zählenden Sortierung. Bislang haben wir die folgenden Sortieralgorithmen behandelt:
In diesem Artikel erfährst du:
- Sortieralgorithmen: eine Einführung in das Sortieren von Daten,
- Bubble sort – Blasen-Sortierung,
- Comb sort – Kamm-Sortierung,
- Big O Notation: Analyse der Komplexität von Algorithmen,
- Auswahlsortierung – Sortieren nach Auswahl,
- Insertion sort – Sortieren nach Einfügung.
Counting sort
Bisher haben wir Algorithmen besprochen, die Elemente miteinander vergleichen und auf dieser Grundlage eine sortierte Ausgabe erzeugen. Heute stellen wir den ersten Algorithmus vor, der keinen Vergleich in seiner Grundlage verwendet. Counting Sort ist ein ganzzahliger stabiler Sortieralgorithmus, der auf dem Zählen von Objekten mit unterschiedlichen Schlüsselwerten basiert, aus denen die Position in der Ausgabereihenfolge bestimmt wird. Er ist nur in Situationen geeignet, in denen die Varianz der maximalen und minimalen Schlüsselwerte im Vergleich zur Anzahl der Elemente in der Eingabe relativ klein ist. Dieser Algorithmus wird oft als Hilfsroutine in der Radix-Varianteverwendet.
Counting sort Algoritmus – Funktionsprinzip
Der Zählsortieralgorithmus ist geeignet, wenn wir viele Elemente mit ganzzahligen Schlüsseln haben, die sich idealerweise in einem relativ kleinen Bereich (max – min) wiederholen. Dann können wir diesen relativ effizienten Algorithmus zum Sortieren der Eingabeelemente verwenden. Er arbeitet nach dem Prinzip des Zählens des Auftretens jedes Schlüssels, den er in einem Hilfsarray speichert. Dieses wird dann in ein Array mit Indizes umgewandelt, die die Positionen der einzelnen Elemente enthalten. Es wird dann verwendet, um die Elemente aus dem Eingabevektor auf den Ausgabevektor abzubilden. Das Funktionsprinzip des Algorithmus lässt sich am besten anhand eines praktischen Beispiels in Java verstehen, das wir implementieren werden.
Vorteile des Counting sort Algorithmus.
- Einfach zu implementieren,
- Schnell und effizient, wenn der Wertebereich 𝑘 k im Vergleich zur Anzahl der Elemente im Eingang 𝑛 n klein ist.
- stabil.
Nachteile des Counting sort Algorithmus
- Funktioniert nur für Schlüssel mit ganzzahligen Werten,
- Ineffizient bei einem großen Wertebereich.
Counting sort Zeitintensität
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Counting sort | Zählen | O(n+k) | O(n+k) | O(n+k) | O(k) | Ja |
Die Variable k ist die Anzahl der Elemente des zählenden Hilfsarrays, mathematisch k = (Maximum – Minimum + 1). Da wir über das Eingabe-Array der Elemente iterieren, erhalten wir eine zeitliche Komplexität von O(n). Die Iteration über das Hilfs-Array trägt zu einer Komplexität von O(k) bei, so dass die gesamte zeitliche Komplexität insgesamt O(n+k) beträgt. Die Speicherung von k Elementen im Hilfsarray im Speicher führt zu einer räumlichen Komplexität von O(k).
Counting sort Animation, Visualisierung, gif
Die Visualisierung von Counting sort sieht wie folgt aus:
Quelle : https://commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Eine Animation des Counting Sort Algorithmus finden du zum Beispiel auf diese Seite.
Counting sort Java-Implementierung
Jetzt zeigen wir eine einfache Implementierung des Counting Sort-Algorithmus in Java.
CountingSort.java
package sorting;
public class CountingSort {
private int min, max;
public void sort(int data[])
{
// Don't sort if there are no elements
if(data.length == 0)
return;
// Create ouput array
int[] output = new int[data.length];
// Find min and max value in 1 loop
min = data[0];
max = data[0];
for (int i = 1; i < data.length; i++) {
if (data[i] < min) {
min = data[i];
} else if (data[i] > max) {
max = data[i];
}
}
// Create count array
int k = max - min + 1;
int[] count = new int[k];
System.out.println("min = " + min + ", max = " + max +
", size (n) = " + data.length + ", range (k) = " + k);
// Count occurrences of elements
for (int i = 0; i < data.length; i++) {
count[data[i] - min]++;
}
System.out.print("Count array: ");
printArray(count);
// Transform counts to positions
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
System.out.print("Transformed count array: ");
printArray(count);
// Map the elements from input to output based on count indexes
// Do it backwards
for (int i = data.length - 1; i >= 0; i--) {
output[count[data[i] - min] - 1] = data[i];
count[data[i] - min]--;
}
// Copy the elements from output back to original array
for (int i = 0; i < data.length; i++) {
data[i] = output[i];
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}Der Algorithmus besteht aus den folgenden Schritten, die wir kurz erläutern werden:
Leeres Feld prüfen
Wenn das Feld leer ist, gibt es nichts zu sortieren.
Ermitteln der Minimal- und Maximalwerte
Zistime rozsah hodnôt min a max.
Erstellen und Initialisieren eines Zählarrays
Die Größe des Zählfelds ist die Differenz zwischen dem Höchst- und dem Mindestwert plus eins, um den gesamten Wertebereich abzudecken.
Transformation in akkumulierte Summen
Für jedes Element im Eingabefeld wird der Wert am entsprechenden Index im Zählfeld um eins erhöht.
Umwandlung in kumulierte Zählungen
Jedes Element in der Zählmatrix wird durch die Summe aller vorherigen Werte aktualisiert, wodurch die endgültigen Positionen der Elemente in der Ausgangsmatrix bestimmt werden.
Platzierung der Elemente im Ausgabefeld
Das Eingabe-Array wird rückwärts durchlaufen (um Stabilität zu gewährleisten) und die Elemente werden auf der Grundlage der Werte im Zähl-Array im Ausgabe-Array platziert, wobei der Index des Zähl-Arrays nach jeder Platzierung eines Elements um 1 verringert wird.
Kopieren der Ausgabe zurück in das ursprüngliche Array
Die sortierten Elemente aus dem Ausgabefeld werden zurück in das ursprüngliche Feld kopiert.
Main.java
import sorting.CountingSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 4, 2, 4, 2, 1, 1, 1, 7, 6, 3, 5, 5 };
CountingSort countingSort = new CountingSort();
System.out.print("Input: ");
countingSort.printArray(dataToSort);
countingSort.sort(dataToSort);
System.out.print("Sorted: ");
countingSort.printArray(dataToSort);
}
}Die Ausgabe dieses Beispiels ist:
Counting sort – Java-Code
Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausführen kannst. Lade den Java Counting Sort Code herunter.
Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.
