Algoritmo di ordinamento dei bucket

In questo tutorial imparerai come funziona l'ordinamento dei bucket. Inoltre, troverai esempi funzionanti di bucket sort in C, C ++, Java e Python.

Bucket Sort è una tecnica di ordinamento che ordina gli elementi dividendo prima gli elementi in diversi gruppi chiamati bucket . Gli elementi all'interno di ogni bucket vengono ordinati utilizzando uno qualsiasi degli algoritmi di ordinamento appropriati o chiamando ricorsivamente lo stesso algoritmo.

Vengono creati diversi bucket. Ogni secchio è riempito con una gamma specifica di elementi. Gli elementi all'interno del bucket vengono ordinati utilizzando qualsiasi altro algoritmo. Infine, gli elementi del bucket vengono raccolti per ottenere l'array ordinato.

Il processo di bucket sort può essere inteso come un approccio scatter-gather . Gli elementi vengono prima dispersi in bucket, quindi vengono ordinati gli elementi dei bucket. Infine, gli elementi vengono raccolti in ordine.

Funzionamento del Bucket Sort

Come funziona il Bucket Sort?

Supponiamo che l'array di input sia: Array di input
Crea un array di dimensione 10. Ogni slot di questo array viene utilizzato come bucket per memorizzare gli elementi. Matrice in cui ogni posizione è un secchio
Inserisci gli elementi nei bucket dall'array. Gli elementi vengono inseriti in base alla gamma della benna.
Nel nostro codice di esempio, abbiamo segmenti ciascuno di intervalli da 0 a 1, 1 a 2, 2 a 3,… (n-1) a n.
Supponiamo che .23venga preso un elemento di input . È moltiplicato per size = 10(cioè .23*10=2.3). Quindi, viene convertito in un numero intero (cioè 2.3≈2). Infine, .23 viene inserito nel bucket-2 . Inserisci elementi nei bucket dall'array
Allo stesso modo, anche .25 viene inserito nello stesso bucket. Ogni volta, viene preso il valore minimo del numero in virgola mobile.
Se prendiamo numeri interi come input, dobbiamo dividerli per l'intervallo (10 qui) per ottenere il valore minimo.
Allo stesso modo, altri elementi vengono inseriti nei rispettivi secchi. Inserisci tutti gli elementi nei bucket dall'array
Gli elementi di ogni bucket vengono ordinati utilizzando uno qualsiasi degli algoritmi di ordinamento stabili. Qui abbiamo usato quicksort (funzione incorporata). Ordina gli elementi in ogni bucket
Gli elementi di ogni bucket vengono raccolti.
Viene eseguito iterando attraverso il bucket e inserendo un singolo elemento nell'array originale in ogni ciclo. L'elemento dal bucket viene cancellato una volta copiato nell'array originale. Raccogli elementi da ogni secchio

Algoritmo di ordinamento dei bucket

 bucketSort () crea N bucket ciascuno dei quali può contenere un intervallo di valori per tutti i bucket inizializza ogni bucket con valori 0 per tutti i bucket inserisci gli elementi nei bucket corrispondenti all'intervallo per tutti i bucket ordina gli elementi in ciascun bucket raccogli elementi da ciascun bucket fine secchio

Esempi di Python, Java e C / C ++

Python Java C C ++

 # Bucket Sort in Python def bucketSort(array): bucket = () # Create empty buckets for i in range(len(array)): bucket.append(()) # Insert elements into their respective buckets for j in array: index_b = int(10 * j) bucket(index_b).append(j) # Sort the elements of each bucket for i in range(len(array)): bucket(i) = sorted(bucket(i)) # Get the sorted elements k = 0 for i in range(len(array)): for j in range(len(bucket(i))): array(k) = bucket(i)(j) k += 1 return array array = (.42, .32, .33, .52, .37, .47, .51) print("Sorted Array in descending order is") print(bucketSort(array))

 // Bucket sort in Java import java.util.ArrayList; import java.util.Collections; public class BucketSort ( public void bucketSort(float() arr, int n) ( if (n <= 0) return; @SuppressWarnings("unchecked") ArrayList() bucket = new ArrayList(n); // Create empty buckets for (int i = 0; i < n; i++) bucket(i) = new ArrayList(); // Add elements into the buckets for (int i = 0; i < n; i++) ( int bucketIndex = (int) arr(i) * n; bucket(bucketIndex).add(arr(i)); ) // Sort the elements of each bucket for (int i = 0; i < n; i++) ( Collections.sort((bucket(i))); ) // Get the sorted array int index = 0; for (int i = 0; i < n; i++) ( for (int j = 0, size = bucket(i).size(); j < size; j++) ( arr(index++) = bucket(i).get(j); ) ) ) // Driver code public static void main(String() args) ( BucketSort b = new BucketSort(); float() arr = ( (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47, (float) 0.51 ); b.bucketSort(arr, 7); for (float i : arr) System.out.print(i + " "); ) )

 // Bucket sort in C #include #include #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) printf("-------------"); printf("Bucktets after sorting"); for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) void print(int ar()) ( int i; for (i = 0; i data); cur = cur->next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); printf("Initial array: "); print(array); printf("-------------"); BucketSort(array); printf("-------------"); printf("Sorted array: "); print(array); return 0; )

 // Bucket sort in C++ #include #include using namespace std; #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) cout << "-------------" << endl; cout << "Bucktets after sorted" << endl; for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) for (i = 0; i next; free(tmp); ) ) free(buckets); return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) // Print buckets void print(int ar()) ( int i; for (i = 0; i < NARRAY; ++i) ( cout << setw(3) << ar(i); ) cout << endl; ) void printBuckets(struct Node *list) ( struct Node *cur = list; while (cur) ( cout << setw(3)  next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); cout << "Initial array: " << endl; print(array); cout << "-------------" << endl; BucketSort(array); cout << "-------------" << endl; cout << "Sorted array: " << endl; print(array); )

Complessità

Complessità del caso peggiore: quando sono presenti elementi a distanza ravvicinata nell'array, è probabile che vengano inseriti nello stesso bucket. Ciò può comportare che alcuni bucket abbiano più numero di elementi rispetto ad altri. Fa dipendere la complessità dall'algoritmo di ordinamento utilizzato per ordinare gli elementi del bucket. La complessità diventa ancora peggiore quando gli elementi sono in ordine inverso. Se l'ordinamento per inserimento viene utilizzato per ordinare gli elementi del bucket, la complessità temporale diventa .O(n²)

O(n²)
Complessità del caso migliore: O(n+k)
si verifica quando gli elementi sono distribuiti uniformemente nei bucket con un numero quasi uguale di elementi in ciascun bucket.
La complessità diventa ancora migliore se gli elementi all'interno dei bucket sono già ordinati.
Se l'ordinamento per inserzione viene utilizzato per ordinare gli elementi di un bucket, la complessità complessiva nel migliore dei casi sarà lineare, ad es. O(n+k). O(n)è la complessità per creare i bucket ed O(k)è la complessità per ordinare gli elementi del bucket utilizzando algoritmi aventi complessità temporale lineare nel migliore dei casi.
Complessità case media: O(n)
si verifica quando gli elementi sono distribuiti casualmente nell'array. Anche se gli elementi non sono distribuiti in modo uniforme, l'ordinamento per bucket viene eseguito in tempo lineare. È vero fino a quando la somma dei quadrati delle dimensioni del secchio non è lineare nel numero totale di elementi.