Bucket-Sortieralgorithmus (Java-, Python-, C/C++-Codebeispiele)

Was ist Bucket Sort?

Bucket-Sortierung, oft auch Bin-Sortierung genannt, ist eine Vergleichssortiermethode, die ein unsortiertes Array als Eingabe akzeptiert und als Ergebnis ein sortiertes Array erzeugt. Bei dieser Methode werden die Elemente auf mehrere Buckets verteilt und jeder dieser Buckets einzeln nach einem beliebigen Sortieralgorithmus wie der Einfügungssortierung sortiert. Anschließend werden alle Buckets zu einem sortierten Array zusammengeführt.

Bucket-Sortierung wird häufig verwendet, wenn die Elemente-

  1. Gleitkommawerte
  2. Gleichmäßig über einen Bereich verteilt

Bucket Sort's Time complexDie Intensität hängt von der Anzahl der verwendeten Buckets und der Gleichmäßigkeit der Eingabeverteilung ab. Während verschiedene Sortieralgorithmen wie z Muschelsortierung, Zusammenführungssortierung, Heapsortierung und schnelle Sorte kann im besten Fall Zeit erreichenplexity von O(n*logn) kann der Bucket-Sortieralgorithmus dasselbe in linearer Zeitkompensation erreichenplexity oder O(n).

Die Bucket-Sortierung folgt dem Scatter-Gather-Ansatz. Bei diesem Ansatz werden Elemente in die entsprechenden Buckets verteilt, in den Buckets sortiert und im letzten Schritt zu einem sortierten Array gesammelt. Dieser Scatter-Gather-Ansatz wird im Folgenden erläutertwing Abschnitt

Scatter-Gather-Ansatz

Großformatig, complex Probleme können manchmal schwierig zu lösen sein. Der Scatter-Gather-Ansatz versucht, solche Probleme zu lösen, indem der gesamte Datensatz in Cluster aufgeteilt wird. Dann wird jeder Cluster einzeln angesprochen und alles wieder zusammengeführt, um die endgültige Antwort zu erhalten.

So implementiert der Bucket-Sortieralgorithmus die Scatter-Gather-Methode:

Scatter-Gather-Ansatz

So funktioniert Bucket Sort

Das grundlegende Funktionsprinzip der Bucket-Sortierung ist wie folgt:

  1. Es wird eine Reihe leerer Buckets erstellt. Aufgrund unterschiedlicher Richtlinien kann die Anzahl der Buckets unterschiedlich sein.
  2. Platzieren Sie jedes Element aus dem Eingabearray in seinem entsprechenden Bucket.
  3. Sortieren Sie diese Eimer einzeln.
  4. Verketten Sie die sortierten Buckets, um ein einzelnes Ausgabearray zu erstellen.

Die detaillierten Arbeitsschritte finden Sie im Folgendenwing .

Pseudocode

Start
Create N empty buckets
For each array element:
Calculate bucket index
Put that element into the corresponding bucket
For each bucket:
Sort elements within each bucket
Merge all the elements from each bucket
Output the sorted array
End

Methode 1: Bucket-Sortieralgorithmus für Gleitkommazahlen

Der Bucket-Sortieralgorithmus für Gleitkommazahlen im Bereich von 0.0 bis 1.0:

Schritt 1) Erstellen Sie zehn (10) leere Buckets, sodass der erste Bucket Zahlen im Bereich [0.0, 0.1) enthält. Dann enthält der zweite Bucket innerhalb von [0.1, 0.2) und so weiter.

Schritt 2) Für jedes Array-Element:

      A. Berechnen Sie den Bucket-Index mit der Formel:
      Bucket-Index= no_of_buckets *array_element
      B. Fügen Sie das Element in den Bucket ein[bucket_index]

Schritt 3) Sortieren Sie jeden Eimer einzeln mithilfe der Einfügungssortierung.

Schritt 4) Verketten Sie alle Buckets in einem einzigen Array.

Sehen wir uns ein Beispiel für eine Bucket-Sortierung an. Für dieses Beispiel werden wir Folgendes sortierenwing Array mit dem Bucket-Sortieralgorithmus-

Bucket-Sortieralgorithmus für Gleitkommazahlen

Schritt 1) Zuerst erstellen wir 10 leere Eimer. Der erste Bucket enthält die Zahlen zwischen [0.0, 0.1). Dann enthält der zweite Eimer die Zahlen zwischen [0.1, 0.2) und so weiter.

Bucket-Sortieralgorithmus für Gleitkommazahlen

Schritt 2) Für jedes Array-Element berechnen wir den Bucket-Index und platzieren das Element in diesem Bucket.

Der Bucket-Index kann mit der Formel berechnet werden:
              Bucket_index= no_of_buckets*array_element

Berechnung des Bucket-Index:
a) 0.78
      Bucket_index = no_of_buckets*array_element
                   = 10 * 0.78
                   = 7.8
Daher wird das Element 0.78 auf dem Bucket[Boden(7.8)] oder dem Bucket[7] gespeichert.

Bucket-Sortieralgorithmus für Gleitkommazahlen

b) 0.17
      Bucket_index = no_of_buckets * Array-Element
                   = 10 * 0.17
                   = 1.7

Das Array-Element 0.17 wird auf Bucket[floor(1.7)] oder Bucket[1] gespeichert.

Bucket-Sortieralgorithmus für Gleitkommazahlen

c) 0.39
      Bucket_index = no_of_buckets * Array-Element
                   = 10 * 0.39
                   = 3.9
   0.39 werden auf Bucket[Boden(3.9)] oder Bucket[3] gespeichert.

Bucket-Sortieralgorithmus für Gleitkommazahlen

Nach der Iteration über alle Array-Elemente sind die Buckets wie folgtwing:

Bucket-Sortieralgorithmus für Gleitkommazahlen

Schritt 3) Anschließend wird jeder Bucket mithilfe der Einfügungssortierung sortiert. Nach dem Sortiervorgang wäre die Ausgabe:

Bucket-Sortieralgorithmus für Gleitkommazahlen

Schritt 4) Im letzten Schritt werden die Buckets zu einem einzigen Array verkettet. Dieses Array ist das sortierte Ergebnis der Eingabe.

Jeder Bucket wird mit dem Ausgabearray verkettet. Zum Beispiel die Verkettung der zweiten Bucket-Elemente:

Bucket-Sortieralgorithmus für Gleitkommazahlen

Die Verkettung der letzten Bucket-Elemente ist wie folgtwing:

Bucket-Sortieralgorithmus für Gleitkommazahlen

Nach der Verkettung ist das resultierende Array das gewünschte sortierte Array.

Bucket-Sortieralgorithmus für Gleitkommazahlen

Bucket-Sort-Programm in C/C++

Eingang:

//Bucket Sort Program in C/C++
//For not having integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
  vector <float>bucket[BUCKET_SIZE];
for (int i = 0; i < array_size; i++) {
    int index = BUCKET_SIZE*input[i];
 bucket[index].push_back(input[i]);
  }
for (int i = 0; i < BUCKET_SIZE; i++)
    sort(bucket[i].begin(), bucket[i].end());
  int out_index = 0;
  for (int i = 0; i < BUCKET_SIZE; i++)
    for (int j = 0; j < bucket[i].size(); j++)
      input[out_index++] = bucket[i][j];
}
int main()
{
float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
 int array_size = sizeof(input)/sizeof(input[0]);
 
 bucketSort(input, array_size);
 cout <<"Sorted Output: \n";
 for (int i = 0; i< array_size; i++)
 cout<<input[i]<<" ";
return 0;
}

Ausgang:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Bucket-Sortierungsprogramm in Python

Eingang:

# Bucket Sort Program in Python
# For not having integer parts
def bucketSort(input):
    output = []
    bucket_size = 10
    for bucket in range(bucket_size):
        output.append([])
    for element in input:
        index = int(bucket_size * element)
        output[index].append(element)
    for bucket in range(bucket_size):
        output[bucket] = sorted(output[bucket])
    out_index = 0
    for bucket in range(bucket_size):
        for element in range(len(output[bucket])):
            input[out_index] = output[bucket][element]
            out_index += 1
    return input

input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))

Ausgang:

Sorted Output:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]

Bucket-Sortierung in Java

Eingang:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    private static final int BUCKET_SIZE = 10;
    public static void bucketSort(float[] input, int arraySize) {
        List <
        Float >
        [] bucket = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < arraySize; i++) {
            int index = (int)(BUCKET_SIZE * input[i]);
            if (bucket[index] == null) {
                bucket[index] = new ArrayList < >
                ();
            }
            bucket[index].add(input[i]);
        }
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
            }
        }
        int outIndex = 0;
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                for (float value: bucket[i]) {
                    input[outIndex++] = value;
               }
            }
        }
    }
    public static void main(String[] args) {
    float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
        int arraySize = input.length;
        bucketSort(input, arraySize);
        System.out.println("Sorted Output:");
        for (int i = 0; i < arraySize; i++) {
            System.out.print(input[i]+" ");
        }
    }
}

Ausgang:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Methode 2: Bucket-Sortieralgorithmus für ganzzahlige Elemente

Der Bucket-Sortieralgorithmus für die Eingabe, die Zahlen außerhalb des Bereichs [0.0, 1.0] enthält, unterscheidet sich ein wenig vom vorherigen Algorithmus. Die für diesen Fall erforderlichen Schritte sind wie folgt:

Schritt 1) Finden Sie die maximalen und minimalen Elemente.

Schritt 2) Wählen Sie die Anzahl der Buckets (n) aus und initialisieren Sie diese Buckets als leer.

Schritt 3) Berechnen Sie die Reichweite oder Spanne jedes Buckets mithilfe der Formel:
               span = (maximum - minimum)/n

Schritt 4) Für jedes Array-Element:

    1.Bucket-Index berechnen:
                   bucket_index = (element - minimum)/span
    2.Fügen Sie das Element in den Bucket[bucket_index] ein.

Schritt 5) Sortieren Sie jeden Bucket mithilfe der Einfügungssortierung.

Schritt 6) Verketten Sie alle Buckets in einem einzigen Array.

Sehen wir uns ein Beispiel für diesen Bucket-Sortieralgorithmus an. Für dieses Beispiel werden wir Folgendes sortierenwing Array mit dem Bucket-Sortieralgorithmus-

Bucket-Sortieralgorithmus für ganzzahlige Elemente

Schritt 1) Im ersten Schritt müssen die maximalen und minimalen Elemente des angegebenen Arrays ermittelt werden. In diesem Beispiel beträgt der Höchstwert 24 und der Mindestwert 1.

Schritt 2) Jetzt müssen wir eine Anzahl leerer Eimer auswählen, n. In diesem Beispiel nehmen wir 5 Eimer. Dann werden wir sie als leer initialisieren.

Schritt 3) Die Spannweite jedes Eimers muss wie folgt berechnet werdenwing Formel:
               span = (maximum-minimum)/n = (24-1)/5 = 4;

Daher enthält der erste Bucket die Zahlen im Bereich [0, 5). Der zweite Bucket enthält die Zahlen innerhalb von [5, 10) usw.

Bucket-Sortieralgorithmus für ganzzahlige Elemente

Schritt 4) Für jedes Array-Element berechnen wir den Bucket-Index und platzieren das Element in diesem Bucket. Der Bucket-Index kann mit der Formel berechnet werden:
               bucket_index = (element - minimum)/span

Berechnung des Bucket-Index:

    a) 11bucket_index = (Element – ​​Minimum)/Span
                       =(11-1)/4
                       =2

Daher wird Element 11 in Bucket[2] gespeichert.

Bucket-Sortieralgorithmus für ganzzahlige Elemente

    b) 9
    Bucket_index = (Element – ​​Minimum)/Span
                       =(9-1)/4
                       =2

Hinweis: Da 9 ein Grenzelement für Bucket[1] ist, muss es in Bucket[1] angehängt werden, anstatt in denselben Bucket wie das vorherige Element.

Bucket-Sortieralgorithmus für ganzzahlige Elemente

Nachdem die Operationen für jedes Element ausgeführt wurden, sehen die Buckets wie folgt aus:

Bucket-Sortieralgorithmus für ganzzahlige Elemente

Schritt 5) Jetzt wird jeder Bucket mithilfe der Einfügungssortierung sortiert. Die Eimer nach dem Sortieren

Bucket-Sortieralgorithmus für ganzzahlige Elemente

Schritt 6) Im letzten Schritt werden die Buckets zu einem einzigen Array verkettet. Das Array wird das sortierte Ergebnis der Eingabe sein.

Bucket-Sortieralgorithmus für ganzzahlige Elemente

Bucket-Sort-Programm in C/C++

Eingang:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
  double max_value = * max_element(input.begin(), input.end());
  double min_value = * min_element(input.begin(), input.end());
  double span = (max_value - min_value) / No_Of_Buckets;
  vector<vector <double>>
  output;
  for (int i = 0; i < No_Of_Buckets; i++)
    output.push_back(vector <double>
      ());
  for (int i = 0; i < input.size(); i++)
  {
    double difference = (input[i] - min_value) / span
     -
      int((input[i] - min_value) / span);
    if (difference == 0 && input[i] != min_value)
      output[int((input[i] - min_value) / span) - 1]
      .push_back(input[i]);
    else
      output[int((input[i] - min_value) / span)].push_back(
        input[i]);
  }
  for (int i = 0; i < output.size(); i++)
  {
    if (!output[i].empty())
      sort(output[i].begin(), output[i].end());
  }
  int index = 0;
  for (vector <double> & bucket: output)
  {
    if (!bucket.empty())
    {
      for (double i: bucket)
      {
        input[index] = i;
        index++;
      }
    }
  }
}
int main()
{
  vector <double>
  input ={11,9,21,8,17,19,13,1,24,12
  };
  int No_Of_Buckets = 5;
  bucketSort(input, No_Of_Buckets);
  cout<<
  "Sorted Output:";
  for (int i; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

Ausgang:

Sorted Output:1 8 9 11 12 13 17 19 21 24

Bucket-Sortierungsprogramm in Python

Eingang:

def bucketSort(input, No_Of_Buckets):
    max_element = max(input)
    min_element = min(input)
    span = (max_element - min_element) / No_Of_Buckets
    output = []
    for bucket in range(No_Of_Buckets):
        output.append([])
    for element in range(len(input)):
        diff = (input[element] - min_element) / span - int(
            (input[element] - min_element) / span
        )
        if diff == 0 and input[element] != min_element:
            output[int((input[element] - min_element) / span) - 1].append(
                input[element]
            )
        else:
            output[int((input[element] - min_element) / span)].append(input[element])
    for bucket in range(len(output)):
        if len(output[bucket]) != 0:
            output[bucket].sort()
    index = 0
    for bucket in output:
        if bucket:
            for element in bucket:
                input[index] = element
                index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:\n", input)

Ausgang:

Sorted Output:
[1, 8, 9, 11, 12, 13, 17, 19, 21, 24]

Bucket-Sortierung in Java

Eingang:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void bucketSort(List < Double > input, int No_Of_Buckets) {
        double max_value = Collections.max(input);
        double min_value = Collections.min(input);
        double span =(max_value - min_value) / No_Of_Buckets;
        List <
        List <
        Double > >
        output = new ArrayList < >
        ();
        for (int i = 0; i < No_Of_Buckets; i++) {
            output.add(new ArrayList < >
                ());
        }
        for (Double value: input) {
            double difference = (value - min_value) / span - ((value - min_value) / span);
            if (difference == 0 && value != min_value) {
                output.get((int)((value - min_value) / span) - 1).add(value);
            } else {
                output.get((int)((value - min_value) / span)).add(value);
				}
			}
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
			Collections.sort(bucket);
            }
        }
        int index = 0;
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                for (Double value: bucket) {
                    input.set(index,value);
                    index++;
                }
            }
        }
    }
    public static void main(String[] args) {
        List <Double>
        input = new ArrayList <>
        ();
        input.add(11.0);
		input.add(9.0);
        input.add(21.0);
        input.add(8.0);
        input.add(17.0);
        input.add(19.0);
        input.add(13.0);
        input.add(1.0);
        input.add(24.0);
        input.add(12.0);
        int No_Of_Buckets = 5;
        bucketSort(input, No_Of_Buckets);
        System.out.println("Sorted Output:");
        for (Double value: input) {
		System.out.print(value + " ");
        }
    }
}

Ausgang:

Sorted Output:
1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0

Pros & Cons

Vorteile Nachteile
Führen Sie schnellere Berechnungen durch Verbraucht im Vergleich zu anderen Algorithmen mehr Platz
Es kann als externe Sortiermethode verwendet werden Die Leistung ist schlecht, wenn die Daten nicht gleichmäßig verteilt sind
Eimer können unabhängig voneinander verarbeitet werden

Bucket Sort Complexity-Analyse

Time Com von Bucket Sortplexity

  • Best Case Complexität:Wenn alle Array-Elemente vorher gleichmäßig verteilt und sortiert werden, würde es O(n) Zeit erfordern, die Elemente in die entsprechenden Buckets zu verteilen. Dann sortieren Sie jeden Eimer nach Sortieren durch Einfügen würde O(k) kosten. Somit ist die Gesamtcomplexität wäre O(n+k).
  • Durchschnittlicher Fall Complexität:Für durchschnittliche Fälle gehen wir davon aus, dass die Eingaben gleichmäßig verteilt sind. Somit erreicht der Bucket-Sortieralgorithmus eine lineare Zeitkompensationplexität von O(n+k). Hier ist O(n) Zeit zum Streuen der Elemente und O(k) Zeit zum Sortieren dieser Elemente mithilfe der Einfügungssortierung erforderlich.
  • Worst Case Complexität:Im schlimmsten Fall werden die Elemente nicht gleichmäßig auf ein oder zwei bestimmte Eimer verteilt und konzentriert. In diesem Fall funktioniert die Bucket-Sortierung als Blasensortierungsalgorithmus. Daher kann es im schlimmsten Fall zu einem Zeitverlust kommenplexDie Größe einer Bucket-Sortierung wäre O(n^2).

Weltraumkomplexität von Bucket Sort

Space com von Bucket Sortplexität ist O(n*k). Dabei ist n die Anzahl der Elemente und k die Anzahl der benötigten Buckets.