Algoritme for bøttesortering (Java, Python, C/C++ Code Eksempler)

⚡ Smart oppsummering

Bucket Sort sprer inndataelementer i flere bøtter, sorterer hver bøtte uavhengig og samler dem for å produsere en endelig sortert matrise.

🪣 Kjerneide: Bøttesortering deler verdier på tvers av bøtter, sorterer hver enkelt og setter dem deretter sammen i rekkefølge.
📊 Passer best: Bucket Sort fungerer best på jevnt fordelte flyttall i [0.0, 1.0] eller jevnt fordelte heltall.
⚡ Tidskompleksitet: Gjennomsnittlige og beste tilfeller når O(n+k) lineær tid; verste tilfelle degraderes til O(n²).
✅ Fordeler: Bøtter kan behandles parallelt, egnet for ekstern sortering av store datasett.
🧪 Gjennomføring: Code i C, C++, Pythonog Java demonstrerer både flyttall- og heltallsvarianter.

Les mer

Hva er Bucket Sort?

Bucket Sort, ofte kalt bin-sortering, er en sammenligningsbasert fordelingssorteringsmetode som aksepterer en usortert matrise som input og produserer en sortert matrise som output. Denne teknikken fordeler elementer i flere bøtter og sorterer hver bøtte individuelt ved hjelp av en annen sorteringsalgoritme, for eksempel innsettingssortering. Deretter slås alle bøttene sammen for å danne den endelige sorterte matrisen.

Bøttesortering brukes ofte når elementene er:

Flytende kommaverdier
Jevnt fordelt over et kjent område

Tidskompleksiteten til Bucket Sort avhenger av antall bøtter som brukes og ensartetheten i inputfordelingen. Mens andre sorteringsalgoritmer som skjell sortering, slå sammen sortering, heapsort og Quicksort For å oppnå en best-case tidskompleksitet på O(n*logn), kan Bucket Sort-algoritmen oppnå lineær tidskompleksitet O(n) under gunstige forhold.

Bøttesortering følger scatter-gather-metoden. Elementer spres i tilsvarende bøtter, sorteres inni hver bøtte og samles for å danne en sortert matrise som det siste trinnet. Denne scatter-gather-metoden diskuteres i den følgende delen.

Scatter-Samle-tilnærmingen

Store, komplekse problemer kan av og til være utfordrende å løse direkte. Scatter-gather-tilnærmingen løser slike problemer ved å dele hele datasettet inn i klynger. Hver klynge behandles separat, og resultatene settes sammen igjen for å produsere det endelige svaret.

Slik implementerer Bucket Sort-algoritmen scatter-gather-metoden:

Hvordan bøttesortering fungerer

Det grunnleggende arbeidsprinsippet for Bucket Sort er som følger:

Et sett med tomme bøtter opprettes. Antall bøtter kan variere avhengig av hvilken policy som er valgt.
Fra input-arrayet plasseres hvert element i den tilhørende bøtten.
Hver bøtte sorteres individuelt ved hjelp av en sekundær sorteringsalgoritme.
De sorterte bøttene er sammenkoblet for å produsere én utdatamatrise.

Kallenavn 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

Metode 1: Bøttesorteringsalgoritme for flytende punkt Numbers

Bucket Sort-algoritmen for flyttall innenfor området [0.0, 1.0]:

Trinn 1) Lag ti (10) tomme felt. Den første felten inneholder tall innenfor området [0.0, 0.1]. Den andre felten inneholder [0.1, 0.2], og så videre.

Trinn 2) For hvert array-element:

a. Beregn bøtteindeksen ved hjelp av formelen:
bøtte_indeks = antall_bøtter * array_element
b. Sett inn elementet i bucket[bucket_index]

Trinn 3) Sorter hver bøtte individuelt ved hjelp av innsettingssortering.

Trinn 4) Sammenkoble alle bøtter til én sortert matrise.

La oss gå gjennom et eksempel på en bøttesortering. I dette eksemplet skal vi sortere følgende matrise:

Trinn 1) Først lager vi 10 tomme bøtter. Den første bøtten inneholder tall i [0.0, 0.1]. Den andre bøtten inneholder [0.1, 0.2], og så videre.

Trinn 2) For hvert arrayelement, beregn bøtteindeksen og plasser elementet i den bøtten.

Bøtteindeksen beregnes ved hjelp av formelen:
bøtte_indeks = antall_bøtter * array_element

Beregning av bøtteindeks:
a) 0.78
      bøtte_indeks = antall_bøtter * array_element
              = 10 * 0.78
              = 7.8
Derfor lagres elementet 0.78 i bucket[floor(7.8)] eller bucket[7].

b) 0.17
      bøtte_indeks = antall_bøtter * array_element
              = 10 * 0.17
              = 1.7

Array-elementet 0.17 lagres i bucket[floor(1.7)] eller bucket[1].

0.39
      bøtte_indeks = antall_bøtter * array_element
              = 10 * 0.39
              = 3.9
0.39 lagres i bucket[floor(3.9)] eller bucket[3].

Etter iterering over alle arrayelementene ser bøttene slik ut:

Trinn 3) Hver bøtte sorteres deretter ved hjelp av innsettingssortering. Etter sorteringsoperasjonen er resultatet:

Trinn 4) I det siste trinnet blir bøttene sammenkoblet til én enkelt matrise. Denne matrisen er det sorterte resultatet av inputen.

Hver bøtte er sammenkoblet med utdatamatrisen. For eksempel, sammenkoblingen av de andre bøtteelementene:

Sammenkoblingen av de siste bøtteelementene vises nedenfor:

Etter sammenkobling er den resulterende matrisen den ønskede sorterte matrisen.

Bøttesorteringsprogram i C/C++

Inngang:

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

Utgang:

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

Bøttesorteringsprogram inn Python

Inngang:

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

Utgang:

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

Bøtte Sorter inn Java

Inngang:

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

Utgang:

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

Metode 2: Bucket Sort Algoritme for heltallselementer

Sorteringsalgoritmen for bøtte for input som inneholder tall utenfor området [0.0, 1.0] er litt forskjellig fra den forrige. algoritmeFremgangsmåten som kreves i dette tilfellet er som følger:

Trinn 1) Finn det største og det minste antallet elementer i matrisen.

Trinn 2) Velg antall bøtter, n, og initialiser dem som tomme.

Trinn 3) Beregn rekkevidden eller spennvidden til hver bøtte ved å bruke formelen:
span = (maximum - minimum) / n

Trinn 4) For hvert array-element:

1. Beregn bøtteindeksen:
bucket_index = (element - minimum) / span
2. Sett inn elementet i bucket[bucket_index]

Trinn 5) Sorter hver bøtte ved hjelp av innsettingssortering.

Trinn 6) Sett sammen alle bøttene i en enkelt matrise.

La oss gå gjennom et eksempel på denne Bucket Sort-algoritmen. I dette eksemplet skal vi sortere følgende matrise:

Trinn 1) I det første trinnet finner vi maksimums- og minimumselementene i den gitte tabellen. For dette eksempelet er maksimumstallet 24 og minimumstallet 1.

Trinn 2) Deretter velger vi antall tomme bøtter, n. I dette eksemplet bruker vi 5 bøtter og initialiserer dem som tomme.

Trinn 3) Spennvidden til hver bøtte beregnes ved hjelp av formelen:
span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Derfor inneholder den første bøtta tall innenfor [0, 5]. Den andre bøtta inneholder [5, 10], og så videre.

Trinn 4) For hvert arrayelement beregner du bøtteindeksen og plasserer elementet i den bøtten. Bøtteindeksen beregnes ved hjelp av formelen:
bucket_index = (element - minimum) / span

Beregning av bøtteindeks:

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

Dermed lagres element 11 i bøtte[2].

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

OBS: Siden 9 er et grenseelement for bucket[1], legges det til bucket[1] i stedet for å plasseres i samme bucket som det forrige elementet.

Etter at operasjonene for hvert element er utført, ser bøttene slik ut:

Trinn 5) Nå sorteres hver bøtte ved hjelp av innsettingssortering. Bøttene etter sortering:

Trinn 6) I det siste trinnet blir bøttene sammenkoblet til én enkelt matrise. matrise er det sorterte resultatet av inputen.

Bøttesorteringsprogram i C/C++

Inngang:

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

Utgang:

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

Bøttesorteringsprogram inn Python

Inngang:

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)

Utgang:

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

Bøtte Sorter inn Java

Inngang:

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

Utgang:

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

Fordeler og ulemper med bøttesortering

Pros	Ulemper
Utfører raskere beregninger på jevnt fordelte data	Bruker mer plass sammenlignet med sorteringsalgoritmer på stedet
Kan brukes som en ekstern sorteringsmetode for store datasett	Yter dårlig når dataene ikke er jevnt fordelt
Bøtter kan behandles uavhengig og parallelt	Krever kunnskap om dataområdet og distribusjonen på forhånd

Bøttesortering kompleksitetsanalyse

Kompleksitet for sortering av bøtte

Beste sakskompleksitet: Hvis alle elementene i matrisen er jevnt fordelt og forhåndssortert innenfor hver bøtte, krever det O(n) tid å spre elementene i de tilsvarende bøttene. Deretter sorteres hver bøtte ved hjelp av innsettings sortering koster O(k). Dermed er den totale kompleksiteten O(n+k).
Gjennomsnittlig sakskompleksitet: For gjennomsnittlige tilfeller antar vi at inngangene er jevnt fordelt. Dermed oppnår Bucket Sort-algoritmen en lineær tidskompleksitet på O(n+k). Her kreves O(n) tid for å spre elementene og O(k) tid for å sortere dem ved hjelp av innsettingssortering.
Worst Case Complexity: I verste fall er ikke elementene jevnt fordelt og konsentreres i én eller to bøtter. I så fall degraderes bøttesorteringen til en oppførsel som ligner på en boblesorteringsalgoritmeDerfor er tidskompleksiteten til Bucket Sort i verste fall O(n²).

Plasskompleksiteten til bøttesortering

Romkompleksiteten til Bucket Sort er O(n*k). Her er n antall elementer og k er antall bøtter som kreves for å holde dem under sortering.

Spørsmål og svar

Bruk Bucket Sort når inngangsverdier er jevnt fordelt over et kjent område, spesielt flyttall i [0.0, 1.0]. Den gir lineær tid på slike data, men fungerer dårlig på klyngede eller ukjente fordelinger.

Bucket Sort er stabil når den indre sorteringsalgoritmen som brukes i hver bøtte er stabil. Innsettingssortering bevarer den relative rekkefølgen av like elementer, så standard Bucket Sort-implementering som bruker innsettingssortering anses som stabil.

Bucket Sort grupperer elementer etter verdiområde og sorterer hver bøtte med en annen algoritme. Radix Sort grupperer tall siffer for siffer og bruker tellende sortering internt. Bucket Sort favoriserer jevnt fordelte flyttall; Radix Sort favoriserer heltall eller strenger med fast bredde.

Den verst tenkelige tidskompleksiteten til Bucket Sort er O(n²). Dette skjer når alle inputelementer faller inn i en enkelt bøtte, noe som tvinger den indre sorteringen (vanligvis innsettingssortering) til å oppføre seg kvadratisk. Jevn fordeling unngår dette scenariet.

Ja. For å håndtere negative verdier, finn både minimum og maksimum, og beregn deretter bøtteindeksen ved hjelp av (element – minimum) / span. Dette flytter negative verdier til et ikke-negativt indeksrom og lar standard bøttesorteringslogikk fortsette uendret.

AI-drevne plattformer som VisuAlgo, Algorithm Visualizer og ChatGPT-genererte trinnvise instruksjoner trachjelper elevene med å visualisere bøttesortering. De animerer sprednings-, sorterings- og samlingsfaser, noe som gjør bøtteindeksmatematikken og partisjoneringslogikken enklere å forstå.

AI-drevne anbefalingssystemer analyserer datasettstørrelse, verdifordeling og minnegrenser for å foreslå en passende algoritme. For jevnt fordelte flyttall favoriserer slike systemer Bucket Sort. For blandede heltallsområder kan de i stedet foreslå quicksort eller Radix Sort.

Algoritme for bøttesortering (Java, Python, C/C++ Code Eksempler)

Hva er Bucket Sort?

Scatter-Samle-tilnærmingen

Hvordan bøttesortering fungerer

Kallenavn Code

Metode 1: Bøttesorteringsalgoritme for flytende punkt Numbers

Bøttesorteringsprogram i C/C++

Bøttesorteringsprogram inn Python

Bøtte Sorter inn Java

Metode 2: Bucket Sort Algoritme for heltallselementer

Bøttesorteringsprogram i C/C++

Bøttesorteringsprogram inn Python

Bøtte Sorter inn Java

Fordeler og ulemper med bøttesortering

Bøttesortering kompleksitetsanalyse

Kompleksitet for sortering av bøtte

Plasskompleksiteten til bøttesortering

Spørsmål og svar

Oppsummer dette innlegget med:

Registrer deg for nyhetsbrevet

Hva er Bucket Sort?

Scatter-Samle-tilnærmingen

Hvordan bøttesortering fungerer

Kallenavn Code

Metode 1: Bøttesorteringsalgoritme for flytende punkt Numbers

RELATERTE ARTIKLER

Bøttesorteringsprogram i C/C++

Bøttesorteringsprogram inn Python

Bøtte Sorter inn Java

Metode 2: Bucket Sort Algoritme for heltallselementer

Bøttesorteringsprogram i C/C++

Bøttesorteringsprogram inn Python

Bøtte Sorter inn Java

Fordeler og ulemper med bøttesortering

Bøttesortering kompleksitetsanalyse

Kompleksitet for sortering av bøtte

Plasskompleksiteten til bøttesortering

Spørsmål og svar

Oppsummer dette innlegget med:

Registrer deg for nyhetsbrevet