Algoritem razvrščanja v vedrih

V tej vadnici boste izvedeli, kako deluje razvrščanje v vedrih. Prav tako boste našli delujoče primere razvrščanja v vedrih v C, C ++, Java in Python.

Razvrstitev v vedrih je tehnika razvrščanja, ki razvrsti elemente tako, da jih najprej razdeli v več skupin, imenovanih vedra . Elementi znotraj vsakega vedra so razvrščeni z uporabo katerega koli ustreznega algoritma za razvrščanje ali rekurzivno kličejo isti algoritem.

Ustvari se več veder. Vsako vedro je napolnjeno z določeno paleto elementov. Elementi v vedru so razvrščeni po katerem koli drugem algoritmu. Na koncu se zberejo elementi vedra, da se dobi razvrščeno polje.

Postopek razvrščanja v vedrih lahko razumemo kot pristop razprševanja . Elementi se najprej razpršijo v vedra, nato pa razvrstijo elemente veder. Na koncu so elementi zbrani po vrsti.

Delovanje sorte žlice

Kako deluje razvrščanje žlice?

  1. Recimo, da je vhodno polje: Vhodno polje
    Ustvari polje velikosti 10. Vsaka reža tega polja se uporablja kot vedro za shranjevanje elementov. Polje, v katerem je vsak položaj vedro
  2. V vede iz matrike vstavite elemente. Elementi se vstavijo glede na obseg žlice.
    V naši vzorčni kodi imamo segmente v območju od 0 do 1, 1 do 2, 2 do 3,… (n-1) do n.
    Recimo, da .23je vzet vhodni element . Pomnoži se z size = 10(tj. .23*10=2.3). Nato se pretvori v celo število (tj. 2.3≈2). Na koncu se v vedro-2 vstavi .23 . Vstavljanje elementov v vedra iz polja
    Podobno se v isti vedro vstavi tudi .25. Vsakokrat se vzame talna vrednost števila s plavajočo vejico.
    Če za vhod vzamemo cela števila, ga moramo razdeliti z intervalom (tukaj 10), da dobimo talno vrednost.
    Podobno so drugi elementi vstavljeni v ustrezna vedra. Vse elemente vstavite v vedra iz polja
  3. Elementi vsakega vedra so razvrščeni z uporabo katerega koli stabilnega algoritma za razvrščanje. Tu smo uporabili hitri razpored (vgrajena funkcija). Razvrsti elemente v vsakem vedru
  4. Zbrani so elementi iz vsakega vedra.
    To se naredi s ponovitvijo skozi vedro in vstavitvijo posameznega elementa v prvotno polje v vsakem ciklu. Element iz vedra se izbriše, ko je kopiran v izvirno matriko. Zberite elemente iz vsakega vedra

Algoritem razvrščanja v vedrih

 bucketSort () ustvari N vedrov, od katerih lahko vsak vsebuje obseg vrednosti za vsa vedra, inicializira vsako vedro z 0 vrednostmi za vsa vedra, vstavi elemente v vedra, ki ustrezajo obsegu za vsa vedra, razvrsti elemente v vsakem vedru, zbere elemente iz vsakega vedra končno vedroSort

Primeri Python, Java in 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); )

Kompleksnost

  • Najslabša zapletenost: Če so v matriki elementi iz neposredne bližine, bodo verjetno postavljeni v isto vedro. To lahko povzroči, da imajo nekateri segmenti več elementov kot drugi. Zapletenost je odvisna od algoritma za razvrščanje, ki se uporablja za razvrščanje elementov segmenta. Zapletenost se še poslabša, če so elementi v obratnem vrstnem redu. Če se sortiranje vstavljanja uporablja za razvrščanje elementov vedra, potem postane časovna zapletenost .O(n2)

    O(n2)
  • Najboljša zapletenost: O(n+k)
    Do tega pride, kadar so elementi enakomerno razporejeni v vedrih s skoraj enakim številom elementov v vsakem vedru.
    Zapletenost postane še boljša, če so elementi v vedrih že razvrščeni.
    Če se sortiranje vstavljanja uporablja za razvrščanje elementov vedra, bo celotna zapletenost v najboljšem primeru linearna, tj. O(n+k). O(n)je zapletenost izdelave veder in O(k)zapletenost razvrščanja elementov vedra z uporabo algoritmov, ki imajo v najboljšem primeru linearno časovno zapletenost.
  • Povprečna zapletenost primerov: O(n)
    Pojavi se, ko so elementi naključno razporejeni v matriki. Tudi če elementi niso enakomerno porazdeljeni, razvrščanje vedrov poteka v linearnem času. Velja, dokler vsota kvadratov velikosti žlice ni linearna v skupnem številu elementov.

Aplikacije za razvrščanje v vedrih

Razvrščanje v vedrih se uporablja, kadar:

  • vhod je enakomerno porazdeljen v obsegu.
  • obstajajo vrednosti s plavajočo vejico

Zanimive Članki...