Algoritmul de sortare al găleților (Java, Python, C/C++ Exemple de cod)
Sarah Chen
Ce este Bucket Sort?
Bucket sort, numită adesea bin sort, este o metodă de sortare prin comparație care acceptă o matrice nesortată ca intrare și ca rezultat produce o matrice sortată. Această metodă funcționează prin distribuirea elementelor în mai multe găleți și sortarea fiecăruia dintre acele găleți individual, după orice algoritm de sortare, cum ar fi sortarea prin inserție. Apoi toate gălețile sunt îmbinate împreună pentru a forma o matrice sortată.
Sortarea cu găleată este folosită în mod obișnuit atunci când elementele sunt-
- Valori în virgulă mobilă
- Distribuit uniform pe un interval
Complexitatea de timp a sortării găleților depinde de numărul de găleți utilizate și de uniformitatea distribuției de intrare. În timp ce diferiți algoritmi de sortare, cum ar fi sortarea cochiliei, sortare îmbinare, sortare în grămada și sortare rapida poate atinge complexitatea timpului în cel mai bun caz de O(n*logn), algoritmul de sortare al găleților poate realiza același lucru în complexitatea timpului liniar sau O(n).
Sortarea cu găleți urmează abordarea scatter-gather. Aplicând această abordare, elementele sunt împrăștiate în gălețile corespunzătoare, sortate în găleți și adunate pentru a forma o matrice sortată ca pas final. Această abordare scatter-gather este discutată în secțiunea următoare
Imprăștire-Adunare-Abordare
Problemele complexe, la scară largă, pot fi ocazional dificil de rezolvat. Abordarea scatter-gather încearcă să rezolve astfel de probleme prin împărțirea întregului set de date în clustere. Apoi, fiecare grup este abordat separat și a reunit totul pentru a obține răspunsul final.
Acesta este modul în care algoritmul de sortare al găleților implementează metoda scatter-gather:
Cum funcționează sortarea găleților
Principiul de bază de lucru al sortării cu găleată este următorul:
- Se creează un set de găleți goale. Pe baza diferitelor politici, numărul de compartimente poate diferi.
- Din matricea de intrare, puneți fiecare element în găleata corespunzătoare.
- Sortați acele găleți individual.
- Concatenați gălețile sortate pentru a crea o singură matrice de ieșire.
Pașii de lucru detaliați sunt furnizați în secțiunile următoare.
Pseudo cod
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
Metoda 1: Algoritmul de sortare al găleților pentru virgulă mobilă Numbers
Algoritmul de sortare al găleților pentru numerele cu virgulă mobilă în intervalul de la 0.0 la 1.0:
Pas 1) Creați zece (10) găleți goale astfel încât prima găleată să conțină numere în intervalul [0.0, 0.1). Apoi, a doua găleată va conține în [0.1, 0.2) și așa mai departe.
Pas 2) Pentru fiecare element de matrice:
-
A. Calculați indicele găleții folosind formula:
bucket index= nr_de_găleți *element_array
-
b. Introduceți elementul în găleată[bucket_index]
Pas 3) Sortați fiecare găleată individual utilizând sortarea prin inserție.
Pas 4) Concatenați toate gălețile într-o singură matrice.
Să vedem un exemplu de sortare a găleților. Pentru acest exemplu, vom sorta următoarea matrice utilizând algoritmul de sortare al găleților-
Pas 1) Mai întâi, vom crea 10 găleți goale. Prima găleată va conține numerele cuprinse între [0.0, 0.1). Apoi, a doua găleată va conține numerele cuprinse între [0.1, 0.2) și așa mai departe.
Pas 2) Pentru fiecare element de matrice, vom calcula indicele găleții și vom plasa elementul în acea găleată.
Indicele găleții poate fi calculat folosind formula:
bucket_index= nr_de_găleți*element_array
Calculul indicelui găleții:
a) 0.78
bucket_index = nr_of_buckets*element_array
= 10 * 0.78
= 7.8
Prin urmare, elementul 0.78 va fi stocat pe găleată[floor(7.8)] sau găleată[7].
b) 0.17
bucket_index = no_of_buckets * element de matrice
= 10 * 0.17
= 1.7
Elementul de matrice 0.17 va fi stocat pe bucket[floor(1.7)] sau bucket[1].
c) 0.39
bucket_index = no_of_buckets * element de matrice
= 10 * 0.39
= 3.9
0.39 va fi stocat pe găleată[floor(3.9)] sau găleată[3].
După iterarea tuturor elementelor matricei, gălețile vor fi următoarele:
Pas 3) Apoi, fiecare găleată va fi sortată utilizând sortarea prin inserție. După operația de sortare, rezultatul ar fi:
Pas 4) În pasul final, gălețile vor fi concatenate într-o singură matrice. Această matrice va fi rezultatul sortat al intrării.
Fiecare găleată va fi concatenată la matricea de ieșire. De exemplu, concatenarea elementelor a doua găleată:
Concatenarea ultimelor elemente de găleată va fi următoarea:
După concatenare, matricea rezultată va fi matricea sortată dorită.
Program de sortare a găleților în C/C++
Intrare:
//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;
}
ieșire:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Programul de sortare a găleților în Python
Intrare:
# 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))
ieșire:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Sortare cu găleată Java
Intrare:
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]+" ");
}
}
}
ieșire:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Metoda 2: Algoritmul de sortare al găleților pentru elemente întregi
Algoritmul de sortare al găleților pentru intrarea care conține numere dincolo de intervalul [0.0, 1.0] este puțin diferit față de cel precedent Algoritmul. Pașii necesari pentru acest caz sunt următorii:
Pas 1) Găsiți elementele maxime și minime.
Pas 2) Selectați numărul de compartimente, n și inițializați acele compartimente ca goale.
Pas 3) Calculați intervalul sau intervalul fiecărei găleți folosind formula:
span = (maximum - minimum)/n
Pas 4) Pentru fiecare element de matrice:
-
1.Calculați indicele găleții:
bucket_index = (element - minimum)/span-
2.Inserați elementul în găleată[bucket_index]
Pas 5) Sortați fiecare găleată folosind sortarea prin inserție.
Pas 6) Concatenează toate gălețile într-o singură matrice.
Să vedem un exemplu al acestui algoritm de sortare a găleților. Pentru acest exemplu, vom sorta următoarea matrice utilizând algoritmul de sortare al găleților-
Pas 1) În primul pas, trebuie găsite elementele maxime și minime ale matricei date. Pentru acest exemplu, maximul este 24, iar minimul este 1.
Pas 2) Acum, trebuie să selectăm un număr de găleți goale, n. În acest exemplu, vom lua 5 găleți. Apoi le vom inițializa ca goale.
Pas 3) Spațiul fiecărei găleți trebuie calculat prin următoarea formulă:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Prin urmare, prima găleată va conține numerele din intervalul [0, 5). A doua găleată va conține numerele din [5, 10) și așa mai departe.
Pas 4) Pentru fiecare element de matrice, vom calcula indicele găleții și vom plasa elementul în acea găleată. Indicele găleții poate fi calculat folosind formula:
bucket_index = (element - minimum)/span
Calculul indicelui găleții:
-
a) 11bucket_index = (element – minim)/span
=(11-1)/4
=2
Astfel, elementul 11 va fi stocat în găleată[2].
-
b) 9
bucket_index = (element – minim)/span
=(9-1)/4
=2
Notă: Deoarece 9 este un element de limită pentru găleată[1], acesta trebuie să fie atașat în găleată[1] în loc să fie adăugat în aceeași găleată a elementului anterior.
După efectuarea operațiilor pentru fiecare element, gălețile vor fi după cum urmează:
Pas 5) Acum, fiecare găleată va fi sortată folosind sortarea prin inserție. Gălețile după sortare-
Pas 6) În pasul final, gălețile vor fi concatenate într-o singură matrice. Acea mulțime va fi rezultatul sortat al intrării.
Program de sortare a găleților în C/C++
Intrare:
#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;
}
ieșire:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Programul de sortare a găleților în Python
Intrare:
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)
ieșire:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Sortare cu găleată Java
Intrare:
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 + " ");
}
}
}
ieșire:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Avantaje dezavantaje
| Pro-uri | Contra |
|---|---|
| Efectuați calcule mai rapide | Consumă mai mult spațiu în comparație cu alți algoritmi |
| Poate fi folosit ca metodă de sortare externă | Funcționează slab atunci când datele nu sunt distribuite uniform |
| Gălețile pot fi procesate independent |
Analiza complexității sortării găleții
Complexitatea timpului lui Bucket Sort
- Complexitatea celui mai bun caz:Dacă toate elementele matricei sunt distribuite și sortate uniform în prealabil, ar fi nevoie de timp O(n) pentru a împrăștia elementele în gălețile corespunzătoare. Apoi sortați fiecare găleată folosind sortare inserție ar costa O(k). Astfel, complexitatea globală ar fi O(n+k).
- Complexitatea medie a cazului:Pentru cazuri medii, presupunem că intrările sunt distribuite uniform. Astfel, algoritmul de sortare al găleților atinge complexitatea timpului liniar de O(n+k). Aici este necesar timp O(n) pentru împrăștierea elementelor și timp O(k) este necesar pentru sortarea acelor elemente folosind sortarea prin inserție.
- Complexitatea celui mai rău caz:În cel mai rău caz, elementele nu vor fi uniform distribuite și concentrate pe una sau două găleți specifice. În acest caz, sortarea cu găleată va funcționa ca un algoritm de sortare cu bule. Prin urmare, în cel mai rău caz, complexitatea de timp a unui tip de găleată ar fi O(n^2).
Complexitatea spațială a sortării găleții
Complexitatea spațială a sortării găleții este O(n*k). Aici n este numărul de elemente și k este numărul de găleți necesare.
