Kausa šķirošanas algoritms

Šajā apmācībā jūs uzzināsiet, kā darbojas kausu šķirošana. Jūs atradīsit arī praktiskus spaiļu kārtošanas piemērus C, C ++, Java un Python.

Bucket Sort ir šķirošanas paņēmiens, kas kārto elementus, vispirms sadalot elementus vairākās grupās, ko sauc par spaiņiem . Katrā segmentā esošie elementi tiek sakārtoti, izmantojot jebkuru no piemērotajiem šķirošanas algoritmiem vai rekursīvi izsaucot to pašu algoritmu.

Tiek izveidoti vairāki spaiņi. Katrs kauss ir piepildīts ar noteiktu elementu klāstu. Spaiņa iekšpusē esošie elementi tiek kārtoti, izmantojot jebkuru citu algoritmu. Visbeidzot, kausa elementi tiek apkopoti, lai iegūtu sakārtotu masīvu.

Kausu šķirošanas procesu var saprast kā pieeju izkliedēšanai un savākšanai . Elementi vispirms tiek izkaisīti spaiņos, pēc tam kausu elementi tiek sakārtoti. Visbeidzot, elementi tiek apkopoti secībā.

Kausa kārtošanas darbs

Kā darbojas kausa kārtošana?

Pieņemsim, ka ievades masīvs ir: Ievades masīvs
Izveidojiet masīvu 10 izmēru. Katrs šī masīva slots tiek izmantots kā spainis elementu glabāšanai. Masīvs, kurā katra pozīcija ir spainis
Ievietojiet elementus masīva spaiņos. Elementi tiek ievietoti atbilstoši kausa diapazonam.
Mūsu koda piemērā mums ir diapazoni no 0 līdz 1, 1 līdz 2, 2 līdz 3,… (n-1) līdz n.
Pieņemsim, ka .23tiek ņemts ievades elements . Tas tiek reizināts ar size = 10(ti. .23*10=2.3). Tad tas tiek pārvērsts par veselu skaitli (ti. 2.3≈2). Visbeidzot, .23 ievieto spainī-2 . Ievietojiet elementus masīvā no masīva.
Tajā pašā spainī ievieto arī .25. Katru reizi tiek ņemta peldošā komata skaitļa zemākā vērtība.
Ja kā ievadi ņemam veselus skaitļus, mums tas jāsadala ar intervālu (šeit 10), lai iegūtu zemāko vērtību.
Līdzīgi arī citi elementi tiek ievietoti to attiecīgajos segmentos. Ievietojiet visus elementus masīva spaiņos
Katra segmenta elementi tiek sakārtoti, izmantojot jebkuru no stabilās šķirošanas algoritmiem. Šeit mēs izmantojām quicksort (iebūvēta funkcija). Kārtojiet elementus katrā spainī
No katra kausa elementi ir apkopoti.
To veic, atkārtojot caur spaini un katrā ciklā ievietojot atsevišķu elementu sākotnējā masīvā. Elements no spaiņa tiek izdzēsts, kad tas ir nokopēts sākotnējā masīvā. Savāc elementus no katra spaiņa

Kausa šķirošanas algoritms

 bucketSort () izveido N kausus, no kuriem katrs var saturēt visu diapazonu vērtību diapazonu, inicializējiet katru kausu ar 0 vērtībām visām spainēm, kas ievietotas elementos spaiņos, kas atbilst diapazonam visiem katrā segmentā esošajiem kausu šķirošanas elementiem. beigu kaussSort

Python, Java un C / C ++ piemēri

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

Sarežģītība

Sliktākā gadījuma sarežģītība: ja masīvā ir tuva diapazona elementi, visticamāk, tie tiks ievietoti vienā spainī. Tā rezultātā dažās grupās var būt vairāk elementu nekā citās. Tas padara sarežģītību atkarīgu no šķirošanas algoritma, ko izmanto, lai kārtotu spaiņa elementus. Sarežģītība kļūst vēl sliktāka, ja elementi atrodas apgrieztā secībā. Ja segmenta elementu kārtošanai tiek izmantota ievietošanas kārtošana, laika sarežģītība kļūst lielāka .O(n²)

O(n²)
Labākā gadījuma sarežģītība: O(n+k)
tā notiek, ja elementi ir vienmērīgi sadalīti spaiņos ar gandrīz vienādu elementu skaitu katrā spainī.
Sarežģītība kļūst vēl labāka, ja elementi spaiņos jau ir sakārtoti.
Ja ievietošanas kārtojumu izmanto, lai kārtotu kausa elementus, tad kopējā sarežģītība labākajā gadījumā būs lineāra, ti. O(n+k). O(n)ir sarežģītība kausu izgatavošanā un O(k)sarežģītība kausa elementu šķirošanā, izmantojot algoritmus, kuriem labākajā gadījumā ir lineāra laika sarežģītība.
Vidējā gadījuma sarežģītība: O(n)
tā notiek, ja elementi masīvā tiek sadalīti nejauši. Pat ja elementi nav vienmērīgi sadalīti, segmentu kārtošana notiek lineārā laikā. Tas ir spēkā līdz brīdim, kad kausu izmēru kvadrātu summa ir lineāra kopējā elementu skaitā.