Algoritme voor emmersortering (Java, Python, C/C++ Code Voorbeelden)

Wat is bucketsortering?

Bucketsort, ook wel binsort genoemd, is een op vergelijkingen gebaseerde sorteermethode die een ongesorteerde array als invoer accepteert en een gesorteerde array als uitvoer produceert. Deze techniek verdeelt de elementen over verschillende buckets en sorteert elke bucket afzonderlijk met behulp van een ander sorteeralgoritme, zoals insertiesortering. Vervolgens worden alle buckets samengevoegd om de uiteindelijke gesorteerde array te vormen.

Bucket Sort wordt vaak gebruikt wanneer de elementen:

1. Waarden met drijvende komma
2. Gelijkmatig verdeeld over een bekend bereik

De tijdscomplexiteit van Bucket Sort hangt af van het aantal gebruikte buckets en de uniformiteit van de invoerverdeling. Terwijl andere sorteeralgoritmen zoals schelp soort, sorteer, heapsort en Snel sorteren Om in het beste geval een tijdcomplexiteit van O(n*logn) te bereiken, kan het Bucket Sort-algoritme onder gunstige omstandigheden een lineaire tijdcomplexiteit van O(n) bereiken.

Bucket Sort volgt de scatter-gather-methode. Elementen worden verspreid over de bijbehorende buckets, binnen elke bucket gesorteerd en in de laatste stap verzameld om een ​​gesorteerde array te vormen. Deze scatter-gather-methode wordt in de volgende sectie besproken.

Verspreidings- en verzamelbenadering

Grootschalige, complexe problemen kunnen soms lastig zijn om direct op te lossen. De scatter-gather-methode pakt dergelijke problemen aan door de gehele dataset in clusters te verdelen. Elk cluster wordt afzonderlijk verwerkt en de resultaten worden vervolgens weer samengevoegd om het uiteindelijke antwoord te verkrijgen.

Hieronder wordt uitgelegd hoe het Bucket Sort-algoritme de scatter-gather-methode implementeert:

Hoe emmersortering werkt

Het basiswerkingsprincipe van Bucket Sort is als volgt:

1. Er wordt een set lege emmers aangemaakt. Afhankelijk van het gekozen beleid kan het aantal emmers variëren.
2. Elk element uit de invoerarray wordt in het bijbehorende vakje geplaatst.
3. Elke emmer wordt afzonderlijk gesorteerd met behulp van een secundair sorteeralgoritme.
4. De gesorteerde buckets worden samengevoegd tot één enkele uitvoerarray.

Pseudo Code

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-sorteeralgoritme voor drijvende-komma Numbers

Het Bucket Sort-algoritme voor drijvende-komma getallen in het bereik [0.0, 1.0]:

Stap 1) Maak tien (10) lege emmers. De eerste emmer bevat getallen binnen het bereik [0.0, 0.1). De tweede emmer bevat [0.1, 0.2), enzovoort.

Stap 2) Voor elk array-element:

• a. Bereken de bucketindex met behulp van de formule:
  bucket_index = aantal_buckets * array_element
• b. Voeg het element in bucket[bucket_index] in.

Stap 3) Sorteer elke emmer afzonderlijk met behulp van invoegsortering.

Stap 4) Voeg alle buckets samen tot één gesorteerde array.

Laten we een voorbeeld van Bucket Sort bekijken. In dit voorbeeld sorteren we de volgende array:

Stap 1) Eerst maken we 10 lege emmers aan. De eerste emmer bevat getallen in het bereik [0.0, 0.1). De tweede emmer bevat getallen in het bereik [0.1, 0.2), enzovoort.

Stap 2) Bereken voor elk element in de array de bucket-index en plaats het element in die bucket.

De bucketindex wordt berekend met de volgende formule:
        bucket_index = aantal_buckets * array_element

Berekening van de bucketindex:
a) 0.78
      bucket_index = aantal_buckets * array_element
              = 10 * 0.78
              = 7.8
Daarom wordt het element 0.78 opgeslagen in bucket[floor(7.8)] of bucket[7].

b) 0.17
      bucket_index = aantal_buckets * array_element
              = 10 * 0.17
              = 1.7

Het array-element 0.17 wordt opgeslagen in bucket[floor(1.7)] of bucket[1].

c) 0.39
      bucket_index = aantal_buckets * array_element
              = 10 * 0.39
              = 3.9
0.39 wordt opgeslagen in bucket[floor(3.9)] of bucket[3].

Na het doorlopen van alle elementen in de array zien de buckets er als volgt uit:

Stap 3) Elke bucket wordt vervolgens gesorteerd met behulp van insertion sort. Na de sorteerbewerking is de uitvoer als volgt:

Stap 4) In de laatste stap worden de buckets samengevoegd tot één enkele array. Deze array is het gesorteerde resultaat van de invoer.

Elke bucket wordt aan de uitvoerarray toegevoegd. Bijvoorbeeld, de toevoeging van de elementen van de tweede bucket:

De samenvoeging van de laatste bucket-elementen wordt hieronder weergegeven:

Na het samenvoegen is de resulterende array de gewenste gesorteerde array.

Emmersorteerprogramma in C/C++

Input:

//Bucket Sort Program in C/C++
//For values without 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: 
";
  for (int i = 0; i< array_size; i++)
    cout<<input[i]<<" ";
  return 0;
}

Output:

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

Emmersorteerprogramma in Python

Input:

# Bucket Sort Program in Python
# For values without 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))

Output:

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

Emmer Sorteer in Java

Input:

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]+" ");
        }
    }
}

Output:

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-sorteeralgoritme voor gehele elementen

Het Bucket Sort-algoritme voor invoer die getallen bevat buiten het bereik [0.0, 1.0] is iets anders dan het vorige. algoritmeDe stappen die in dit geval nodig zijn, zijn als volgt:

Stap 1) Zoek het maximum en het minimum element in de array.

Stap 2) Selecteer het aantal buckets, n, en initialiseer ze als leeg.

Stap 3) Bereken het bereik of de reikwijdte van elke bucket met behulp van de formule:
        span = (maximum - minimum) / n

Stap 4) Voor elk array-element:

• 1. Bereken de bucketindex:
          bucket_index = (element - minimum) / span
• 2. Voeg het element in bucket[bucket_index] in.

Stap 5) Sorteer elke emmer met behulp van invoegsortering.

Stap 6) Voeg alle buckets samen in één array.

Laten we een voorbeeld van dit Bucket Sort-algoritme bekijken. Voor dit voorbeeld sorteren we de volgende array:

Stap 1) In de eerste stap bepalen we het maximum en het minimum van de gegeven array. In dit voorbeeld is het maximum 24 en het minimum 1.

Stap 2) Vervolgens kiezen we het aantal lege emmers, n. In dit voorbeeld gebruiken we 5 emmers en initialiseren we ze als leeg.

Stap 3) De omvang van elke emmer wordt berekend met behulp van de volgende formule:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

De eerste emmer bevat dus getallen tussen [0, 5). De tweede emmer bevat [5, 10), enzovoort.

Stap 4) Bereken voor elk element in de array de bucket-index en plaats het element in die bucket. De bucket-index wordt berekend met de volgende formule:
        bucket_index = (element - minimum) / span

Berekening van de bucketindex:

a) 11
bucket_index = (element – ​​minimum) / span
        = (11 - 1) / 4
        = 2

Element 11 wordt dus opgeslagen in bucket[2].

b) 9
bucket_index = (element – ​​minimum) / span
        = (9 - 1) / 4
        = 2

Let op: Omdat 9 een grenselement is voor bucket[1], wordt het aan bucket[1] toegevoegd in plaats van in dezelfde bucket te worden geplaatst als het vorige element.

Na het uitvoeren van de bewerkingen voor elk element zien de buckets er als volgt uit:

Stap 5) Nu wordt elke bucket gesorteerd met behulp van insertion sort. De buckets na het sorteren:

Stap 6) In de laatste stap worden de buckets samengevoegd tot één enkele array. reeks is het gesorteerde resultaat van de invoer.

Emmersorteerprogramma in C/C++

Input:

#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=0; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

Output:

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

Emmersorteerprogramma in Python

Input:

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:
", input)

Output:

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

Emmer Sorteer in Java

Input:

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 + " ");
        }
    }
}

Output:

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

Voordelen en nadelen van de emmersorteermethode

Complexiteitsanalyse van bucketsortering

Bucket Sorteertijdcomplexiteit

• Beste geval complexiteit: Als alle elementen van de array gelijkmatig verdeeld en vooraf gesorteerd zijn binnen elke bucket, kost het O(n) tijd om de elementen over de corresponderende buckets te verdelen. Vervolgens wordt elke bucket gesorteerd met behulp van invoegsoort De kosten bedragen O(k). De totale complexiteit is dus O(n+k).
• Gemiddelde casuscomplexiteit: In gemiddelde gevallen gaan we ervan uit dat de invoer gelijkmatig verdeeld is. Het Bucket Sort-algoritme bereikt daardoor een lineaire tijdscomplexiteit van O(n+k). Hierbij is O(n) tijd nodig voor het verspreiden van de elementen en O(k) tijd voor het sorteren ervan met behulp van insertion sort.
• Complexiteit in het ergste geval: In het ergste geval zijn de elementen niet gelijkmatig verdeeld en concentreren ze zich in één of twee emmers. In dat geval gedraagt ​​Bucket Sort zich vergelijkbaar met een bubbelsorteeralgoritmeDaarom is de tijdscomplexiteit van Bucket Sort in het slechtste geval O(n²).

Ruimtecomplexiteit van emmersortering

De ruimtecomplexiteit van Bucket Sort is O(n*k). Hierbij is n het aantal elementen en k het aantal emmers dat nodig is om ze tijdens het sorteren op te slaan.

Veelgestelde vragen