Kibirų rūšiavimo algoritmas

Šioje pamokoje sužinosite, kaip veikia kibirų rūšiavimas. Be to, rasite darbinių grupių rūšiavimo pavyzdžių C, C ++, Java ir Python.

„Bucket Sort“ yra rūšiavimo technika, rūšiuojanti elementus, pirmiausia padalijant elementus į kelias grupes, vadinamas kibirais . Kiekvieno segmento elementai yra rūšiuojami naudojant bet kurį tinkamą rūšiavimo algoritmą arba rekursyviai iškviečiant tą patį algoritmą.

Sukuriami keli kibirai. Kiekvienas kibiras užpildytas tam tikru elementų diapazonu. Elementai kibiro viduje yra rūšiuojami naudojant bet kurį kitą algoritmą. Galiausiai surenkami masyvo elementai.

Kibirų rūšiavimo procesą galima suprasti kaip sklaidos surinkimo metodą. Pirmiausia elementai išskirstomi į kaušus, tada jų elementai yra rūšiuojami. Galiausiai elementai surenkami eilės tvarka.

Kibirų rūšiavimo darbas

Kaip veikia kibirų rūšiavimas?

Tarkime, įvesties masyvas yra: Įvesties masyvas
Sukurkite 10 dydžio masyvą. Kiekvienas šio masyvo lizdas naudojamas kaip elementų saugojimo grupė. Masyvas, kuriame kiekviena padėtis yra kibiras
Įdėkite elementus į masyvo grupes. Elementai įterpiami atsižvelgiant į kaušo diapazoną.
Mūsų pavyzdiniame kode turime grupes, kurių kiekvienas svyruoja nuo 0 iki 1, nuo 1 iki 2, nuo 2 iki 3,… (n-1) iki n.
Tarkime, .23imamas įvesties elementas . Jis padauginamas iš size = 10(t. Y. .23*10=2.3). Tada jis paverčiamas sveikuoju skaičiumi (t. Y. 2.3≈2). Galiausiai .23 įkišamas į kibirą-2 . Įstatykite elementus į masyvo
rinkinius. Panašiai į tą patį kibirą įterpiama .25. Kiekvieną kartą imama slankiojo kablelio skaičiaus žemiausia vertė.
Jei imsime sveikų skaičių skaičius, turime jį padalyti iš intervalo (čia 10), kad gautume žemiausią vertę.
Panašiai į kitus jų elementus įterpiami ir kiti elementai. Įdėkite visus elementus į masyvo grupes
Kiekvieno segmento elementai yra rūšiuojami naudojant bet kurį iš stabilių rūšiavimo algoritmų. Čia mes naudojome „quicksort“ (integruota funkcija). Rūšiuoti elementus kiekviename segmente
Surenkami elementai iš kiekvieno kibiro.
Tai daroma kartojant per kibirą ir kiekvieno ciklo metu įterpiant atskirą elementą į pradinę masyvą. Elementas iš grupės ištrinamas, kai jis nukopijuojamas į pradinį masyvą. Surinkite elementus iš kiekvieno kibiro

Kibirų rūšiavimo algoritmas

 „bucketSort“ () sukuria N grupes, kurių kiekvienoje gali būti visų segmentų reikšmių diapazonas. Kiekvieną grupę inicijuokite 0 reikšmių visiems segmentams, įdėtiems elementams į grupes, atitinkančias visų kiekvieno segmentų rūšiavimo elementų diapazoną. pabaigos kibiras Rūšiuoti

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

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

Sudėtingumas

Blogiausio atvejo sudėtingumas: kai masyve yra artimo nuotolio elementų, jie greičiausiai bus dedami į tą patį kibirą. Dėl to kai kuriuose segmentuose gali būti daugiau elementų nei kituose. Dėl to sudėtingumas priklauso nuo rūšiavimo algoritmo, naudojamo rūšiuoti segmento elementus. Sudėtingumas tampa dar blogesnis, kai elementai yra atvirkštine tvarka. Jei įterpimo rūšiavimas naudojamas rūšiuoti segmento elementus, laiko sudėtingumas tampa didesnis .O(n²)

O(n²)
Geriausio atvejo sudėtingumas: O(n+k)
tai įvyksta, kai elementai yra tolygiai pasiskirstę grupėse, o kiekvienoje grupėje yra beveik vienodas elementų skaičius.
Sudėtingumas tampa dar geresnis, jei elementai kibiruose jau yra rūšiuojami.
Jei rūšiuoti kibiro elementus naudojama įterpimo rūšiavimas, tai geriausiu atveju bendras sudėtingumas bus tiesinis, t. O(n+k). O(n)yra sudėtingumas kuriant kaušus ir O(k)yra sudėtingas rūšiuoti segmento elementus naudojant algoritmus, kurių geriausiu atveju laiko trukmė yra sudėtinga.
Vidutinis atvejų sudėtingumas: O(n)
Tai įvyksta, kai elementai masyve paskirstomi atsitiktinai. Net jei elementai nėra pasiskirstę tolygiai, grupių rūšiavimas vyksta linijiniu laiku. Tai galioja tol, kol kibirų dydžių kvadratų suma yra tiesinė visame elementų skaičiuje.