Bucket Sort Algorithm (Java, Python, C/C++ Kodexempel)
Sarah Chen
Vad är Bucket Sort?
Skogsortering, ofta kallad lagersortering, är en jämförelsesorteringsmetod som accepterar en osorterad matris som en indata och producerar en sorterad matris som ett resultat. Den här metoden fungerar genom att dela upp elementen i flera hinkar och sortera var och en av dessa hinkar individuellt med valfri sorteringsalgoritm, såsom infogningssortering. Sedan slås alla hinkar samman för att bilda en sorterad array.
Skopsortering används vanligtvis när elementen är-
- Flyttalsvärden
- Jämnt fördelad över ett intervall
Skopsorteringens tidskomplexitet beror på antalet använda hinkar och enhetligheten i inmatningsfördelningen. Medan olika sorteringsalgoritmer som t.ex skal sortera, slå samman sortering, heapsortera och quick kan uppnå bästa möjliga tidskomplexitet för O(n*logn), kan skopsorteringsalgoritmen uppnå samma i linjär tidskomplexitet eller O(n).
Hinksortering följer scatter-gather-metoden. Genom att tillämpa detta tillvägagångssätt sprids elementen i motsvarande hinkar, sorteras i hinkarna och samlas för att bilda en sorterad array som det sista steget. Denna scatter-insamlingsmetod diskuteras i följande avsnitt
Scatter-Gather-Approach
Storskaliga, komplexa problem kan ibland vara utmanande att lösa. Scatter-gather-metoden försöker lösa sådana problem genom att dela upp hela datamängden i kluster. Sedan adresseras varje kluster separat och sammanförs allt för att få det slutgiltiga svaret.
Så här implementerar bucketsorteringsalgoritmen scatter-gather-metoden:
Hur hinksortering fungerar
Den grundläggande arbetsprincipen för skopsortering är följande:
- En uppsättning tomma hinkar skapas. Baserat på olika policyer kan antalet hinkar variera.
- Från inmatningsmatrisen lägger du varje element i dess motsvarande hink.
- Sortera hinkarna individuellt.
- Sammanfoga de sorterade hinkarna för att skapa en enda utmatningsmatris.
De detaljerade arbetsstegen finns i följande avsnitt.
Pseudokod
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
Skoksorteringsalgoritmen för flyttalsnummer inom intervallet 0.0 till 1.0:
Steg 1) Skapa tio(10) tomma hinkar så att den första hinken kommer att innehålla siffror inom intervallet [0.0, 0.1). Sedan kommer den andra hinken att innehålla inom [0.1, 0.2) och så vidare.
Steg 2) För varje arrayelement:
-
a. Beräkna hinkindex med formeln:
bucket index= no_of_buckets *array_element
-
b. Sätt in elementet i hinken[bucket_index]
Steg 3) Sortera varje hink individuellt med hjälp av instickssortering.
Steg 4) Sammanfoga alla hinkar till en enda array.
Låt oss se ett exempel på en hinksortering. För det här exemplet kommer vi att sortera följande array med hjälp av hinksorteringsalgoritmen-
Steg 1) Först skapar vi 10 tomma hinkar. Den första hinken kommer att innehålla siffrorna mellan [0.0, 0.1). Sedan kommer den andra hinken att innehålla siffrorna mellan [0.1, 0.2) och så vidare.
Steg 2) För varje matriselement kommer vi att beräkna hinkindexet och placera elementet i den hinken.
Hinkindexet kan beräknas med 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 kommer elementet 0.78 att lagras på hinken[golv(7.8)] eller hinken[7].
b) 0.17
bucket_index = no_of_buckets * matriselement
= 10 * 0.17
= 1.7
Arrayelementet 0.17 kommer att lagras på hink[golv(1.7)] eller hink[1].
c) 0.39
bucket_index = no_of_buckets * matriselement
= 10*0.39
= 3.9
0.39 kommer att lagras på hink[golv(3.9)] eller hink[3].
Efter att ha itererat över alla arrayelement kommer hinkarna att vara följande:
Steg 3) Sedan kommer varje hink att sorteras med hjälp av insättningssortering. Efter sorteringsoperationen skulle resultatet bli:
Steg 4) I det sista steget kommer hinkarna att sammanfogas till en enda array. Den matrisen kommer att vara det sorterade resultatet av inmatningen.
Varje hink kommer att kopplas samman till utmatningsmatrisen. Till exempel - sammanlänkningen av de andra hinkelementen:
Sammansättningen av de sista hinkelementen kommer att vara följande:
Efter sammanfogning kommer den resulterande arrayen att vara den önskade sorterade arrayen.
Skopsorteringsprogram i C/C++
Ingång:
//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;
}
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 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))
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
Bucketsorteringsalgoritmen för indata som innehåller siffror utanför intervallet [0.0, 1.0] är lite annorlunda än den föregående algoritm. De steg som krävs för detta fall är följande-
Steg 1) Hitta de högsta och lägsta elementen.
Steg 2) Välj antalet hinkar, n, och initiera dessa hinkar 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 hinkindex:
bucket_index = (element - minimum)/span-
2.Sätt in elementet i hink[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 se ett exempel på denna hinksortering. För det här exemplet kommer vi att sortera följande array med hjälp av hinksorteringsalgoritmen-
Steg 1) I det första steget måste maximi- och minimumelementen för den givna arrayen hittas. I det här exemplet är maxvärdet 24 och minimum 1.
Steg 2) Nu måste vi välja ett antal tomma hinkar, n. I det här exemplet tar vi 5 hinkar. Sedan initierar vi dem som tomma.
Steg 3) Spännvidden för varje hink måste beräknas med följande formel:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Därför kommer den första hinken att innehålla siffrorna inom intervallet [0, 5). Den andra hinken kommer att innehålla siffrorna inom [5, 10) och så vidare.
Steg 4) För varje matriselement kommer vi att beräkna hinkindexet och placera elementet i den hinken. Hinkindexet kan beräknas med formeln:
bucket_index = (element - minimum)/span
Beräkning av hinkindex:
-
a) 11bucket_index = (element – minimum)/span
=(11-1)/4
=2
Således kommer element 11 att lagras i hink[2].
-
b) 9
bucket_index = (element – minimum)/span
=(9-1)/4
=2
Obs: Eftersom 9 är ett gränselement för hinken[1], måste den läggas till i hinken[1] istället för att läggas till i samma hink som föregående element.
Efter att ha utfört operationerna för varje element kommer hinkarna att se ut som följer:
Steg 5) Nu kommer varje hink att sorteras med hjälp av insättningssortering. Hinkarna efter sortering-
Steg 6) I det sista steget kommer hinkarna att sammanfogas till en enda array. Den där array kommer att vara 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; 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:\n", 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ördelar nackdelar
| Fördelar | Nackdelar |
|---|---|
| Utför snabbare beräkningar | Tar mer utrymme jämfört med andra algoritmer |
| Den kan användas som en extern sorteringsmetod | Presterar dåligt när data inte är jämnt fördelad |
| Skopor kan bearbetas oberoende |
Skopsorteringskomplexitetsanalys
Bucket Sorts tidskomplexitet
- Best Case-komplexitet:Om alla arrayelementen är jämnt fördelade och sorterade i förväg, skulle det kräva O(n) tid för att sprida elementen i motsvarande hinkar. Sortera sedan varje hink med hjälp av insättningssortering skulle kosta O(k). Sålunda skulle den totala komplexiteten vara O(n+k).
- Genomsnittlig ärendekomplexitet:För genomsnittliga fall antar vi att indata är likformigt fördelade. Sålunda uppnår skopsorteringsalgoritmen linjär tidskomplexitet O(n+k). Här krävs O(n)-tid för att sprida elementen och O(k)-tid krävs för att sortera dessa element med hjälp av infogningssortering.
- Worst Case Complexity:I värsta fall kommer elementen inte att vara jämnt fördelade och koncentrerade över en eller två specifika hinkar. I så fall kommer hinksortering att fungera som en bubbelsorteringsalgoritm. Därför skulle tidskomplexiteten för en hinksortering i värsta fall vara O(n^2).
Utrymmeskomplexitet för hinksortering
Skoksortens rymdkomplexitet är O(n*k). Här är n antalet element och k är antalet hinkar som krävs.