Spandsorteringsalgoritme (Java, Python, C/C++ Code Eksempler)

⚡ Smart opsummering

Bucket Sort spreder inputelementer i flere buckets, sorterer hver bucket uafhængigt og samler dem for at producere et endeligt sorteret array.

  • 🪣 Kerneidé: Bucket Sort opdeler værdier på tværs af buckets, sorterer hver enkelt og sammenkæder dem derefter i rækkefølge.
  • 📊 Bedste Fit: Bucket Sort fungerer bedst på jævnt fordelte flydende tal i [0.0, 1.0] eller jævnt fordelte heltal.
  • ⚡ Tidskompleksitet: Gennemsnitlige og bedste tilfælde når O(n+k) lineær tid; værst tænkelige tilfælde degraderes til O(n²).
  • ✅ fordele: Buckets kan behandles parallelt, hvilket er egnet til ekstern sortering af store datasæt.
  • 🧪 Gennemførelse: Code i C, C++, Pythonog Java demonstrerer både flydende komma- og heltalsvarianter.

Hvad er Bucket Sort?

Bucket Sort, ofte kaldet bin sortering, er en sammenligningsbaseret fordelingssorteringsmetode, der accepterer et usorteret array som input og producerer et sorteret array som output. Denne teknik fordeler elementer i flere buckets og sorterer hver bucket individuelt ved hjælp af en anden sorteringsalgoritme, såsom indsættelsessortering. Derefter flettes alle buckets sammen for at danne det endelige sorterede array.

Bucket Sort bruges almindeligvis, når elementerne er:

  1. Flydende komma værdier
  2. Ensartet fordelt over et kendt interval

Tidskompleksiteten af ​​Bucket Sort afhænger af antallet af anvendte buckets og ensartetheden af ​​inputfordelingen. Mens andre sorteringsalgoritmer som f.eks. skal sortere, flette sortering, heapsortering og hurtigsortering For at opnå en best-case tidskompleksitet på O(n*logn), kan Bucket Sort-algoritmen opnå lineær tidskompleksitet O(n) under gunstige forhold.

Bucket Sort følger scatter-gather-metoden. Elementer spredes i tilsvarende buckets, sorteres inde i hver bucket og samles for at danne et sorteret array som det sidste trin. Denne scatter-gather-metode diskuteres i det følgende afsnit.

Scatter-Samle-tilgangen

Store, komplekse problemer kan til tider være udfordrende at løse direkte. Scatter-gather-tilgangen adresserer sådanne problemer ved at opdele hele datasættet i klynger. Hver klynge behandles separat, og resultaterne samles igen for at producere det endelige svar.

Sådan implementerer Bucket Sort-algoritmen scatter-gather-metoden:

Scatter-Samle-tilgangen

Sådan fungerer spandsortering

Det grundlæggende arbejdsprincip for Bucket Sort er som følger:

  1. Der oprettes et sæt tomme buckets. Antallet af buckets kan variere afhængigt af den valgte politik.
  2. Fra input-arrayet placeres hvert element i dets tilsvarende bucket.
  3. Hver bucket sorteres individuelt ved hjælp af en sekundær sorteringsalgoritme.
  4. De sorterede buckets sammenkædes for at producere et enkelt outputmatrix.

Kaldenavn 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: Bucket Sort Algoritme for Floating-Point Numbers

Bucket Sort-algoritmen for flydende tal inden for området [0.0, 1.0]:

Trin 1) Opret ti (10) tomme spande. Den første spand indeholder tal inden for intervallet [0.0, 0.1]. Den anden spand indeholder [0.1, 0.2] og så videre.

Trin 2) For hvert array-element:

  • a. Beregn spandindekset ved hjælp af formlen:
    bucket_index = no_of_buckets * array_element
  • b. Indsæt elementet i bucket[bucket_index]

Trin 3) Sorter hver spand individuelt ved hjælp af indføringssortering.

Trin 4) Saml alle buckets i et enkelt sorteret array.

Lad os gennemgå et eksempel på en bucketsortering. I dette eksempel sorterer vi følgende array:

Spandsorteringsalgoritme for flydende point Numbers

Trin 1) Først opretter vi 10 tomme spande. Den første spand indeholder tal i [0.0, 0.1]. Den anden spand indeholder [0.1, 0.2] og så videre.

Spandsorteringsalgoritme for flydende point Numbers

Trin 2) For hvert array-element skal du beregne bucket-indekset og placere elementet i den pågældende bucket.

Bucket-indekset beregnes ved hjælp af formlen:
        bucket_index = no_of_buckets * array_element

Beregning af spandindeks:
a) 0.78
      bucket_index = no_of_buckets * array_element
              = 10 * 0.78
              = 7.8
Derfor gemmes elementet 0.78 i bucket[floor(7.8)] eller bucket[7].

Spandsorteringsalgoritme for flydende point Numbers

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

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

Spandsorteringsalgoritme for flydende point Numbers

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

Spandsorteringsalgoritme for flydende point Numbers

Efter iterering over alle array-elementer ser buckets ud som følger:

Spandsorteringsalgoritme for flydende point Numbers

Trin 3) Hver bucket sorteres derefter ved hjælp af indsættelsessortering. Efter sorteringsoperationen er outputtet:

Spandsorteringsalgoritme for flydende point Numbers

Trin 4) I det sidste trin sammenkædes buckets til et enkelt array. Dette array er det sorterede resultat af inputtet.

Hver bucket er sammenkædet med outputmatrixen. For eksempel sammenkædelsen af ​​de andre bucket-elementer:

Spandsorteringsalgoritme for flydende point Numbers

Sammenkædningen af ​​de sidste bucket-elementer er vist nedenfor:

Spandsorteringsalgoritme for flydende point Numbers

Efter sammenkædning er det resulterende array det ønskede sorterede array.

Spandsorteringsalgoritme for flydende point Numbers

Skovlsorteringsprogram i 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

Spandsorteringsprogram ind 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]

Spand Sorter i 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

Metode 2: Bucket Sort Algoritme for heltalselementer

Sorteringsalgoritmen for bucket-data, der indeholder tal uden for området [0.0, 1.0], er en smule anderledes end den foregående. algoritmeDe nødvendige trin i denne sag er som følger:

Trin 1) Find det største og mindste antal elementer i arrayet.

Trin 2) Vælg antallet af buckets, n, og initialiser dem som tomme.

Trin 3) Beregn rækkevidden eller spændvidden for hver spand ved hjælp af formlen:
        span = (maximum - minimum) / n

Trin 4) For hvert array-element:

  • 1. Beregn spandindekset:
            bucket_index = (element - minimum) / span
  • 2. Indsæt elementet i bucket[bucket_index]

Trin 5) Sorter hver spand ved hjælp af indføringssortering.

Trin 6) Sammensæt alle spandene i et enkelt array.

Lad os gennemgå et eksempel på denne Bucket Sort-algoritme. I dette eksempel sorterer vi følgende array:

Bucket Sort Algoritme for heltalselementer

Trin 1) I det første trin finder vi det maksimale og minimale antal elementer i det givne array. I dette eksempel er maksimum 24 og minimum 1.

Trin 2) Dernæst vælger vi antallet af tomme buckets, n. I dette eksempel bruger vi 5 buckets og initialiserer dem som tomme.

Trin 3) Spændet for hver spand beregnes ved hjælp af formlen:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Derfor indeholder den første spand tal inden for [0, 5]. Den anden spand indeholder [5, 10], og så videre.

Bucket Sort Algoritme for heltalselementer

Trin 4) For hvert array-element beregnes bucket-indekset, og elementet placeres i den pågældende bucket. Bucket-indekset beregnes ved hjælp af formlen:
        bucket_index = (element - minimum) / span

Beregning af spandindeks:

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

Således er element 11 gemt i bucket[2].

Bucket Sort Algoritme for heltalselementer

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

Bemærk: Da 9 er et grænseelement for bucket[1], tilføjes det til bucket[1] i stedet for at blive placeret i den samme bucket som det foregående element.

Bucket Sort Algoritme for heltalselementer

Efter at have udført operationerne for hvert element, ser buckets ud som følger:

Bucket Sort Algoritme for heltalselementer

Trin 5) Nu sorteres hver spand ved hjælp af indsættelsessortering. Spandene efter sortering:

Bucket Sort Algoritme for heltalselementer

Trin 6) I det sidste trin sammenkædes buckets til et enkelt array. matrix er det sorterede resultat af inputtet.

Bucket Sort Algoritme for heltalselementer

Skovlsorteringsprogram i 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

Spandsorteringsprogram ind 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]

Spand Sorter i 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

Fordele og ulemper ved spandsortering

FORDELE ULEMPER
Udfører hurtigere beregninger på ensartet fordelte data Bruger mere plads sammenlignet med algoritmer til sortering på stedet
Kan bruges som en ekstern sorteringsmetode til store datasæt Yder dårligt, når dataene ikke er ensartet fordelt
Spande kan behandles uafhængigt og parallelt Kræver kendskab til dataområdet og -fordelingen på forhånd

Bucket Sort kompleksitetsanalyse

Sorteringstid for bucket-kompleksitet

  • Bedste sags kompleksitet: Hvis alle array-elementerne er ensartet fordelt og præsorteret inden for hver bucket, kræver det O(n) tid at sprede elementerne i de tilsvarende buckets. Derefter sorteres hver bucket ved hjælp af indsætnings sortering koster O(k). Således er den samlede kompleksitet O(n+k).
  • Gennemsnitlig sagskompleksitet: For gennemsnitlige tilfælde antager vi, at inputtene er ensartet fordelt. Således opnår Bucket Sort-algoritmen en lineær tidskompleksitet på O(n+k). Her kræves O(n) tid til at sprede elementerne og O(k) tid til at sortere dem ved hjælp af indsættelsessortering.
  • Worst Case-kompleksitet: I værste fald er elementerne ikke ensartet fordelt og koncentreres i en eller to spande. I så fald forringes Bucket Sort til en adfærd, der ligner en boblesorteringsalgoritmeDerfor er tidskompleksiteten af ​​Bucket Sort i værste fald O(n²).

Pladskompleksitet af spandsortering

Rumkompleksiteten af ​​Bucket Sort er O(n*k). Her er n antallet af elementer, og k er antallet af buckets, der kræves for at indeholde dem under sortering.

Ofte Stillede Spørgsmål

Brug Bucket Sort, når inputværdier er ensartet fordelt over et kendt område, især flydende tal i [0.0, 1.0]. Den leverer lineær tid på sådanne data, men fungerer dårligt på klyngede eller ukendte fordelinger.

Bucket Sort er stabil, når den indre sorteringsalgoritme, der bruges i hver bucket, er stabil. Indsættelsessortering bevarer den relative rækkefølge af lige elementer, så standard Bucket Sort-implementeringen, der bruger indsættelsessortering, betragtes som stabil.

Bucket Sort grupperer elementer efter værdiinterval og sorterer hver bucket med en anden algoritme. Radix Sort grupperer tal ciffer for ciffer og bruger intern tællesortering. Bucket Sort favoriserer ensartet fordelte flydende tal; Radix Sort favoriserer heltal eller strenge med fast bredde.

Den værst tænkelige tidskompleksitet for Bucket Sort er O(n²). Dette sker, når alle inputelementer falder i en enkelt bucket, hvilket tvinger den indre sortering (typisk indsættelsessortering) til at opføre sig kvadratisk. Ensartet fordeling undgår dette scenarie.

Ja. For at håndtere negative værdier skal du finde både minimum og maksimum, og derefter beregne bucket-indekset ved hjælp af (element – ​​minimum) / span. Dette flytter negative værdier til et ikke-negativt indeksrum og lader standard Bucket Sort-logikken fortsætte uændret.

AI-drevne platforme som VisuAlgo, Algorithm Visualizer og ChatGPT-genererede trinvise instruktioner traces hjælper eleverne med at visualisere Bucket Sort. De animerer scatter-, sorterings- og samlingsfaser, hvilket gør bucketindeksmatematikken og partitioneringslogikken lettere at forstå.

AI-drevne anbefalingssystemer analyserer datasætstørrelse, værdifordeling og hukommelsesgrænser for at foreslå en passende algoritme. For ensartet fordelte flydende tal foretrækker sådanne systemer Bucket Sort. For blandede heltalsområder kan de i stedet foreslå quicksort eller Radix Sort.

Opsummer dette indlæg med: