Bucket Sort Algorithm (Java, Python, C/C++ Code Exempel)

⚡ Smart sammanfattning

Bucket Sort sprider indataelement i flera buckets, sorterar varje bucket oberoende och samlar dem för att producera en slutlig sorterad array.

🪣 Kärnidé: Bucket Sort delar upp värden över hinkar, sorterar varje och sammanfogar dem sedan i ordning.
📊 Bästa passform: Bucket Sort fungerar bäst på jämnt fördelade flyttal i [0.0, 1.0] eller jämnt spridda heltal.
⚡ Tidskomplexitet: Genomsnittliga och bästa fall når O(n+k) linjär tid; värsta fall degraderas till O(n²).
✅ fördelar: Buckets kan bearbetas parallellt, lämpligt för extern sortering av stora datamängder.
🧪 Genomförande: Code i C, C++, Pythonoch Java demonstrerar både flyttal och heltalsvarianter.

Läs mer

Vad är Bucket Sort?

Bucket Sort, ofta kallad bin-sortering, är en jämförelsebaserad sorteringsmetod som accepterar en osorterad array som indata och producerar en sorterad array som utdata. Denna teknik distribuerar element i flera hinkar och sorterar varje hink individuellt med hjälp av en annan sorteringsalgoritm, såsom insättningssortering. Sedan slås alla hinkar samman för att bilda den slutliga sorterade arrayen.

Bucket Sort används vanligtvis när elementen är:

Flyttalsvärden
Likformigt fördelad över ett känt område

Tidskomplexiteten för Bucket Sort beror på antalet skopor som används och enhetligheten i inmatningsfördelningen. Medan andra sorteringsalgoritmer som t.ex. skal sortera, slå samman sortering, heapsortera och quick uppnå en bästa möjliga tidskomplexitet på O(n*logn), kan Bucket Sort-algoritmen uppnå linjär tidskomplexitet O(n) under gynnsamma förhållanden.

Bucket Sort följer scatter-gather-metoden. Element sprids i motsvarande hinkar, sorteras inuti varje hink och samlas ihop för att bilda en sorterad array som det sista steget. Denna scatter-gather-metod diskuteras i följande avsnitt.

Scatter-Samle-metoden

Storskaliga, komplexa problem kan ibland vara utmanande att lösa direkt. Scatter-gather-metoden åtgärdar sådana problem genom att dela upp hela datamängden i kluster. Varje kluster bearbetas separat och resultaten sammanförs för att producera det slutliga svaret.

Så här implementerar Bucket Sort-algoritmen scatter-gather-metoden:

Hur hinksortering fungerar

Den grundläggande arbetsprincipen för Bucket Sort är följande:

En uppsättning tomma hinkar skapas. Antalet hinkar kan variera beroende på vilken policy som valts.
Från inmatningsarrayen placeras varje element i motsvarande bucket.
Varje hink sorteras individuellt med hjälp av en sekundär sorteringsalgoritm.
De sorterade buckets sammanfogas för att producera en enda utdatamatris.

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

Metod 1: Skopsorteringsalgoritm för flytande punkt Numbers

Bucket Sort-algoritmen för flyttal inom intervallet [0.0, 1.0]:

Steg 1) Skapa tio (10) tomma hinkar. Den första hinken innehåller tal inom intervallet [0.0, 0.1]. Den andra hinken innehåller [0.1, 0.2] och så vidare.

Steg 2) För varje arrayelement:

a. Beräkna hinkens index med hjälp av formeln:
bucket_index = no_of_buckets * array_element
b. Infoga elementet i bucket[bucket_index]

Steg 3) Sortera varje hink individuellt med hjälp av instickssortering.

Steg 4) Sammanfoga alla buckets till en enda sorterad array.

Låt oss gå igenom ett exempel på en Bucket Sort-funktion. I det här exemplet sorterar vi följande array:

Steg 1) Först skapar vi 10 tomma hinkar. Den första hinken innehåller tal i [0.0, 0.1]. Den andra hinken innehåller [0.1, 0.2], och så vidare.

Steg 2) För varje arrayelement, beräkna bucketindexet och placera elementet i den bucketen.

Bucketindexet beräknas med hjälp av formeln:
bucket_index = no_of_buckets * array_element

Beräkning av hinkindex:
a) 0.78
      bucket_index = no_of_buckets * array_element
              = 10 * 0.78
              = 7.8
Därför lagras elementet 0.78 i bucket[floor(7.8)] eller bucket[7].

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

Arrayelementet 0.17 lagras i bucket[floor(1.7)] eller bucket[1].

c) 0.39
      bucket_index = no_of_buckets * array_element
              = 10 * 0.39
              = 3.9
0.39 lagras i bucket[floor(3.9)] eller bucket[3].

Efter iterering över alla arrayelement ser buckets ut enligt följande:

Steg 3) Varje hink sorteras sedan med hjälp av insättningssortering. Efter sorteringsoperationen är utdata:

Steg 4) I det sista steget sammanfogas buckets till en enda array. Den arrayen är det sorterade resultatet av indata.

Varje bucket är sammanlänkad med utdatamatrisen. Till exempel, sammanlänkning av de andra bucketelementen:

Sammanfogningen av de sista bucket-elementen visas nedan:

Efter sammankoppling är den resulterande arrayen den önskade sorterade arrayen.

Skopsorteringsprogram i C/C++

Ingång:

//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;
}

Produktion:

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

Hinksorteringsprogram in Python

Ingång:

# 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))

Produktion:

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

Hink Sortera in Java

Ingång:

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

Produktion:

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

Metod 2: Bucket Sort Algoritm för heltalselement

Sorteringsalgoritmen Bucket för indata som innehåller tal utanför intervallet [0.0, 1.0] skiljer sig något från den föregående. algoritmStegen som krävs i det här fallet är följande:

Steg 1) Hitta det största och minsta antalet element i arrayen.

Steg 2) Välj antalet hinkar, n, och initiera dem som tomma.

Steg 3) Beräkna intervallet eller spännvidden för varje hink med hjälp av formeln:
span = (maximum - minimum) / n

Steg 4) För varje arrayelement:

1. Beräkna skopindex:
bucket_index = (element - minimum) / span
2. Infoga elementet i bucket[bucket_index]

Steg 5) Sortera varje hink med hjälp av insättningssortering.

Steg 6) Sammanfoga alla hinkar till en enda array.

Låt oss gå igenom ett exempel på denna Bucket Sort-algoritm. I det här exemplet sorterar vi följande array:

Steg 1) I det första steget hittar vi det maximala och minimala antalet element i den givna arrayen. I det här exemplet är det maximala antalet 24 och det minimala antalet 1.

Steg 2) Därefter väljer vi antalet tomma hinkar, n. I det här exemplet använder vi 5 hinkar och initierar dem som tomma.

Steg 3) Spännvidden för varje skopa beräknas med hjälp av formeln:
span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Därför innehåller den första hinken tal inom [0, 5]. Den andra hinken innehåller [5, 10), och så vidare.

Steg 4) För varje element i arrayen, beräkna bucketindexet och placera elementet i den bucketen. Bucketindexet beräknas med hjälp av formeln:
bucket_index = (element - minimum) / span

Beräkning av hinkindex:

a) 11
bucket_index = (element – minimum) / spann
= (11 – 1) / 4
= 2

Således lagras element 11 i hinken[2].

b) 9
bucket_index = (element – minimum) / spann
= (9 – 1) / 4
= 2

Obs: Eftersom 9 är ett gränselement för bucket[1] läggs det till i bucket[1] istället för att placeras i samma bucket som föregående element.

Efter att operationerna för varje element har utförts ser buckets ut enligt följande:

Steg 5) Nu sorteras varje hink med hjälp av insättningssortering. Hinkarna efter sortering:

Steg 6) I det sista steget sammanfogas buckets till en enda array. array är det sorterade resultatet av inmatningen.

Skopsorteringsprogram i C/C++

Ingång:

#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;
}

Produktion:

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

Hinksorteringsprogram in Python

Ingång:

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)

Produktion:

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

Hink Sortera in Java

Ingång:

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

Produktion:

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

För- och nackdelar med hinksortering

Fördelar	Nackdelar
Utför snabbare beräkningar på jämnt fördelade data	Förbrukar mer utrymme jämfört med sorteringsalgoritmer på plats
Kan användas som en extern sorteringsmetod för stora datamängder	Presterar dåligt när data inte är jämnt fördelad
Skopor kan bearbetas oberoende och parallellt	Kräver kunskap om dataintervall och distribution i förväg

Skopsorteringskomplexitetsanalys

Komplexitet för sortering av hink, tid

Best Case-komplexitet: Om alla element i arrayen är jämnt fördelade och försorterade inom varje bucket, krävs det O(n) tid för att sprida elementen i motsvarande buckets. Sortera sedan varje bucket med hjälp av insättningssortering kostar O(k). Således är den totala komplexiteten O(n+k).
Genomsnittlig ärendekomplexitet: För genomsnittliga fall antar vi att ingångarna är jämnt fördelade. Således uppnår Bucket Sort-algoritmen en linjär tidskomplexitet på O(n+k). Här krävs O(n) tid för att sprida elementen och O(k) tid för att sortera dem med hjälp av insättningssortering.
Worst Case Complexity: I värsta fall är elementen inte jämnt fördelade och koncentreras i en eller två hinkar. I så fall försämras Bucket Sort till ett beteende som liknar en bubbelsorteringsalgoritmDärför är tidskomplexiteten för Bucket Sort i värsta fall O(n²).

Utrymmeskomplexitet för hinksortering

Rumskomplexiteten för Bucket Sort är O(n*k). Här är n antalet element och k är antalet hinkar som krävs för att hålla dem under sorteringen.

Vanliga frågor

Använd Bucket Sort när indatavärden är jämnt fördelade över ett känt område, särskilt flyttal i [0.0, 1.0]. Den ger linjär tid på sådan data men presterar dåligt på klustrade eller okända fördelningar.

Bucket Sort är stabil när den inre sorteringsalgoritmen som används inuti varje bucket är stabil. Insertion sort bevarar den relativa ordningen av lika element, så standard Bucket Sort-implementeringen som använder insertion sort anses stabil.

Bucket Sort grupperar element efter värdeintervall och sorterar varje bucket med en annan algoritm. Radix Sort grupperar tal siffra för siffra och använder räknesortering internt. Bucket Sort gynnar jämnt fördelade flyttal; Radix Sort gynnar heltal eller strängar med fast bredd.

Den värsta tänkbara tidskomplexiteten för Bucket Sort är O(n²). Detta inträffar när alla inmatningselement faller in i en enda bucket, vilket tvingar den inre sorteringen (vanligtvis insättningssortering) att bete sig kvadratiskt. En enhetlig fördelning undviker detta scenario.

Ja. För att hantera negativa värden, hitta både minimum och maximum, beräkna sedan bucketindex med hjälp av (element – minimum) / span. Detta flyttar negativa värden till ett icke-negativt indexutrymme och låter standardlogiken för Bucket Sort fortsätta oförändrad.

AI-drivna plattformar som VisuAlgo, Algorithm Visualizer och ChatGPT-genererade steg-för-steg-guider trachjälper eleverna att visualisera Bucket Sort. De animerar spridnings-, sorterings- och insamlingsfaser, vilket gör matematiken kring bucketindex och partitioneringslogik lättare att förstå.

AI-drivna rekommendatorer analyserar datamängdernas storlek, värdefördelning och minnesgränser för att föreslå en passande algoritm. För enhetligt fördelade flyttal föredrar sådana system Bucket Sort. För blandade heltalsområden kan de istället föreslå quicksort eller Radix Sort.

Bucket Sort Algorithm (Java, Python, C/C++ Code Exempel)

Vad är Bucket Sort?

Scatter-Samle-metoden

Hur hinksortering fungerar

Pseudo Code

Metod 1: Skopsorteringsalgoritm för flytande punkt Numbers

Skopsorteringsprogram i C/C++

Hinksorteringsprogram in Python

Hink Sortera in Java

Metod 2: Bucket Sort Algoritm för heltalselement

Skopsorteringsprogram i C/C++

Hinksorteringsprogram in Python

Hink Sortera in Java

För- och nackdelar med hinksortering

Skopsorteringskomplexitetsanalys

Komplexitet för sortering av hink, tid

Utrymmeskomplexitet för hinksortering

Vanliga frågor

Sammanfatta detta inlägg med:

Anmäl dig till nyhetsbrevet