Algoritmus triedenia segmentov

V tomto výučbe sa dozviete, ako funguje triedenie segmentov. Nájdete tiež pracovné príklady triedenia segmentov v jazykoch C, C ++, Java a Python.

Bucket Sort je technika triedenia, pri ktorej sa prvky triedia tak, že sa najskôr prvky rozdelia do niekoľkých skupín, ktoré sa nazývajú lopaty . Prvky vo vnútri každého segmentu sú triedené pomocou ktoréhokoľvek z vhodných algoritmov triedenia alebo rekurzívne volajúcich ten istý algoritmus.

Je vytvorených niekoľko vedier. Každé vedro je naplnené konkrétnym rozsahom prvkov. Prvky vo vnútri vedra sú triedené pomocou iného algoritmu. Nakoniec sa prvky vedra zhromaždia, aby sa získalo zoradené pole.

Proces triedenia segmentov možno chápať ako prístup rozptýleného zhromažďovania . Prvky sa najskôr rozptýlia do segmentov a potom sa prvky segmentov roztriedia. Nakoniec sa prvky zhromaždia v poradí.

Práca na triedení lopaty

Ako funguje triedenie vedra?

Predpokladajme, že vstupné pole je: Vstupné pole
Vytvorte pole o veľkosti 10. Každý slot tohto poľa sa používa ako segment na ukladanie prvkov. Pole, v ktorom je v každej polohe vedro
Vložte prvky do vedier z poľa. Prvky sa vkladajú podľa rozsahu vedra.
V našom príklade kódu máme segmenty každé z rozsahov od 0 do 1, 1 až 2, 2 až 3,… (n-1) až n.
Predpokladajme, že .23sa vezme vstupný prvok . Vynásobí sa size = 10(tj. .23*10=2.3). Potom sa prevedie na celé číslo (tj. 2.3≈2). Nakoniec sa do vedra-2 vloží 0,23 . Vložte prvky do vedier z poľa
Podobne sa do toho istého vedra vkladá aj 0,25. Zakaždým sa vezme minimálna hodnota čísla s pohyblivou rádovou čiarkou.
Ak vezmeme celé číslo ako vstup, musíme ho vydeliť intervalom (10 tu), aby sme dostali minimálnu hodnotu.
Podobne sú vložené ďalšie prvky do príslušných vedier. Vložte všetky prvky do vedier z poľa
Prvky každého segmentu sa triedia pomocou ktoréhokoľvek zo stabilných algoritmov triedenia. Tu sme použili quicksort (zabudovaná funkcia). Zoraďte prvky v každom segmente
Prvky z každého vedra sa zhromaždia.
Robí sa to iteráciou cez vedro a vložením jednotlivého prvku do pôvodného poľa v každom cykle. Prvok z vedra sa vymaže, keď sa skopíruje do pôvodného poľa. Zhromaždite prvky z každého vedra

Algoritmus triedenia segmentov

 bucketSort () vytvorte N vedier, z ktorých každý môže obsahovať rozsah hodnôt pre všetky vedrá, inicializuje každý vedierko s 0 hodnotami pre všetky vedrá vložené prvky do vedier zodpovedajúce rozsahu pre všetky vedrá triediace prvky v každom vedre zhromažďujú prvky z každého vedra koncové vedroSort

Príklady jazyka Python, Java a 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); )

Zložitosť

Najhoršia zložitosť: Ak sú v poli prvky blízkeho dosahu, je pravdepodobné, že budú umiestnené v rovnakom vedre. To môže mať za následok, že niektoré segmenty budú mať väčší počet prvkov ako iné. To robí závislosť zložitosti na algoritme triedenia použitom na triedenie prvkov vedra. Zložitosť sa ešte zhorší, ak sú prvky v opačnom poradí. Ak sa na triedenie prvkov vedra použije triedenie vloženia, stane sa časová zložitosť .O(n²)

O(n²)
Najlepšia zložitosť prípadu: O(n+k)
Nastáva, keď sú prvky rovnomerne rozložené vo vedrách s takmer rovnakým počtom prvkov v každom vedre.
Zložitosť sa stáva ešte lepšou, ak sú prvky vo vnútri segmentov už zoradené.
Ak sa na triedenie prvkov vedra použije triedenie vloženia, bude celková zložitosť v najlepšom prípade lineárna, tj. O(n+k). O(n)je zložitosť na výrobu segmentov a O(k)je to zložitosť na triedenie prvkov segmentu pomocou algoritmov, ktoré majú v najlepšom prípade lineárnu časovú zložitosť.
Priemerná zložitosť prípadu: O(n)
Nastáva, keď sú prvky v poli rozmiestnené náhodne. Aj keď prvky nie sú distribuované rovnomerne, triedenie segmentov prebieha v lineárnom čase. Platí to, kým súčet štvorcov veľkostí vedra nie je lineárny v celkovom počte prvkov.