Algoritmo di ordinamento del bucket (Java, Python, C/C++ Esempi di codici)
Sara Chen
Cos'è l'ordinamento dei bucket?
L'ordinamento dei bucket, spesso chiamato ordinamento dei contenitori, è un metodo di ordinamento per confronto che accetta un array non ordinato come input e produce come risultato un array ordinato. Questo metodo funziona distribuendo gli elementi in più contenitori e ordinando ciascuno di questi contenitori individualmente mediante qualsiasi algoritmo di ordinamento come l'ordinamento per inserzione. Quindi tutti i bucket vengono uniti insieme per formare un array ordinato.
L'ordinamento del bucket viene comunemente utilizzato quando gli elementi sono-
- Valori in virgola mobile
- Distribuito uniformemente su un intervallo
La complessità temporale del bucket sort dipende dal numero di bucket utilizzati e dall'uniformità della distribuzione degli input. Mentre diversi algoritmi di ordinamento come ordinamento della shell, unisci sort, heapsort e smistamento rapido può raggiungere la migliore complessità temporale di O(n*logn), l'algoritmo di ordinamento bucket può ottenere lo stesso risultato in complessità temporale lineare o O(n).
Bucket sort segue l'approccio scatter-gather. Applicando questo approccio, gli elementi vengono sparsi nei bucket corrispondenti, ordinati nei bucket e raccolti per formare un array ordinato come passaggio finale. Questo approccio scatter-gather è discusso nella sezione seguente
Approccio dispersione-raccolta
Problemi complessi e su larga scala possono occasionalmente essere difficili da risolvere. L'approccio scatter-gather tenta di risolvere tali problemi dividendo l'intero set di dati in cluster. Quindi ogni cluster viene affrontato separatamente e ricomposto per ottenere la risposta finale.
Ecco come l'algoritmo di ordinamento del bucket implementa il metodo scatter-gather:
Come funziona l'ordinamento dei bucket
Il principio di funzionamento di base del bucket sort è il seguente:
- Viene creato un set di bucket vuoti. In base alle diverse policy, il numero di bucket può variare.
- Dall'array di input, inserisci ciascun elemento nel bucket corrispondente.
- Ordina quei secchi individualmente.
- Concatena i bucket ordinati per creare un singolo array di output.
Le fasi di lavoro dettagliate sono fornite nelle sezioni seguenti.
Pseudo codice
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
Metodo 1: algoritmo di ordinamento del bucket per virgola mobile Numbers
L'algoritmo di ordinamento del bucket per i numeri in virgola mobile nell'intervallo da 0.0 a 1.0:
Passo 1) Crea dieci (10) contenitori vuoti in modo che il primo contenitore contenga numeri nell'intervallo [0.0, 0.1). Quindi il secondo bucket conterrà [0.1, 0.2) e così via.
Passo 2) Per ogni elemento dell'array:
-
UN. Calcola l'indice del bucket utilizzando la formula:
indice bucket= no_of_buckets *array_element
-
B. Inserisci l'elemento nel bucket[bucket_index]
Passo 3) Ordina ciascun bucket individualmente utilizzando l'ordinamento per inserzione.
Passo 4) Concatena tutti i bucket in un unico array.
Vediamo un esempio di bucket sort. Per questo esempio, ordineremo il seguente array utilizzando l'algoritmo bucket sort:
Passo 1) Per prima cosa creeremo 10 bucket vuoti. Il primo bucket conterrà i numeri compresi tra [0.0, 0.1). Quindi il secondo bucket conterrà i numeri compresi tra [0.1, 0.2) e così via.
Passo 2) Per ogni elemento dell'array, calcoleremo l'indice del bucket e posizioneremo l'elemento in quel bucket.
L'indice del bucket può essere calcolato utilizzando la formula:
bucket_index= no_of_buckets*array_element
Calcolo dell'indice del bucket:
a) 0.78
bucket_index = no_di_buckets*array_element
= 10 * 0.78
= 7.8
Pertanto, l'elemento 0.78 verrà memorizzato nel bucket[floor(7.8)] o nel bucket[7].
b) 0.17
bucket_index = no_of_buckets * elemento dell'array
= 10 * 0.17
= 1.7
L'elemento dell'array 0.17 verrà archiviato in bucket[floor(1.7)] o bucket[1].
c) 0.39
bucket_index = no_of_buckets * elemento dell'array
= 10 * 0.39
= 3.9
0.39 verrà archiviato in bucket[floor(3.9)] o bucket[3].
Dopo aver eseguito l'iterazione su tutti gli elementi dell'array, i bucket saranno i seguenti:
Passo 3) Quindi, ciascun bucket verrà ordinato utilizzando l'ordinamento per inserzione. Dopo l'operazione di ordinamento, l'output sarebbe:
Passo 4) Nella fase finale, i bucket verranno concatenati in un unico array. Tale array sarà il risultato ordinato dell'input.
Ogni bucket verrà concatenato all'array di output. Ad esempio, la concatenazione dei secondi elementi del bucket:
La concatenazione degli ultimi elementi del bucket sarà la seguente:
Dopo la concatenazione, l'array risultante sarà l'array ordinato desiderato.
Programma di ordinamento dei bucket in C/C++
Ingresso:
//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;
}
Produzione:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Programma di ordinamento del bucket in Python
Ingresso:
# 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))
Produzione:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Ordinamento a secchiello Java
Ingresso:
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]+" ");
}
}
}
Produzione:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Metodo 2: algoritmo di ordinamento del bucket per elementi interi
L'algoritmo di ordinamento del bucket per l'input che contiene numeri oltre l'intervallo [0.0, 1.0] è leggermente diverso dal precedente algoritmo. I passaggi necessari per questo caso sono i seguenti:
Passo 1) Trova gli elementi massimi e minimi.
Passo 2) Seleziona il numero di contenitori, n, e inizializza tali contenitori come vuoti.
Passo 3) Calcola l'intervallo o l'intervallo di ciascun bucket utilizzando la formula:
span = (maximum - minimum)/n
Passo 4) Per ogni elemento dell'array:
-
1.Calcola l'indice del bucket:
bucket_index = (element - minimum)/span-
2.Inserisci l'elemento in bucket[bucket_index]
Passo 5) Ordina ciascun bucket utilizzando l'ordinamento per inserzione.
Passo 6) Concatena tutti i bucket in un unico array.
Vediamo un esempio di questo algoritmo di bucket sort. Per questo esempio, ordineremo il seguente array utilizzando l'algoritmo di bucket sort:
Passo 1) Nel primo passaggio è necessario trovare gli elementi massimo e minimo dell'array specificato. Per questo esempio, il massimo è 24 e il minimo è 1.
Passo 2) Ora dobbiamo selezionare un numero di secchi vuoti, n. In questo esempio, prenderemo 5 secchi. Quindi li inizializzeremo come vuoti.
Passo 3) La campata di ogni bucket deve essere calcolata con la seguente formula:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Pertanto, il primo bucket conterrà i numeri nell'intervallo [0, 5). Il secondo bucket conterrà i numeri all'interno di [5, 10) e così via.
Passo 4) Per ogni elemento dell'array, calcoleremo l'indice del bucket e posizioneremo l'elemento in quel bucket. L'indice del bucket può essere calcolato utilizzando la formula:
bucket_index = (element - minimum)/span
Calcolo dell'indice del bucket:
-
a) 11bucket_index = (elemento – minimo)/intervallo
=(11-1)/4
=2
Pertanto, l'elemento 11 verrà memorizzato nel bucket[2].
-
b) 9
bucket_index = (elemento – minimo)/intervallo
=(9-1)/4
=2
Nota: Poiché 9 è un elemento di confine per il bucket[1], deve essere aggiunto a bucket[1] invece di essere aggiunto allo stesso bucket dell'elemento precedente.
Dopo aver eseguito le operazioni per ciascun elemento, i bucket saranno i seguenti:
Passo 5) Ora ogni bucket verrà ordinato utilizzando l'ordinamento per inserzione. I secchi dopo la cernita
Passo 6) Nella fase finale, i bucket verranno concatenati in un unico array. Quello schieramento sarà il risultato ordinato dell'input.
Programma di ordinamento dei bucket in C/C++
Ingresso:
#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;
}
Produzione:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Programma di ordinamento del bucket in Python
Ingresso:
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)
Produzione:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Ordinamento a secchiello Java
Ingresso:
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 + " ");
}
}
}
Produzione:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Pro e contro
| Vantaggi | Contro |
|---|---|
| Esegui calcoli più rapidi | Consuma più spazio rispetto ad altri algoritmi |
| Può essere utilizzato come metodo di ordinamento esterno | Ha prestazioni scadenti quando i dati non sono distribuiti uniformemente |
| I bucket possono essere elaborati in modo indipendente |
Analisi della complessità del bucket sort
Complessità temporale di Bucket Sort
- migliore Complessità del caso:Se tutti gli elementi dell'array fossero distribuiti e ordinati in modo uniforme in anticipo, sarebbe necessario O(n) tempo per disperdere gli elementi nei contenitori corrispondenti. Quindi ordinare ciascun secchio utilizzando ordinamento per inserzione costerebbe O(k). Quindi la complessità complessiva sarebbe O(n+k).
- Complessità media del caso:Per i casi medi, assumiamo che gli input siano distribuiti uniformemente. Quindi l'algoritmo di bucket sorting raggiunge una complessità temporale lineare di O(n+k). Qui è richiesto tempo O(n) per la dispersione degli elementi e tempo O(k) per l'ordinamento di tali elementi mediante l'ordinamento per inserimento.
- Complessità del caso peggiore:Nel peggiore dei casi, gli elementi non saranno distribuiti uniformemente e concentrati su uno o due secchi specifici. In tal caso, l'ordinamento del bucket funzionerà come a algoritmo di ordinamento delle bolle. Pertanto, nel caso peggiore, la complessità temporale di un bucket sort sarebbe O(n^2).
Complessità spaziale del bucket sort
La complessità spaziale del bucket sort è O(n*k). Qui n è il numero di elementi e k è il numero di bucket richiesti.
