Java Entwickler Experte
Bucket sort (bin sort) – Sortieren nach Eimern (bins) 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 schnellen Bucket sort, auch bekannt als Bin-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,
- Selection sort – Sortieren nach Auswahl,
- Insertion sort – Sortieren nach Einfügung,
- Counting sort – Sortieren durch Zählen,
- Heap sort – Heap Sortierung
- Merge sort – Sortieren durch Aufteilen und Zusammenführen,
- Quick sort – schnelles Sortieren mit Pivot.
Bucket sort, Bin sort Algorithmus
Bucket (Bin) Sort ist eine spezielle Sortiertechnik, die darin besteht, die Elemente des Eingabevektors in verschiedene Gruppen (Buckets oder Bins) zu unterteilen. Diese Gruppen werden auf der Grundlage einer gleichmäßigen Verteilung gebildet (siehe auch Uniform distribution). Die Gruppen werden dann einzeln durch einen beliebigen Sortieralgorithmus sortiert und die sortierte Ausgabe ist die Vereinigung der Ergebnisse der einzelnen Buckets. Die Rechenkomplexität des Algorithmus hängt dann von dem Algorithmus ab, der die Daten in jeder Gruppe sortiert, von der Anzahl der Gruppen sowie von der Gleichverteilung der Werte in der Eingabe.
Bucket sort, Bin sort – Funktionsprinzip des Algorithmus
Wenn wir eine große Menge an Daten sortieren müssen, die die Eigenschaft haben, gleichmäßig sortiert zu sein (z.B. Ordnungszahlen), können wir durch die Aufteilung in Untergruppen die Anzahl der Vergleiche zwischen den Elementen reduzieren, was uns hilft, die Sortierzeit zu verringern. Sobald die Daten sortiert sind, können wir sie in Gruppen sortiert lassen und beim Hinzufügen neuer Elemente zu den Gruppen nur die Gruppen sortieren, zu denen das neue Element hinzugefügt wurde. Sortierte Daten lassen sich auch einfacher und schneller sortieren, wenn wir dafür einen geeigneten Algorithmus verwenden, wie z.B. Insertion sort. Die Aufteilung in mehrere Gruppen ermöglicht es uns außerdem, parallele Sortier- und Datenverarbeitungstechniken einzusetzen. Das Grundprinzip des Bucket-Sortieralgorithmus ist wie folgt:
- Bestimmung der Anzahl der Buckets Durch einen einmaligen Durchlauf der Werte können wir den maximalen Wert ermitteln.
- Erstellung eines Arrays mit leeren Anfangs-Buckets
- Verteilung der Elemente in die entsprechenden Buckets
Am besten erfolgt die Verteilung der Elemente (Scatter) mithilfe einer einfachen Hash-Funktion. - Sortierung der Elemente in jedem Bucket
- Zusammenführen (gather) der Ergebnisse aus den einzelnen Buckets in der richtigen Reihenfolge
Bucket sort Animation, Visualisierung
Vorteile des Bucket sort Algorithmus
- Relativ effizient für Daten mit gleichmäßiger Verteilung: Dezimalzahlen im Bereich von 0,0 bis 1,0 oder Ganzzahlen in einem engen Bereich.
- Stabil, wenn ein stabiler Sortieralgorithmus zum Sortieren der Daten nach Gruppen verwendet wird.
- Es kann parallelisiert werden, um die Berechnungslast auf mehrere Prozessoren zu verteilen.
Nachteile des Bucket sort Algorithmus
- Erfordert zusätzlichen Speicherplatz für die Erstellung von Gruppen.
- Eine unpassend gewählte Varianzfunktion kann die Zeitkomplexität erheblich erhöhen.
Bucket Sort – Zeitkomplexität
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Bucket sort | Distribution | O(n²) | O(n + k) | O(n + k) | O(n + k) | ja/nein |
Variable n = Anzahl der Array-Elemente, k = Anzahl der Eimer
Der schlimmste Fall von Bucket sort Zeitkomplexität
Im schlimmsten Fall landen alle Elemente im selben Bucket in umgekehrter Reihenfolge. Dies kann entweder auf eine ungeeignete Datenverteilung für diesen Algorithmus oder auf eine schlecht implementierte Streufunktion zurückzuführen sein. In diesem Fall nähert sich die Zeitkomplexität O(n²).
Bucket Sort – Implementierung, Java-Code
Jetzt schauen wir uns die Implementierung des Bucket-Sort-Algorithmus in Java an.
BucketSort.java
package sorting;
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public void sort(float[] data)
{
// Set optimal bucket count here
int bucketCount = 10;
ArrayList<Float>[] buckets = new ArrayList[bucketCount];
// Create empty buckets
for (int i = 0; i < bucketCount; i++) {
buckets[i] = new ArrayList<>();
}
// Scatter elements into buckets using appropriate hash function
for (float f : data) {
int bucketIndex = (int) Math.floor(f * 10);
buckets[bucketIndex].add(f);
}
System.out.println("After distribution:");
for (int i = 0; i < bucketCount; i++) {
printBucket(i, buckets[i]);
}
// Sort all the buckets
for (int i = 0; i < bucketCount; i++) {
Collections.sort(buckets[i]);
}
System.out.println("After sorting individual buckets:");
for (int i = 0; i < bucketCount; i++) {
printBucket(i, buckets[i]);
}
// Concatenate buckets elements to get sorted data
int j = 0;
for (int i = 0; i < bucketCount; i++) {
for (float num : buckets[i]) {
data[j++] = num;
}
}
}
public void printBucket(int id, ArrayList<Float> data)
{
System.out.println("Bucket " + id + " -> " + data);
}
// Function to print an array
public void printArray(float[] data)
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
}
}Main.java
import sorting.BucketSort;
public class Main {
public static void main(String[] args) {
float[] dataToSort = { 0.88f, 0.16f, 0.39f, 0.26f, 0.82f, 0.94f, 0.21f, 0.12f, 0.23f, 0.68f };
BucketSort bucketSort = new BucketSort();
System.out.print("Input: ");
bucketSort.printArray(dataToSort);
System.out.println();
bucketSort.sort(dataToSort);
System.out.print("Sorted: ");
bucketSort.printArray(dataToSort);
}
}Die Ausgabe dieses Beispiels ist:
Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausführen kannst. Lade den Java-Code für BucketSort herunter.
Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.
