Vödör rendezési algoritmus (Java, Python, C/C++ Példák kódra)
Sarah Chen
Mi az a Bucket Sort?
A csoportos rendezés, amelyet gyakran bin rendezésnek neveznek, egy összehasonlító rendezési módszer, amely egy rendezetlen tömböt fogad be bemenetként, és ennek eredményeként rendezett tömböt hoz létre. Ez a módszer úgy működik, hogy az elemeket több gyűjtőhelyre osztja fel, és ezeket a gyűjtőket egyenként rendezi bármilyen rendezési algoritmussal, például beszúrásos rendezéssel. Ezután az összes vödröt összevonják, és egy rendezett tömböt alkotnak.
A vödör rendezést általában akkor használják, ha az elemek
- Lebegőpontos értékek
- Egyenletesen elosztva egy tartományon belül
A vödör rendezés időbeli bonyolultsága a felhasznált gyűjtők számától és a bemeneti eloszlás egyenletességétől függ. Míg a különböző rendezési algoritmusok, mint pl shell fajta, Merge sort, Heapsort és gyorshajtás el tudja érni a legjobb esetben az O(n*logn) időbonyolultságot, a vödör rendezési algoritmus ugyanezt érheti el lineáris időbonyolultságban vagy O(n).
A vödör rendezés a szétszórt-gyűjtő megközelítést követi. Ezzel a megközelítéssel az elemeket szétszórják a megfelelő gyűjtőkön, a gyűjtőkön belül rendezik, majd utolsó lépésként összegyűjtik a rendezett tömböt. Ezt a szóródás-gyűjtő megközelítést a következő szakasz tárgyalja
Szórj-Gyerj-Közel
A nagy léptékű, összetett problémák megoldása esetenként kihívást jelenthet. A szóródás-gyűjtő megközelítés megpróbálja megoldani az ilyen problémákat azáltal, hogy a teljes adatkészletet klaszterekre osztja. Ezután az egyes klasztereket külön-külön megcímezzük, és mindent összehozunk, hogy megkapjuk a végső választ.
A vödör rendezési algoritmus így valósítja meg a scatter-Gather módszert:
Hogyan működik a vödör rendezés
A vödör rendezés alapvető működési elve a következő:
- Üres vödrök készlete jön létre. A különböző irányelvek alapján a gyűjtőhelyek száma eltérő lehet.
- A bemeneti tömbből tegyen minden elemet a megfelelő vödörbe.
- Válogassa szét ezeket a vödröket egyenként.
- A rendezett gyűjtők összefűzése egyetlen kimeneti tömb létrehozásához.
A részletes munkalépések a következő szakaszokban találhatók.
Álkód
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
1. módszer: Vödör szerinti rendezési algoritmus lebegőpontoshoz Numbers
A vödör rendezési algoritmusa 0.0 és 1.0 közötti lebegőpontos számokhoz:
Step 1) Hozzon létre tíz(10) üres gyűjtőmezőt úgy, hogy az első csoport a [0.0, 0.1 tartományon belüli számokat tartalmazza. Ekkor a második vödör [0.1, 0.2) és így tovább.
Step 2) Minden tömbelemhez:
-
a. Számítsa ki a vödörindexet a következő képlet segítségével:
bucket index= no_of_buckets *tömb_elem
-
b. Helyezze be az elemet a vödörbe[bucket_index]
Step 3) Az egyes gyűjtőket külön-külön rendezze be a beillesztési rendezés segítségével.
Step 4) Összefűzi az összes tárolót egyetlen tömbbe.
Lássunk egy vödör rendezési példát. Ebben a példában a következő tömböt rendezzük a vödör rendezési algoritmussal:
Step 1) Először 10 üres vödröt hozunk létre. Az első vödör a [0.0, 0.1 közötti számokat tartalmazza. Ezután a második vödör tartalmazza a [0.1, 0.2) és így tovább közötti számokat.
Step 2) Minden tömbelemhez kiszámítjuk a vödör indexét, és az elemet abba a vödörbe helyezzük.
A vödörindex a következő képlettel számítható ki:
bucket_index= no_of_buckets*array_element
Csoportindex számítása:
a) 0.78
bucket_index = vödörek_niája*tömb_elem
= 10 * 0.78
= 7.8
Ezért a 0.78 elem a vödörben[floor(7.8)] vagy a vödörben[7] lesz tárolva.
b) 0.17
bucket_index = no_of_buckets * tömbelem
= 10 * 0.17
= 1.7
A 0.17 tömbelem a bucket[floor(1.7)] vagy a bucket[1] helyen lesz tárolva.
c) 0.39
bucket_index = no_of_buckets * tömbelem
= 10*0.39
= 3.9
A 0.39 a vödörben[floor(3.9)] vagy a vödörben[3] lesz tárolva.
Az összes tömbelem iterációja után a gyűjtőzónák a következők lesznek:
Step 3) Ezután az egyes gyűjtők a beillesztési rendezés segítségével lesznek rendezve. A rendezési művelet után a kimenet a következő lenne:
Step 4) Az utolsó lépésben a vödrök egyetlen tömbbe lesznek összefűzve. Ez a tömb lesz a bemenet rendezett eredménye.
Minden egyes vödör a kimeneti tömbhöz fűződik. Például a második vödör elemeinek összefűzése:
Az utolsó vödör elemek összefűzése a következő lesz:
Az összefűzés után az eredményül kapott tömb a kívánt rendezett tömb lesz.
Vödör rendezés program C/C++
Bemenet:
//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
Vödör rendezési program be Python
Bemenet:
# 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]
Vödör Rendezés Java
Bemenet:
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
2. módszer: Vödör rendezési algoritmus egész számú elemekhez
A [0.0, 1.0] tartományon kívüli számokat tartalmazó bemenet vödör rendezési algoritmusa kissé eltér az előzőtől algoritmus. Az ebben az esetben szükséges lépések a következők:
Step 1) Keresse meg a maximális és minimális elemeket.
Step 2) Válassza ki a gyűjtőzónák számát (n), és inicializálja azokat üresként.
Step 3) Számítsa ki az egyes gyűjtőhelyek tartományát a következő képlet segítségével:
span = (maximum - minimum)/n
Step 4) Minden tömbelemhez:
-
1. Számítsa ki a csoportindexet:
bucket_index = (element - minimum)/span-
2. Illessze be az elemet a bucket[bucket_index]-be
Step 5) Rendezze az egyes gyűjtőket a beillesztési rendezés segítségével.
Step 6) Összefűzze az összes tárolót egyetlen tömbbe.
Nézzünk egy példát erre a vödör rendezési algoritmusra. Ebben a példában a következő tömböt rendezzük a vödör rendezési algoritmussal:
Step 1) Első lépésben meg kell találni az adott tömb maximális és minimális elemeit. Ebben a példában a maximum 24, a minimum pedig 1.
Step 2) Most ki kell választanunk néhány üres vödröt, n. Ebben a példában 5 vödröt veszünk. Ezután üresként inicializáljuk őket.
Step 3) Az egyes edények fesztávját a következő képlettel kell kiszámítani:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Ezért az első csoport a [0, 5 tartományon belüli számokat tartalmazza. A második vödör tartalmazza a számokat [5, 10) és így tovább.
Step 4) Minden tömbelemhez kiszámítjuk a vödör indexét, és az elemet abba a vödörbe helyezzük. A vödörindex a következő képlettel számítható ki:
bucket_index = (element - minimum)/span
Csoportindex számítása:
-
a) 11bucket_index = (elem – minimum)/span
=(11-1)/4
=2
Így a 11. elem a vödörben[2] lesz tárolva.
-
b) 9
bucket_index = (elem – minimum)/span
=(9-1)/4
=2
Jegyzet: Mivel a 9 a vödör[1] határeleme, a gyűjtőhelyhez[1] kell hozzáfűzni, ahelyett, hogy az előző elem ugyanabba a gyűjtőhelyébe fűzné.
Az egyes elemekhez tartozó műveletek végrehajtása után a vödrök a következők lesznek:
Step 5) Most minden gyűjtőzóna a beillesztési rendezés segítségével lesz rendezve. A vödrök válogatás után-
Step 6) Az utolsó lépésben a vödrök egyetlen tömbbe lesznek összefűzve. Hogy sor a bemenet rendezett eredménye lesz.
Vödör rendezés program C/C++
Bemenet:
#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
Vödör rendezési program be Python
Bemenet:
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]
Vödör Rendezés Java
Bemenet:
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
Érvek és ellenérvek
| Érvek | Hátrányok |
|---|---|
| Gyorsabb számítás végrehajtása | Több helyet foglal más algoritmusokhoz képest |
| Külső válogatási módszerként használható | Rosszul teljesít, ha az adatok nem egyenletesen oszlanak el |
| A vödrök önállóan is feldolgozhatók |
Vödör rendezés összetettségének elemzése
A vödör rendezési idő összetettsége
- Legjobb eset összetettsége:Ha az összes tömbelemet egyenletesen elosztjuk és előzetesen rendezzük, akkor O(n) időre lenne szükség ahhoz, hogy az elemeket a megfelelő gyűjtőhelyekbe szórjuk. Ezután az egyes vödrök válogatása segítségével beszúrási rendezés O(k)-ba kerülne. Így a teljes komplexitás O(n+k) lenne.
- Átlagos ügykomplexitás:Átlagos esetekben feltételezzük, hogy a bemenetek egyenletes eloszlásúak. Így a vödör rendezési algoritmus eléri az O(n+k) lineáris időbonyolultságot. Itt O(n) idő szükséges az elemek szórásához, és O(k) idő szükséges az elemek beszúrásos rendezéssel történő rendezéséhez.
- A legrosszabb eset összetettsége:A legrosszabb esetben az elemek nem egyenletesen oszlanak el és koncentrálódnak egy vagy két meghatározott vödörre. Ebben az esetben a vödör rendezés a buborék rendezési algoritmus. Ezért a legrosszabb esetben a vödör rendezés időbonyolultsága O(n^2) lenne.
A vödör rendezés térbeli összetettsége
A vödörrendezés térkomplexitása O(n*k). Itt n az elemek száma, k pedig a szükséges gyűjtőhelyek száma.