Bucket Sort Algorithm

I denne veiledningen vil du lære hvordan sortering av bøtter fungerer. Du finner også arbeidseksempler på sortering av bøtter i C, C ++, Java og Python.

Bucket Sort er en sorteringsteknikk som sorterer elementene ved først å dele elementene i flere grupper som kalles bøtter . Elementene i hver bøtte er sortert ved hjelp av en hvilken som helst av de passende sorteringsalgoritmene eller ved å ringe den samme algoritmen rekursivt.

Flere bøtter lages. Hver bøtte er fylt med et bestemt utvalg av elementer. Elementene i bøtta sorteres ved hjelp av en hvilken som helst annen algoritme. Til slutt blir elementene i bøtta samlet for å få den sorterte matrisen.

Prosessen med sortering av bøtter kan forstås som en scatter-gather- tilnærming. Elementene blir først spredt i bøtter, deretter blir elementene i bøtter sortert. Til slutt er elementene samlet i rekkefølge.

Arbeid av Bucket Sort

Hvordan fungerer Bucket Sort?

Anta at inngangsmatrisen er: Inngangsmatrise
Opprett en matrise med størrelse 10. Hver spor i denne matrisen brukes som en bøtte for lagring av elementer. Array der hver posisjon er en bøtte
Sett inn elementer i skuffene fra matrisen. Elementene settes inn i henhold til rekkevidden til skuffen.
I vår eksempelkode har vi skuffer hver i området fra 0 til 1, 1 til 2, 2 til 3,… (n-1) til n.
Anta at det .23tas et inngangselement . Den multipliseres med size = 10(dvs. .23*10=2.3). Deretter blir det konvertert til et helt tall (dvs. 2.3≈2). Til slutt settes .23 inn i bøtte-2 . Sett inn elementer i bøttene fra matrisen.
På samme måte blir .25 også satt inn i samme bøtte. Hver gang blir gulvverdien til det flytende punktet tatt.
Hvis vi tar heltall som input, må vi dele det med intervallet (10 her) for å få gulvverdien.
Tilsvarende settes andre elementer inn i deres respektive bøtter. Sett alle elementene i skuffene fra matrisen
Elementene i hver bøtte sorteres ved hjelp av noen av de stabile sorteringsalgoritmene. Her har vi brukt quicksort (innebygd funksjon). Sorter elementene i hver bøtte
Elementene fra hver bøtte er samlet.
Det gjøres ved å iterere gjennom skuffen og sette inn et enkelt element i den opprinnelige matrisen i hver syklus. Elementet fra bøtta slettes når den er kopiert til den opprinnelige matrisen. Samle elementer fra hver bøtte

Bucket Sort Algorithm

 bucketSort () opprett N bøtter, som hver kan inneholde et verdiområde for alle bøttene initialiser hver bøtte med 0 verdier for alle bøttene, legg elementer i bøtter som samsvarer med området for alle bøttene, sorter elementene i hver bøtte, samle elementer fra hver bøtte slutt bøtteSort

Python, Java og C / C ++ eksempler

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); )

Kompleksitet

Verste sakskompleksitet: Når det er elementer av nær rekkevidde i matrisen, vil de sannsynligvis plasseres i samme bøtte. Dette kan føre til at noen bøtter har flere antall elementer enn andre. Det gjør at kompleksiteten avhenger av sorteringsalgoritmen som brukes til å sortere elementene i bøtta. Kompleksiteten blir enda verre når elementene er i omvendt rekkefølge. Hvis innsettingssortering brukes til å sortere elementer i bøtta, blir tidskompleksiteten .O(n²)

O(n²)
Best case-kompleksitet: O(n+k)
Det oppstår når elementene fordeles jevnt i skuffene med nesten like mange elementer i hver bøtte.
Kompleksiteten blir enda bedre hvis elementene i skuffene allerede er sortert.
Hvis innsettingssortering brukes til å sortere elementer i en bøtte, vil den samlede kompleksiteten i beste fall være lineær, dvs. O(n+k). O(n)er kompleksiteten for å lage skuffene og O(k)er kompleksiteten for å sortere elementene i skuffen ved hjelp av algoritmer som har lineær tidskompleksitet i beste fall.
Gjennomsnittlig sakskompleksitet: O(n)
Det oppstår når elementene fordeles tilfeldig i matrisen. Selv om elementene ikke er fordelt jevnt, går skuffesortering lineært. Det gjelder til summen av kvadratene i skuffestørrelsene er lineær i det totale antallet elementer.