Algoritm de sortare a cupei

În acest tutorial, veți afla cum funcționează sortarea în cupe. De asemenea, veți găsi exemple de lucru de sortare bucket în C, C ++, Java și Python.

Bucket Sort este o tehnică de sortare care sortează elementele împărțind mai întâi elementele în mai multe grupuri numite găleți . Elementele din interiorul fiecărei cupe sunt sortate folosind oricare dintre algoritmii de sortare corespunzători sau apelând recursiv același algoritm.

Sunt create mai multe găleți. Fiecare găleată este umplută cu o gamă specifică de elemente. Elementele din interiorul cupei sunt sortate folosind orice alt algoritm. În cele din urmă, elementele cupei sunt adunate pentru a obține matricea sortată.

Procesul de sortare a găleatelor poate fi înțeles ca o abordare dispersivă . Elementele sunt mai întâi împrăștiate în găleți, apoi elementele găleților sunt sortate. În cele din urmă, elementele sunt adunate în ordine.

Funcționarea sortării cupei

Cum funcționează sortarea cupei?

Să presupunem că matricea de intrare este: Matrice de intrare
Creați o matrice de dimensiunea 10. Fiecare slot al acestei matrice este folosit ca o bucket pentru stocarea elementelor. Matrice în care fiecare poziție este o găleată
Introduceți elemente în găleți din matrice. Elementele sunt inserate în funcție de intervalul cupei.
În exemplul nostru de cod, avem găleți fiecare cu intervale de la 0 la 1, 1 la 2, 2 la 3, … (n-1) la n.
Să presupunem că .23este luat un element de intrare . Se înmulțește cu size = 10(adică .23*10=2.3). Apoi, este convertit într-un număr întreg (adică 2.3≈2). În cele din urmă, .23 este introdus în cupa-2 . Introduceți elemente în găleți din matrice
În mod similar, .25 este, de asemenea, introdus în aceeași găleată. De fiecare dată, se ia valoarea minimă a numărului în virgulă mobilă.
Dacă luăm numere întregi ca intrare, trebuie să-l împărțim la interval (10 aici) pentru a obține valoarea etajului.
În mod similar, alte elemente sunt inserate în gălețile lor respective. Introduceți toate elementele în găleți din matrice
Elementele fiecărei găleți sunt sortate folosind oricare dintre algoritmii stabili de sortare. Aici, am folosit quicksort (funcție încorporată). Sortați elementele din fiecare cupă
Elementele din fiecare găleată sunt adunate.
Se face prin iterarea prin cupă și inserarea unui element individual în matricea originală în fiecare ciclu. Elementul din găleată este șters odată ce este copiat în matricea originală. Adunați elemente din fiecare găleată

Algoritm de sortare a cupei

 bucketSort () creează N găleți, fiecare dintre acestea putând deține o gamă de valori pentru toate gălețile inițializează fiecare găleți cu 0 valori pentru toate gălețile plasate elemente în găleți care corespund intervalului pentru toate gălețile. sfârșitul găleatăSort

Exemple Python, Java și 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); )

Complexitate

Cel mai prost caz de complexitate: atunci când există elemente de rază apropiată în matrice, este probabil ca acestea să fie plasate în aceeași cupă. Acest lucru poate duce la faptul că unele găleți au mai multe elemente decât altele. Face complexitatea să depindă de algoritmul de sortare folosit pentru sortarea elementelor cupei. Complexitatea devine și mai gravă atunci când elementele sunt în ordine inversă. Dacă sortarea prin inserție este utilizată pentru a sorta elementele cupei, atunci complexitatea timpului devine .O(n²)

O(n²)
Complexitatea celui mai bun caz: O(n+k)
apare atunci când elementele sunt distribuite uniform în cupe cu un număr aproape egal de elemente în fiecare cupă.
Complexitatea devine și mai bună dacă elementele din interiorul găleților sunt deja sortate.
Dacă sortarea prin inserție este utilizată pentru a sorta elementele unei găleți, atunci complexitatea generală în cel mai bun caz va fi liniar, adică. O(n+k). O(n)este complexitatea pentru realizarea găleților și O(k)este complexitatea pentru sortarea elementelor găleții folosind algoritmi cu complexitate de timp liniară în cel mai bun caz.
Complexitatea medie a cazurilor: O(n)
apare atunci când elementele sunt distribuite aleatoriu în matrice. Chiar dacă elementele nu sunt distribuite uniform, sortarea cupei rulează în timp liniar. Este valabil până când suma pătratelor dimensiunilor cupei este liniară în numărul total de elemente.