Algorytm sortowania wiader

W tym samouczku dowiesz się, jak działa sortowanie zbiorcze. Znajdziesz także działające przykłady sortowania kubełkowego w C, C ++, Javie i Pythonie.

Bucket Sort to technika sortowania, która sortuje elementy, najpierw dzieląc je na kilka grup zwanych zasobnikami . Elementy w każdym zasobniku są sortowane przy użyciu dowolnego odpowiedniego algorytmu sortowania lub rekurencyjnie wywołującego ten sam algorytm.

Tworzonych jest kilka zasobników. Każde wiadro jest wypełnione określoną gamą elementów. Elementy wewnątrz wiadra są sortowane przy użyciu dowolnego innego algorytmu. Na koniec elementy wiadra są zbierane, aby uzyskać posortowaną tablicę.

Proces sortowania kubełkowego można rozumieć jako podejście typu scatter-collect . Elementy są najpierw rozrzucane do wiader, a następnie sortowane. Wreszcie elementy są gromadzone w porządku.

Praca w trybie Bucket Sort

Jak działa sortowanie zbiorcze?

Załóżmy, że tablica wejściowa to: Tablica wejściowa
Utwórz tablicę o rozmiarze 10. Każde gniazdo tej tablicy jest używane jako zasobnik do przechowywania elementów. Tablica, w której każda pozycja jest zasobnikiem
Wstaw elementy do segmentów z tablicy. Elementy są wstawiane zgodnie z zakresem wiadra.
W naszym przykładowym kodzie mamy przedziały z zakresu od 0 do 1, od 1 do 2, od 2 do 3,… (n-1) do n.
Załóżmy, że .23brany jest element wejściowy . Jest mnożony przez size = 10(tj. .23*10=2.3). Następnie jest konwertowany na liczbę całkowitą (tj. 2.3≈2). Na koniec 0,23 jest wkładany do wiadra-2 . Wstawianie elementów do koszyków z tablicy
Podobnie, 0,25 jest również wstawiane do tego samego segmentu. Za każdym razem przyjmowana jest wartość dolna liczby zmiennoprzecinkowej.
Jeśli weźmiemy liczby całkowite jako dane wejściowe, musimy podzielić je przez przedział (tutaj 10), aby uzyskać wartość dolną.
Podobnie inne elementy są wstawiane do odpowiednich pojemników. Wstaw wszystkie elementy do segmentów z tablicy
Elementy każdego wiadra są sortowane przy użyciu dowolnego ze stabilnych algorytmów sortowania. Tutaj użyliśmy quicksort (wbudowana funkcja). Posortuj elementy w każdym wiadrze
Zbierane są elementy z każdego wiadra.
Odbywa się to poprzez iterację w zasobniku i wstawianie pojedynczego elementu do oryginalnej tablicy w każdym cyklu. Element z zasobnika jest usuwany po skopiowaniu do oryginalnej tablicy. Zbierz elementy z każdego wiadra

Algorytm sortowania wiader

 bucketSort () tworzy N zasobników, z których każdy może pomieścić zakres wartości dla wszystkich zasobników inicjuje każdy zasobnik z wartościami 0 dla wszystkich zasobników, umieszcza elementy w zasobnikach pasujących do zakresu dla wszystkich zasobników sortuj elementy w każdym zasobniku zbiera elementy z każdego zasobnika koniec łyżki

Przykłady w Pythonie, Javie i 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); )

Złożoność

Złożoność najgorszego przypadku: gdy w tablicy znajdują się elementy bliskiego zasięgu, prawdopodobnie zostaną one umieszczone w tym samym segmencie. Może to spowodować, że niektóre zasobniki będą miały więcej elementów niż inne. To sprawia, że złożoność zależy od algorytmu sortowania używanego do sortowania elementów wiadra. Złożoność staje się jeszcze gorsza, gdy elementy są w odwrotnej kolejności. Jeśli sortowanie przez wstawianie jest używane do sortowania elementów zasobnika, wtedy staje się złożoność czasowa .O(n²)

O(n²)
Złożoność najlepszego przypadku: O(n+k)
Występuje, gdy elementy są równomiernie rozmieszczone w segmentach z prawie taką samą liczbą elementów w każdym segmencie.
Złożoność staje się jeszcze lepsza, jeśli elementy wewnątrz kubełków są już posortowane.
Jeśli sortowanie przez wstawianie jest używane do sortowania elementów zasobnika, wówczas ogólna złożoność w najlepszym przypadku będzie liniowa, tj. O(n+k). O(n)to złożoność tworzenia wiader i O(k)złożoność sortowania elementów wiadra przy użyciu algorytmów o liniowej złożoności czasowej w najlepszym przypadku.
Średnia złożoność przypadku: O(n)
występuje, gdy elementy są rozmieszczone losowo w tablicy. Nawet jeśli elementy nie są rozmieszczone równomiernie, sortowanie kubełkowe przebiega w czasie liniowym. To prawda, dopóki suma kwadratów rozmiarów wiadra nie jest liniowa względem całkowitej liczby elementów.