Spandsorteringsalgoritme (Java, Python, C/C++ Kodeeksempler)
Sarah Chen
Hvad er Bucket Sort?
Bucket sort, ofte kaldet bin sort, er en sammenligningssorteringsmetode, der accepterer et usorteret array som input og producerer et sorteret array som et resultat. Denne metode fungerer ved at fordele elementerne i flere buckets og sortere hver af disse buckets individuelt ved en hvilken som helst sorteringsalgoritme såsom indsættelsessortering. Derefter flettes alle spandene sammen for at danne et sorteret array.
Spandsortering bruges almindeligvis, når elementerne er-
- Flydende komma værdier
- Ensartet fordelt over et område
Spandsorteringens tidskompleksitet afhænger af antallet af brugte spande og ensartetheden af inputfordelingen. Mens forskellige sorteringsalgoritmer som f.eks skal sortere, flette sortering, heapsortering og hurtigsortering kan opnå den bedst mulige tidskompleksitet af O(n*logn), kan spandsorteringsalgoritmen opnå det samme i lineær tidskompleksitet eller O(n).
Bucket sortering følger scatter-samler tilgangen. Ved at anvende denne tilgang spredes elementer i de tilsvarende spande, sorteres i spandene og samles for at danne et sorteret array som det sidste trin. Denne scatter-samler tilgang diskuteres i det følgende afsnit
Scatter-Gather-Approach
Store, komplekse problemer kan nogle gange være udfordrende at løse. Scatter-gather-tilgangen forsøger at løse sådanne problemer ved at opdele hele datasættet i klynger. Derefter adresseres hver klynge separat og bringes alt sammen igen for at få det endelige svar.
Sådan implementerer spandsorteringsalgoritmen scatter-gather-metoden:
Sådan fungerer spandsortering
Det grundlæggende arbejdsprincip for skovlsortering er som følger:
- Et sæt tomme spande oprettes. Baseret på forskellige politikker kan antallet af spande variere.
- Fra input-arrayet skal du lægge hvert element i dets tilsvarende spand.
- Sorter disse spande individuelt.
- Sammensæt de sorterede buckets for at skabe et enkelt output-array.
De detaljerede arbejdstrin findes i de følgende afsnit.
Pseudokode
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
Spandsorteringsalgoritmen for flydende kommatal inden for området fra 0.0 til 1.0:
Trin 1) Opret ti(10) tomme buckets, således at den første bucket vil indeholde tal inden for området [0.0, 0.1). Så vil den anden spand indeholde inden for [0.1, 0.2) og så videre.
Trin 2) For hvert array-element:
-
en. Beregn spandindeks ved hjælp af formlen:
bucket index= no_of_buckets *array_element
-
b. Indsæt elementet i spanden[bucket_index]
Trin 3) Sorter hver spand individuelt ved hjælp af indføringssortering.
Trin 4) Sammensæt alle spande i et enkelt array.
Lad os se et eksempel på spandsortering. I dette eksempel vil vi sortere følgende array ved hjælp af bucket sort algoritmen-
Trin 1) Først vil vi oprette 10 tomme spande. Den første bøtte vil indeholde tallene mellem [0.0, 0.1). Så vil den anden bøtte indeholde tallene mellem [0.1, 0.2) og så videre.
Trin 2) For hvert array-element vil vi beregne bucket-indekset og placere elementet i den bucket.
Spandindekset kan 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 vil elementet 0.78 blive opbevaret på spanden[gulv(7.8)] eller spanden[7].
b) 0.17
bucket_index = no_of_buckets * array-element
= 10 * 0.17
= 1.7
Array-elementet 0.17 vil blive opbevaret på spand[gulv(1.7)] eller spand[1].
c) 0.39
bucket_index = no_of_buckets * array-element
= 10 * 0.39
= 3.9
0.39 vil blive opbevaret på spand[gulv(3.9)] eller spand[3].
Efter iteration over alle array-elementer vil buckets være følgende:
Trin 3) Derefter vil hver spand blive sorteret ved hjælp af indsættelsessortering. Efter sorteringsoperationen ville outputtet være:
Trin 4) I det sidste trin vil spandene blive sammenkædet i et enkelt array. Denne matrix vil være det sorterede resultat af inputtet.
Hver bucket vil blive sammenkædet med output-arrayet. For eksempel - sammenkædningen af de andre skovlelementer:
Sammenkædningen af de sidste skovlelementer vil være følgende:
Efter sammenkædning vil det resulterende array være det ønskede sorterede array.
Skovlsorteringsprogram i C/C++
Input:
//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;
}
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 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))
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
Spandsorteringsalgoritmen for input, der indeholder tal uden for området [0.0, 1.0] er en smule anderledes end den forrige algoritme. De nødvendige trin i denne sag er som følger-
Trin 1) Find maksimum og minimum elementer.
Trin 2) Vælg antallet af buckets, n, og initialiser disse buckets 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 bucket index:
bucket_index = (element - minimum)/span-
2. Indsæt elementet i spand[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 se et eksempel på denne spandsorteringsalgoritme. I dette eksempel vil vi sortere følgende array ved hjælp af bucket sort algoritmen-
Trin 1) I det første trin skal maksimum- og minimumselementerne i det givne array findes. I dette eksempel er maksimum 24, og minimum er 1.
Trin 2) Nu skal vi vælge et antal tomme spande, n. I dette eksempel tager vi 5 spande. Så vil vi initialisere dem som tomme.
Trin 3) Spændvidden af hver spand skal beregnes ved hjælp af følgende formel:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Derfor vil den første bøtte indeholde tallene inden for området [0, 5). Den anden bøtte vil indeholde tallene inden for [5, 10) og så videre.
Trin 4) For hvert array-element vil vi beregne bucket-indekset og placere elementet i den bucket. Spandindekset kan beregnes ved hjælp af formlen:
bucket_index = (element - minimum)/span
Beregning af spandindeks:
-
a) 11bucket_index = (element – minimum)/span
=(11-1)/4
=2
Således vil element 11 blive opbevaret i spand[2].
-
b) 9
bucket_index = (element – minimum)/span
=(9-1)/4
=2
Bemærk: Da 9 er et grænseelement for spanden[1], skal det tilføjes i spanden[1] i stedet for at tilføjes i samme spand som det forrige element.
Efter at have udført operationerne for hvert element, vil spandene være som følger:
Trin 5) Nu vil hver spand blive sorteret ved hjælp af indsættelsessortering. Spandene efter sortering-
Trin 6) I det sidste trin vil spandene blive sammenkædet i et enkelt array. At matrix vil være det sorterede resultat af input.
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; 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:\n", 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
Pros og Cons
| FORDELE | ULEMPER |
|---|---|
| Udfør hurtigere beregning | Bruger mere plads sammenlignet med andre algoritmer |
| Den kan bruges som ekstern sorteringsmetode | Yder dårligt, når dataene ikke er ensartet fordelt |
| Bøtter kan behandles uafhængigt |
Bucket Sort kompleksitetsanalyse
Bucket Sorts tidskompleksitet
- Bedste sags kompleksitet:Hvis alle array-elementerne er ensartet fordelt og sorteret på forhånd, ville det kræve O(n) tid at sprede elementerne i de tilsvarende spande. Derefter sorteres hver spand vha indsætnings sortering ville koste O(k). Den samlede kompleksitet ville således være O(n+k).
- Gennemsnitlig sagskompleksitet:For gennemsnitlige tilfælde antager vi, at inputs er ensartet fordelt. Skovlsorteringsalgoritmen opnår således en lineær tidskompleksitet på O(n+k). Her kræves O(n) tid til at sprede elementerne, og O(k) tid kræves til sortering af disse elementer ved hjælp af indsættelsessortering.
- Worst Case-kompleksitet:I værste fald vil elementerne ikke være ensartet fordelt og koncentreret over en eller to specifikke spande. I så fald vil spandsortering fungere som en boblesorteringsalgoritme. Derfor vil tidskompleksiteten af en spandsortering i værste tilfælde være O(n^2).
Pladskompleksitet af spandsortering
Bucketsortens pladskompleksitet er O(n*k). Her er n antallet af elementer, og k er antallet af krævede spande.
