Bucket Sort in Java

1. Einleitung

In diesem Artikel werden wir uns mit dem Bucket-Sortieralgorithmus befassen. Wir beginnen mit einer kurzen Theorie, bevor wir neben dem Unit-Test unserer Lösung an der Java-Implementierung arbeiten . Schließlich werden wir uns die zeitliche Komplexität der Bucket-Sortierung ansehen .

2. Die Theorie der Eimersortierung

Die Bucket-Sortierung, manchmal auch als Bin-Sortierung bezeichnet, ist ein spezifischer Sortieralgorithmus. Die Sortierung verteilt die Elemente, die sortiert werden sollen, auf mehrere einzeln sortierte Buckets. Auf diese Weise können wir die Anzahl der Vergleiche zwischen den Elementen reduzieren und die Sortierzeit verkürzen.

Werfen wir einen kurzen Blick auf die Schritte, die zum Ausführen einer Bucket-Sortierung erforderlich sind :

  1. Richten Sie eine Reihe unserer anfangs leeren Eimer ein
  2. Verteilen Sie unsere Elemente in den entsprechenden Eimern
  3. Sortieren Sie jeden Eimer
  4. Verketten Sie die sortierten Buckets, um die vollständige Liste neu zu erstellen

3. Java-Implementierung

Obwohl dieser Algorithmus nicht sprachspezifisch ist, werden wir die Sortierung in Java implementieren. Lassen Sie uns die obige Liste Schritt für Schritt durchgehen und den Code schreiben, um eine Liste von Ganzzahlen zu sortieren.

3.1. Bucket Setup

Zuerst müssen wir einen Hashing-Algorithmus bestimmen , um zu entscheiden, welches unserer Elemente in welchen Bucket gestellt wird:

private int hash(int i, int max, int numberOfBuckets) { return (int) ((double) i / max * (numberOfBuckets - 1)); }

Mit unserer definierten Hash-Methode können wir jetzt die Anzahl der Bins als Quadratwurzel der Größe der Eingabeliste angeben :

final int numberOfBuckets = (int) Math.sqrt(initialList.size()); List
    
      buckets = new ArrayList(numberOfBuckets); for(int i = 0; i < numberOfBuckets; i++) { buckets.add(new ArrayList()); }
    

Schließlich benötigen wir eine kurze Methode, um die maximale Ganzzahl in unserer Eingabeliste zu bestimmen:

private int findMax(List input) { int m = Integer.MIN_VALUE; for (int i : input) { m = Math.max(i, m); } return m; }

3.2. Verteilen der Elemente

Nachdem wir unsere Buckets definiert haben, können wir jedes Element unserer Eingabeliste mithilfe der Hash- Methode in den entsprechenden Bucket verteilen :

int max = findMax(initialList); for (int i : initialList) { buckets.get(hash(i, max, numberOfBuckets)).add(i); } 

3.3. Sortieren der einzelnen Eimer

Wenn unsere Buckets definiert und voller Ganzzahlen sind, verwenden wir einen Komparator , um sie zu sortieren :

Comparator comparator = Comparator.naturalOrder(); for(List bucket : buckets){ bucket.sort(comparator); }

3.4. Verkettung unserer Eimer

Schließlich müssen wir unsere Eimer zusammenziehen, um die einzelne Liste neu zu erstellen. Da unsere Buckets sortiert sind, müssen wir jeden Bucket nur einmal durchlaufen und die Elemente an eine Masterliste anhängen:

List sortedArray = new LinkedList(); for(List bucket : buckets) { sortedArray.addAll(bucket); } return sortedArray;

4. Testen unseres Codes

Nachdem unsere Implementierung abgeschlossen ist, schreiben wir einen kurzen Komponententest, um sicherzustellen, dass er wie erwartet funktioniert:

BucketSorter sorter = new IntegerBucketSorter(); List unsorted = Arrays.asList(80,50,60,30,20,10,70,0,40,500,600,602,200,15); List expected = Arrays.asList(0,10,15,20,30,40,50,60,70,80,200,500,600,602); List sorted = sorter.sort(unsorted); assertEquals(expected, sorted);

5. Zeitkomplexität

Lassen Sie uns als nächstes einen kurzen Blick auf die zeitliche Komplexität der Durchführung einer Bucket-Sortierung werfen.

5.1. Worst-Case-Szenario

In unserem Worst-Case-Szenario würden wir alle unsere Elemente im selben Bucket und in umgekehrter Reihenfolge finden. In diesem Fall reduzieren wir unsere Bucket-Sortierung auf eine einfache Sortierung, bei der jedes Element mit jedem anderen Element verglichen wird, was eine zeitliche Komplexität von O (n²) ergibt .

5.2. Durchschnittliches Fallszenario

In unserem Durchschnittsfall stellen wir fest, dass die Elemente relativ gleichmäßig auf unsere Eingabe-Buckets verteilt sind. Da jeder unserer Schritte nur eine Iteration durch unsere Eingabe-Buckets erfordert, stellen wir fest, dass unsere Bucket-Sortierung in O (n) -Zeit abgeschlossen ist .

6. Fazit

In diesem Artikel haben wir gesehen, wie eine Bucket-Sortierung in Java implementiert wird. Wir haben uns auch die zeitliche Komplexität des Bucket-Sortieralgorithmus angesehen.

Wie immer ist der in diesem Artikel gezeigte Code über GitHub verfügbar.