Ämpäri lajittelualgoritmi

Tässä opetusohjelmassa opit, kuinka kauhalajittelu toimii. Löydät myös toimivia esimerkkejä ämpärien lajittelusta C, C ++, Java ja Python.

Ämpäri lajittelu on lajittelutekniikka, joka lajittelee elementit jakamalla elementit ensin useisiin ryhmiin, joita kutsutaan kauhoiksi . Jokaisen kauhan sisällä olevat elementit lajitellaan millä tahansa sopivalla lajittelualgoritmilla tai rekursiivisesti kutsumalla samaa algoritmia.

Luodaan useita kauhoja. Jokainen kauha on täytetty tietyllä alueella elementtejä. Kauhan sisällä olevat elementit lajitellaan millä tahansa muulla algoritmilla. Lopuksi kauhan elementit kerätään lajitellun taulukon saamiseksi.

Ämpäri-lajittelun prosessi voidaan ymmärtää hajontakokoamismenetelmänä . Elementit hajautetaan ensin kauhoihin, sitten kauhojen elementit lajitellaan. Lopuksi elementit kerätään järjestyksessä.

Työskentely Bucket Sort

Kuinka kauhalajittelu toimii?

Oletetaan, että syöttötaulukko on: Syöttötaulukko
Luo kokoinen taulukko 10. Tämän ryhmän kutakin aukkoa käytetään ämpärinä elementtien tallentamiseen. Taulukko, jossa kukin sijainti on ämpäri
Lisää elementtejä ryhmistä ryhmään. Elementit lisätään kauhan alueen mukaan.
Esimerkkikoodissamme on ämpärejä, jotka vaihtelevat välillä 0 - 1, 1 - 2, 2 - 3,… (n-1) - n.
Oletetaan, että syötetty elementti .23otetaan. Se kerrotaan size = 10(ts. .23*10=2.3). Sitten se muunnetaan kokonaisluvuksi (ts. 2.3≈2). Lopuksi .23 lisätään ämpäri-2: een . Aseta elementit kauhoihin ryhmästä.
Samoin .25 lisätään samaan kauhaan. Joka kerta otetaan liukuluvun alin arvo.
Jos otamme kokonaislukuja syötteenä, meidän on jaettava se välillä (tässä 10) saadaksesi lattia-arvon.
Samoin muut elementit lisätään vastaaviin kauhoihinsa. Aseta kaikki elementit taulukon kauhoihin
Kunkin kauhan elementit lajitellaan millä tahansa vakaan lajittelualgoritmin avulla. Tässä olemme käyttäneet pikalajitetta (sisäänrakennettu toiminto). Lajittele elementit kuhunkin ämpäriin
Elementit kustakin kauhasta kerätään.
Se tehdään iteroimalla kauhan läpi ja lisäämällä yksittäinen elementti alkuperäiseen ryhmään jokaisessa jaksossa. Elementti kauhasta poistetaan, kun se on kopioitu alkuperäiseen ryhmään. Kerää elementtejä kustakin kauhasta

Ämpäri lajittelualgoritmi

 bucketSort () luo N kauhaa, joista kussakin voi olla arvoalue kaikille ämpäreille, alustaa kukin ämpäri 0 arvolla kaikille ämpäreille, jotka laitetaan elementteihin ämpäreihin, jotka vastaavat alueita jokaisen kauhan lajitteluelementeille jokaisessa ämpäri keräävät elementit kustakin kauhasta Lajittele

Python-, Java- ja C / C ++ -esimerkkejä

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

Monimutkaisuus

Pahimman tapauksen monimutkaisuus: Kun matriisissa on lähietäisyyden elementtejä, ne todennäköisesti sijoitetaan samaan ämpäriin. Tämä voi johtaa siihen, että joissakin ryhmissä on enemmän elementtejä kuin toisissa. Se tekee monimutkaisuudesta riippuvan lajittelualgoritmista, jota käytetään kauhan elementtien lajittelussa. Monimutkaisuus pahenee entisestään, kun elementit ovat päinvastaisessa järjestyksessä. Jos lisäyslajittelua käytetään kauhan elementtien lajittelussa, aika monimutkaisuus muuttuu .O(n²)

O(n²)
Parhaan tapauksen monimutkaisuus: O(n+k)
Se tapahtuu, kun elementit jakautuvat tasaisesti kauhoihin siten, että kussakin kauhassa on lähes sama määrä elementtejä.
Monimutkaisuus paranee entisestään, jos kauhojen sisällä olevat elementit on jo lajiteltu.
Jos lisäyslajittelua käytetään kauhan elementtien lajittelussa, kokonaiskompleksisuus on parhaimmillaan lineaarinen eli. O(n+k). O(n)on monimutkaisuus kauhojen valmistuksessa ja O(k)monimutkaisuus kauhan elementtien lajittelussa käyttämällä algoritmeja, joilla on parhaimmillaan lineaarinen aikakompleksi.
Keskimääräinen tapauksen monimutkaisuus: O(n)
Se tapahtuu, kun elementit jaetaan satunnaisesti taulukossa. Vaikka elementit eivät olisikaan jakautuneet tasaisesti, ämpärilajittelu toimii lineaarisessa ajassa. Se pitää paikkansa, kunnes kauhan koon neliöiden summa on lineaarinen elementtien kokonaismäärässä.