Ämbrisorteerimise algoritm

Selles õpetuses saate teada, kuidas ämbrite sortimine töötab. Samuti leiate toimivaid näiteid ämbrite sortimisest C, C ++, Java ja Python.

Bucket Sort on sortimistehnika, mis sorteerib elemendid, jagades elemendid kõigepealt mitmeks rühmaks, mida nimetatakse ämbriteks . Igas ämbris olevad elemendid sorteeritakse mis tahes sobiva sorteerimisalgoritmi abil või kutsutakse rekursiivselt sama algoritmi.

Luuakse mitu ämbrit. Iga ämber on täidetud kindla valiku elementidega. Kopa sees olevad elemendid sorteeritakse mis tahes muu algoritmi abil. Lõpuks kogutakse massi elemendid sorteeritud massiivi saamiseks.

Ämbrisorteerimise protsessi võib mõista hajutamise-kogumise lähenemisena. Elemendid hajutatakse kõigepealt ämbritesse, seejärel sorteeritakse ämbrite elemendid. Lõpuks on elemendid järjestatud.

Bucket Sort töötab

Kuidas koppide sortimine töötab?

Oletame, et sisendmassiiv on järgmine: Sisendimassiiv
Loo massiivi suurusega 10. Selle massiivi iga pesa kasutatakse elementide salvestamiseks ämbrina. Massiiv, milles iga positsioon on ämber
Sisestage elemendid massiivi ämbritesse. Elemendid sisestatakse vastavalt kopa ulatusele.
Näitekoodis on meil ämbrid vahemikus 0 kuni 1, 1 kuni 2, 2 kuni 3,… (n-1) kuni n.
Oletame, et võetakse sisendelement .23. See korrutatakse size = 10(st. .23*10=2.3). Seejärel teisendatakse see täisarvuks (st. 2.3≈2). Lõpuks sisestatakse ämber-2 .23 . Sisestage elemendid massiivi ämbritesse.
Samamoodi lisatakse samasse ämbrisse .25. Igal ajal võetakse ujuva punkti numbri põhiväärtus.
Kui võtame sisendiks täisarvud, peame põranda väärtuse saamiseks jagama selle intervalliga (siin 10).
Samamoodi sisestatakse muud elemendid nende vastavatesse ämbritesse. Sisestage kõik elemendid massiivi ämbritesse
Iga ämbri elemendid sorteeritakse mis tahes stabiilse sorteerimise algoritmi abil. Siin oleme kasutanud kiirsorti (sisseehitatud funktsioon). Sorteerige elemendid igas ämbris
Igast ämbrist elemendid on kokku kogutud.
Seda tehakse itereerides läbi ämbri ja sisestades igas tsüklis eraldi elemendi algsesse massiivi. Element massiivist kustutatakse, kui see on algsesse massiivi kopeeritud. Koguge elemendid igast ämbrist

Ämbrisorteerimise algoritm

 bucketSort () looge N ämbrit, millest igaühes saab olla kõigi ämbrite väärtuste vahemik, lähtestage iga ämber 0 väärtusega kõigile ämbritele, pane elemendid ämbritesse, mis vastavad vahemikus kõigile ämbrite sortimiselementidele igas ämbris lõpuämberSorteeri

Pythoni, Java ja C / C ++ näited

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

Keerukus

Halvima juhtumi keerukus: kui massiivis on lähedalasuvaid elemente, paigutatakse need tõenäoliselt samasse ämbrisse. Selle tulemuseks võib olla, et mõnes ämbris on rohkem elemente kui teistes. See paneb keerukuse sõltuma sorteerimisalgoritmist, mida kasutatakse kopa elementide sortimiseks. Keerukus muutub veelgi hullemaks, kui elemendid on vastupidises järjekorras. Kui ämber elementide sortimiseks kasutatakse sisestussorteerimist, muutub aja keerukus .O(n²)

O(n²)
Parima juhtumi keerukus: O(n+k)
see juhtub siis, kui elemendid on ühtlaselt jaotatud ämbritesse ja igas ämbris on peaaegu võrdne arv elemente.
Keerukus muutub veelgi paremaks, kui ämbrite sees olevad elemendid on juba sorteeritud.
Kui kopa elementide sorteerimiseks kasutatakse sisestussorteerimist, on üldine keerukus parimal juhul lineaarne, st. O(n+k). O(n)on ämbrite valmistamise O(k)keerukus ja ämber elementide sorteerimise keerukus algoritmide abil, millel on parimal juhul lineaarne ajakeerukus.
Keskmine juhtumi keerukus: O(n)
see juhtub siis, kui elemendid jaotatakse massiivis juhuslikult. Isegi kui elemendid pole jaotatud ühtlaselt, jookseb ämbrite sortimine lineaarse ajaga. See kehtib seni, kuni ämber suuruste ruutude summa on elementide koguarvus lineaarne.