W tym artykule omówimy algorytm sortowania kubełkowego. Elementy danych sortowane według segmentów są dystrybuowane w formie segmentów. Podczas rozmów kwalifikacyjnych związanych z kodowaniem lub technicznymi programistami często zadaje się pytanie o algorytmy sortowania. Dlatego ważne jest, aby omówić ten temat.
Sortowanie segmentowe to algorytm sortowania, który dzieli elementy na wiele grup nazywanych koszykami. Elementy w sortowaniu segmentowym są najpierw równomiernie dzielone na grupy zwane segmentami, a następnie sortowane według dowolnego innego algorytmu sortowania. Następnie elementy są gromadzone w posortowany sposób.
Podstawowa procedura sortowania kubełkowego jest następująca:
- Najpierw podziel zakres na stałą liczbę segmentów.
- Następnie wrzuć każdy element do odpowiedniego wiadra.
- Następnie posortuj każdy segment indywidualnie, stosując algorytm sortowania.
- Na koniec połącz wszystkie posortowane segmenty.
Zaletami sortowania kubełkowego są:
- Sortowanie wiaderkowe zmniejsza liczbę nie. porównań.
- Jest asymptotycznie szybki ze względu na równomierny rozkład elementów.
Ograniczenia sortowania kubełkowego są następujące:
- Może to być stabilny algorytm sortowania lub nie.
- Nie jest to przydatne, jeśli mamy dużą tablicę, ponieważ zwiększa to koszty.
- Nie jest to algorytm sortowania na miejscu, ponieważ do sortowania zasobników wymagana jest dodatkowa przestrzeń.
Najlepsza i średnia złożoność sortowania kubełkowego to O(n + k) , a najgorszym przypadkiem złożoności sortowania kubełkowego jest NA2) , Gdzie N to liczba elementów.
Powszechnie stosowane jest sortowanie kubełkowe -
- Z wartościami zmiennoprzecinkowymi.
- Gdy dane wejściowe są równomiernie rozłożone w pewnym zakresie.
Podstawową ideę sortowania kubełkowego przedstawiono w następujący sposób:
bucketSort(a[], n) 1. Create 'n' empty buckets 2. Do for each array element a[i] 2.1. Put array elements into buckets, i.e. insert a[i] into bucket[n*a[i]] 3. Sort the elements of individual buckets by using the insertion sort. 4. At last, gather or concatenate the sorted buckets. End bucketSort
Przyjrzyjmy się teraz algorytmowi sortowania kubełkowego.
Algorytm
Bucket Sort(A[]) 1. Let B[0....n-1] be a new array 2. n=length[A] 3. for i=0 to n-1 4. make B[i] an empty list 5. for i=1 to n 6. do insert A[i] into list B[n a[i]] 7. for i=0 to n-1 8. do sort list B[i] with insertion-sort 9. Concatenate lists B[0], B[1],........, B[n-1] together in order End
Metoda zbierania rozproszonego
Algorytm sortowania Bucket możemy zrozumieć poprzez podejście zbierania rozproszenia. Tutaj podane elementy są najpierw rozrzucane do wiader. Po rozproszeniu elementy w każdym segmencie są sortowane przy użyciu stabilnego algorytmu sortowania. Na koniec posortowane elementy zostaną zebrane w odpowiedniej kolejności.
Weźmy nieposortowaną tablicę, aby zrozumieć proces sortowania segmentowego. Sortowanie segmentowe będzie łatwiejsze do zrozumienia na przykładzie.
Niech elementami tablicy są -
Teraz utwórz segmenty o zakresie od 0 do 25. Zakres segmentów to 0-5, 5-10, 10-15, 15-20, 20-25. Elementy wstawiane są do czerpaków zgodnie z zakresem czerpaków. Załóżmy, że wartość elementu wynosi 16, więc zostanie on wstawiony do wiadra z zakresem 15-20. Podobnie każdy element tablicy zostanie odpowiednio wstawiony.
Wiadomo, że ta faza to tzw rozproszenie elementów tablicy .
Teraz, sortować każde wiadro osobno. Elementy każdego segmentu można sortować przy użyciu dowolnego ze stabilnych algorytmów sortowania.
W końcu, zebrać posortowane elementy z każdego segmentu w odpowiedniej kolejności
Teraz tablica jest całkowicie posortowana.
Złożoność sortowania kubełkowego
Przyjrzyjmy się teraz złożoności czasowej sortowania segmentowego w najlepszym, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną sortowania kubełkowego.
1. Złożoność czasowa
| Sprawa | Czas | Złożoność |
|---|---|---|
| Najlepszy przypadek | O(n + k) | |
| Przeciętny przypadek | O(n + k) | |
| Najgorszy przypadek | NA2) |
Jeśli użyjemy sortowania przez wstawianie do sortowania elementów kubełków, ogólna złożoność będzie liniowa, tj. O(n + k), gdzie O(n) służy do tworzenia segmentów, a O(k) służy do sortowania elementów kubełków w najlepszym przypadku stosując algorytmy o liniowej złożoności czasowej.
W najlepszym przypadku złożoność czasowa sortowania segmentowego wynosi O(n + k) .
Złożoność ulegnie pogorszeniu, gdy elementy zostaną ułożone w odwrotnej kolejności.
Najgorszy przypadek złożoności czasowej sortowania kubełkowego to NA2) .
2. Złożoność przestrzeni
| Złożoność przestrzeni | O(n*k) |
| Stabilny | TAK |
- Złożoność przestrzenna sortowania kubełkowego wynosi O(n*k).
Implementacja sortowania kubełkowego
Przyjrzyjmy się teraz programom sortowania kubełkowego w różnych językach programowania.
Program: Napisz program realizujący sortowanie kubełkowe w języku C.
#include int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) printf('%d ', a[i]); main() a[]="{54," 12, 84, 57, 69, 41, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of printf('before sorting are -
'); printarr(a, n); bucket(a, printf('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-5.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) cout< <a[i]<<' '; main() a[]="{34," 42, 74, 57, 99, 84, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of cout<<'before sorting are -
'; printarr(a, n); bucket(a, cout<<'
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-6.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C#.</p> <pre> using System; class Bucket { static int getMax(int[] a) // function to get maximum element from the given array { int n = a.Length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } static void bucket(int[] a) // function to implement bucket sort { int n = a.Length; int max = getMax(a); //max is the maximum element of array int[] bucket = new int[max+1]; for (int i = 0; i <= 10 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; static void printarr(int[] a) * function to print the array int i; n="a.Length;" (i="0;" console.write(a[i] + ' '); main() int[] a="{" 95, 50, 45, 15, 20, }; console.write('before sorting elements are -
'); printarr(a); bucket(a); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-7.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in Java.</p> <pre> public class Bucket { int getMax(int a[]) // function to get maximum element from the given array { int n = a.length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[]) // function to implement bucket sort { int n = a.length; int max = getMax(a); //max is the maximum element of array int bucket[] = new int[max+1]; for (int i = 0; i <= 9 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[]) * function to print the array int i; n="a.length;" (i="0;" system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 90, 40, 5, 15, 30, }; bucket b1="new" bucket(); system.out.print('before sorting elements are -
'); b1.printarr(a); b1.bucket(a); system.out.print('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-8.webp" alt="bucket sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. Along with the algorithm, we have also discussed the bucket sort complexity, working, and implementation in different programming languages.</p> <hr></=></pre></=></pre></=></pre></=>