Vödör rendezési algoritmus

Ebben az oktatóanyagban megtudhatja, hogyan működik a vödrök rendezése. Ezenkívül a C, C ++, a Java és a Pythonban is talál példákat a vödrök rendezésére.

A Bucket Sort egy válogatási technika, amely az elemeket úgy rendezi, hogy először több csoportra osztja az elemeket, úgynevezett vödrökre . Az egyes vödrökben lévő elemeket a megfelelő rendezési algoritmusok bármelyikével rendezik, vagy rekurzív módon ugyanazt az algoritmust hívják meg.

Több vödör jön létre. Minden vödör meghatározott elemtartománnyal van feltöltve. A vödör belsejében lévő elemeket bármilyen más algoritmus segítségével rendezzük. Végül a vödör elemeit összegyűjtjük, hogy megkapjuk a rendezett tömböt.

A vödrös rendezés folyamata szétszóródás-összegyűjtés megközelítésként értelmezhető. Az elemeket először szétszórják vödrökbe, majd a vödrök elemeit rendezik. Végül az elemeket sorrendben gyűjtjük össze.

Bucket Sort működése

Hogyan működik a vödör rendezés?

Tegyük fel, hogy a bemeneti tömb a következő: Bemeneti tömb
Hozzon létre egy 10-es méretű tömböt. Ennek a tömbnek minden egyes nyílását vödörként használják az elemek tárolására. Tömb, amelyben minden helyzet egy vödör
Helyezzen elemeket a tömbből a vödrökbe. Az elemeket a vödör tartományának megfelelően helyezzük be.
Példakódunkban 0 és 1, 1 és 2, 2 és 3,… (n-1) és n közötti tartományok vannak.
Tegyük fel, hogy egy bemeneti elemet .23veszünk fel. Megszorozza size = 10(azaz. .23*10=2.3). Ezután egész számra (azaz 2.3≈2) konvertáljuk . Végül 0,23-at illesztünk a 2-es vödörbe . Helyezzen elemeket a tömbökből a tömbökbe.
Hasonlóképpen, .25 is beillesztésre kerül ugyanabba a vödörbe. Minden alkalommal a lebegőpontos szám padlóértékét vesszük fel.
Ha egész számokat veszünk bemenetként, el kell osztanunk az intervallummal (itt 10), hogy megkapjuk a legalacsonyabb értéket.
Hasonlóképpen más elemeket is beillesztenek a megfelelő vödrökbe. Helyezze be az összes elemet a tömbből álló vödrökbe
Az egyes vödrök elemeit a stabil rendezési algoritmusok bármelyikével rendezik. Itt quicksort-ot (beépített funkciót) használtunk. Rendezze az elemeket az egyes vödrökbe
Az egyes vödrökből származó elemeket összegyűjtjük.
Ezt úgy végezzük, hogy iterálunk a vödörben, és minden ciklusban beillesztünk egy-egy elemet az eredeti tömbbe. Az elem a vödörből törlődik, miután átmásolta az eredeti tömbbe. Gyűjtsön elemeket minden vödörből

Vödör rendezési algoritmus

 bucketSort () hozzon létre N vödröt, amelyek mindegyikének tartalmazhat egy értéktartományt az összes vödör számára. Minden vödröt 0 értékkel inicializál az összes vödörre, ha az összes vödörbe helyezett elemet a vödrökbe sorolja, és megegyezik az összes vödör rendezési elemének tartományával. vég vödörSort

Példák Python, Java és 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); )

Bonyolultság

Legrosszabb eset komplexitás: Ha a tömbben közeli hatótávolságú elemek találhatók, akkor valószínűleg ugyanabba a vödörbe kerülnek. Ez azt eredményezheti, hogy egyes vödrök több elemet tartalmaznak, mint mások. A bonyolultságot a vödör elemeinek rendezéséhez használt rendezési algoritmustól teszi függővé. A komplexitás még rosszabbá válik, ha az elemek fordított sorrendben vannak. Ha a beszúrási rendezést használják a vödör elemeinek rendezésére, akkor az idő bonyolultsága válik .O(n²)

O(n²)
Legjobb bonyolultság: O(n+k)
Akkor fordul elő, ha az elemek egyenletesen oszlanak el a vödrökben, és mindegyik vödörben közel azonos számú elem található.
A komplexitás még jobbá válik, ha a vödrök belsejében lévő elemek már rendezve vannak.
Ha a beszúrási rendezést használják a vödör elemeinek rendezésére, akkor a teljes komplexitás a legjobb esetben lineáris lesz, azaz. O(n+k). O(n)a vödrök készítésének bonyolultsága és a vödör O(k)elemeinek válogatásának bonyolultsága a legjobb esetben lineáris időbonyolultságú algoritmusokkal.
Átlagos esetösszetétel: O(n)
Akkor fordul elő, amikor az elemeket véletlenszerűen osztják el a tömbben. Még akkor is, ha az elemek nincsenek egyenletesen elosztva, a sorrend rendezése lineáris időben fut. Addig igaz, amíg a vödörméretek négyzetének összege lineáris az elemek összes számában.