Algoritmus třídění segmentů

V tomto tutoriálu se dozvíte, jak funguje třídění kbelíku. Pracovní příklady třídění segmentů najdete také v jazycích C, C ++, Java a Python.

Bucket Sort je technika třídění, která třídí prvky tak, že nejprve rozdělíte prvky do několika skupin zvaných kbelíky . Prvky uvnitř každého segmentu jsou tříděny pomocí libovolného vhodného třídicího algoritmu nebo rekurzivně volajícího stejného algoritmu.

Je vytvořeno několik segmentů. Každý kbelík je naplněn specifickým rozsahem prvků. Prvky uvnitř kbelíku jsou tříděny pomocí jakéhokoli jiného algoritmu. Nakonec se prvky kbelíku shromáždí, aby se získalo seřazené pole.

Proces třídění kbelíku lze chápat jako přístup scatter-collect . Prvky jsou nejprve rozptýleny do segmentů, poté jsou prvky segmentů roztříděny. Nakonec jsou prvky shromážděny v pořádku.

Fungování třídění lopaty

Jak funguje třídění segmentů?

Předpokládejme, že vstupní pole je: Vstupní pole
Vytvořte pole o velikosti 10. Každý slot tohoto pole se používá jako kbelík pro ukládání prvků. Pole, ve kterém je v každé poloze kbelík
Vložte prvky do kbelíků z pole. Prvky se vkládají podle rozsahu lopaty.
V našem příkladovém kódu máme kbelíky každé z rozsahů od 0 do 1, 1 až 2, 2 až 3,… (n-1) až n.
Předpokládejme, že .23je převzat vstupní prvek . Vynásobí se size = 10(tj. .23*10=2.3). Poté se převede na celé číslo (tj. 2.3≈2). Nakonec se do kbelíku 2 vloží 0,23 . Vložte prvky do kbelíků z pole
Podobně se do stejného kbelíku vloží 0,25. Pokaždé se vezme minimální hodnota čísla s plovoucí desetinnou čárkou.
Vezmeme-li jako vstup celočíselná čísla, musíme ji vydělit intervalem (zde 10), abychom získali minimální hodnotu.
Podobně jsou do příslušných kbelíků vloženy další prvky. Vložte všechny prvky do kbelíků z pole
Prvky každého segmentu jsou tříděny pomocí některého ze stabilních třídicích algoritmů. Zde jsme použili quicksort (vestavěná funkce). Seřaďte prvky v každém kbelíku
Sbírají se prvky z každého kbelíku.
Provádí se iterací v kbelíku a vložením jednotlivého prvku do původního pole v každém cyklu. Prvek z kbelíku je vymazán, jakmile je zkopírován do původního pole. Shromážděte prvky z každého kbelíku

Algoritmus třídění segmentů

 bucketSort () create N buckets each of which can hold a range of values for all the bucks initialize each bucket with 0 values for all the bucks put elements into buckets matching the range for all the buckets sort elements in each bucket collect elements from each bucket konec kbelíku

Python, Java a C / C ++ příklady

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

Složitost

Složitost nejhoršího případu: Pokud jsou v poli prvky blízkého dosahu, je pravděpodobné, že budou umístěny do stejného kbelíku. To může mít za následek, že některé segmenty budou mít větší počet prvků než jiné. Díky tomu je složitost závislá na třídícím algoritmu použitém k třídění prvků kbelíku. Složitost se ještě zhorší, když jsou prvky v opačném pořadí. Pokud se pro třídění prvků segmentu používá třídění vložení, stane se časová složitost .O(n²)

O(n²)
Nejlepší složitost případu: O(n+k)
Dochází k němu, když jsou prvky rovnoměrně rozloženy v segmentech s téměř stejným počtem prvků v každém segmentu.
Složitost se stává ještě lepší, pokud jsou prvky uvnitř segmentů již seřazeny.
Pokud se pro třídění prvků kbelíku používá třídění vložení, bude celková složitost v nejlepším případě lineární, tj. O(n+k). O(n)je složitost pro výrobu segmentů a O(k)je složitost pro třídění prvků segmentu pomocí algoritmů, které mají v nejlepším případě lineární časovou složitost.
Průměrná složitost případu: O(n)
Dochází k němu, když jsou prvky náhodně distribuovány v poli. I když prvky nejsou distribuovány rovnoměrně, třídění segmentů probíhá v lineárním čase. Platí, dokud součet čtverců velikostí kbelíku není lineární v celkovém počtu prvků.