В тази статия ще обсъдим алгоритъма за сортиране на кофа. Елементите с данни в сортирането на кофи се разпределят под формата на кофи. При програмиране или технически интервюта за софтуерни инженери алгоритмите за сортиране се задават широко. Така че е важно да обсъдим темата.
Bucket sort е алгоритъм за сортиране, който разделя елементите на множество групи, наречени кофи. Елементите при сортиране в кофа първо се разделят равномерно на групи, наречени кофи, и след това се сортират от всеки друг алгоритъм за сортиране. След това елементите се събират по сортиран начин.
Основната процедура за извършване на сортиране на кофа е дадена, както следва -
- Първо, разделете диапазона на фиксиран брой кофи.
- След това хвърлете всеки елемент в съответната кофа.
- След това сортирайте всяка кофа поотделно, като приложите алгоритъм за сортиране.
- И накрая, свържете всички сортирани кофи.
Предимствата на сортирането с кофи са -
- Сортирането на кофата намалява бр. на сравнения.
- Той е асимптотично бърз поради равномерното разпределение на елементите.
Ограниченията на сортирането в кофата са -
- Може или не може да бъде стабилен алгоритъм за сортиране.
- Не е полезно, ако имаме голям масив, защото увеличава разходите.
- Това не е алгоритъм за сортиране на място, тъй като е необходимо допълнително място за сортиране на кофите.
Най-добрата и средна сложност на сортирането на кофа е O(n + k) , а в най-лошия случай сложността на сортирането на кофа е На2) , където н е броят на елементите.
Сортирането на кофата обикновено се използва -
- Със стойности с плаваща запетая.
- Когато входът е разпределен равномерно в диапазон.
Основната идея за извършване на сортирането на кофа е дадена, както следва -
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
Сега нека видим алгоритъма за сортиране на кофа.
Алгоритъм
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
Подход на разпръскване и събиране
Можем да разберем алгоритъма за сортиране на Bucket чрез подхода на разпръснато събиране. Тук дадените елементи първо се разпръскват в кофи. След разпръскването елементите във всяка кофа се сортират с помощта на стабилен алгоритъм за сортиране. Най-накрая сортираните елементи ще бъдат събрани в ред.
Нека вземем несортиран масив, за да разберем процеса на сортиране в кофа. Ще бъде по-лесно да разберете сортирането на кофата чрез пример.
Нека елементите на масива са -
Сега създайте кофи с диапазон от 0 до 25. Диапазонът на кофи е 0-5, 5-10, 10-15, 15-20, 20-25. Елементите се вмъкват в кофите според обхвата на кофата. Да предположим, че стойността на даден елемент е 16, така че той ще бъде вмъкнат в кофата с диапазон 15-20. По същия начин всеки елемент от масива ще се вмъкне съответно.
Известно е, че тази фаза е разсейване на елементите на масива .
Сега, вид всяка кофа поотделно. Елементите на всяка кофа могат да бъдат сортирани с помощта на някой от стабилните алгоритми за сортиране.
Най-накрая, събирам сортираните елементи от всяка кофа по ред
Сега масивът е напълно сортиран.
Сложност на сортиране на кофа
Сега нека видим времевата сложност на сортирането на кофа в най-добрия случай, средния случай и в най-лошия случай. Ще видим и пространствената сложност на сортирането на кофата.
1. Времева сложност
| Случай | време | Сложност |
|---|---|---|
| Най-добър случай | O(n + k) | |
| Среден случай | O(n + k) | |
| Най-лошия случай | На2) |
Ако използваме сортирането чрез вмъкване, за да сортираме елементите на кофата, общата сложност ще бъде линейна, т.е. O(n + k), където O(n) е за създаване на кофи, а O(k) е за сортиране на елементите на кофата използване на алгоритми с линейна времева сложност в най-добрия случай.
Най-добрият случай времева сложност на сортиране на кофа е O(n + k) .
Сложността ще се влоши, когато елементите са в обратен ред.
Най-лошият случай на времева сложност на сортирането на кофа е На2) .
2. Космическа сложност
| Космическа сложност | O(n*k) |
| Стабилен | ДА |
- Пространствената сложност на сортирането в кофа е O(n*k).
Внедряване на bucket sort
Сега нека видим програмите за сортиране на кофи в различни езици за програмиране.
програма: Напишете програма за реализиране на сортиране в кофа на език 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></=>