Bucket Sort Algorithm

I den här handledningen lär du dig hur sortering av hinkar fungerar. Du hittar också arbetsexempel på hink-sortering i C, C ++, Java och Python.

Bucket Sort är en sorteringsteknik som sorterar elementen genom att först dela in elementen i flera grupper som kallas hinkar . Elementen inuti varje hink sorteras med hjälp av någon av lämpliga sorteringsalgoritmer eller rekursivt anropande av samma algoritm.

Flera skopor skapas. Varje hink är fylld med ett specifikt utbud av element. Elementen inuti skopan sorteras med någon annan algoritm. Slutligen samlas elementen i skopan för att få den sorterade matrisen.

Processen för hink sortering kan förstås som en scatter-samla strategi. Elementen sprids först i skopor och sedan sorteras skopelementen. Slutligen samlas elementen i ordning.

Bearbetning av Bucket Sort

Hur fungerar Bucket Sort?

Antag att inmatningsmatrisen är: Inmatningsmatris
Skapa en matris med storlek 10. Varje plats i denna matris används som en hink för lagring av element. Array där varje position är en hink
Sätt in element i skoporna från matrisen. Elementen sätts in enligt skopans räckvidd.
I vår exempelkod har vi skopor var och en av intervallen från 0 till 1, 1 till 2, 2 till 3, … (n-1) till n.
Antag att ett ingångselement .23tas. Det multipliceras med size = 10(dvs. .23*10=2.3). Därefter omvandlas det till ett heltal (dvs. 2.3≈2). Slutligen sätts .23 i bucket-2 . Infoga element i skoporna från matrisen.
På samma sätt sätts också .25 i samma skopa. Varje gång tas golvvärdet för flytpunkten.
Om vi tar heltal som input måste vi dela det med intervallet (10 här) för att få golvvärdet.
På liknande sätt sätts andra element in i deras respektive skopor. Sätt in alla element i skoporna från matrisen
Elementen i varje skopa sorteras med någon av de stabila sorteringsalgoritmerna. Här har vi använt quicksort (inbyggd funktion). Sortera elementen i varje skopa
Elementen från varje hink samlas.
Det görs genom att itera genom skopan och infoga ett enskilt element i den ursprungliga matrisen i varje cykel. Elementet från skopan raderas när den har kopierats till den ursprungliga matrisen. Samla in element från varje hink

Bucket Sort Algorithm

 bucketSort () skapa N-skopor som alla kan innehålla ett intervall av värden för alla skopor initialisera varje skopa med 0-värden för alla skopor placera element i skopor som matchar intervallet för alla skopor sorteringselement i varje skopa samla element från varje skopa slut skopaSortera

Python, Java och C / C ++ exempel

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

Komplexitet

Värstfallskomplexitet: När det finns element av nära avstånd i matrisen kommer de sannolikt att placeras i samma hink. Detta kan resultera i att vissa skopor har mer antal element än andra. Det gör komplexiteten beroende av sorteringsalgoritmen som används för att sortera elementen i skopan. Komplexiteten blir ännu värre när elementen är i omvänd ordning. Om insättningssortering används för att sortera element i skopan blir tidskomplexiteten .O(n²)

O(n²)
Bästa fallkomplexitet: O(n+k)
Det inträffar när elementen fördelas jämnt i skoporna med nästan lika många element i varje skopa.
Komplexiteten blir ännu bättre om elementen i skoporna redan är sorterade.
Om insättningssortering används för att sortera element i en hink kommer den totala komplexiteten i bästa fall att vara linjär, dvs. O(n+k). O(n)är komplexiteten för att tillverka skoporna och O(k)är komplexiteten för att sortera elementen i skopan med hjälp av algoritmer som har linjär tidskomplexitet i bästa fall.
Genomsnittlig fallkomplexitet: O(n)
Det inträffar när elementen fördelas slumpmässigt i matrisen. Även om elementen inte är fördelade enhetligt, körs sorteringen på linjär tid. Det gäller tills summan av kvadraterna för skopstorlekarna är linjär i det totala antalet element.