Bu yazımızda kova sıralama algoritmasını ele alacağız. Kova sıralamasındaki veri öğeleri, kovalar biçiminde dağıtılır. Yazılım mühendislerine yönelik kodlama veya teknik görüşmelerde sıralama algoritmaları yaygın olarak sorulmaktadır. Bu nedenle konuyu tartışmak önemlidir.
Kova sıralaması, öğeleri kova olduğu söylenen birden fazla gruba ayıran bir sıralama algoritmasıdır. Kova sıralamasındaki öğeler ilk olarak kova adı verilen gruplara eşit şekilde bölünür ve daha sonra başka herhangi bir sıralama algoritmasına göre sıralanırlar. Daha sonra elementler sıralı bir şekilde toplanır.
Kova sıralamasını gerçekleştirmenin temel prosedürü aşağıdaki şekilde verilmiştir:
- Öncelikle aralığı sabit sayıda bölüme ayırın.
- Daha sonra her öğeyi uygun kovaya atın.
- Bundan sonra, bir sıralama algoritması uygulayarak her bir kovayı ayrı ayrı sıralayın.
- Ve son olarak sıralanan tüm kovaları birleştirin.
Kova sıralamasının avantajları şunlardır:
- Kova sıralaması sayıyı azaltır. karşılaştırmalardan ibarettir.
- Elementlerin düzgün dağılımı nedeniyle asimptotik olarak hızlıdır.
Kova sıralamasının sınırlamaları şunlardır:
- Kararlı bir sıralama algoritması olabilir veya olmayabilir.
- Dizimizin geniş olması maliyeti arttırdığı için kullanışlı değildir.
- Bu yerinde bir sıralama algoritması değildir çünkü kovaları sıralamak için fazladan alan gerekir.
Kova sıralamasının en iyi ve ortalama durum karmaşıklığı O(n + k) ve kova sıralamanın en kötü durum karmaşıklığı şudur: Açık2) , Neresi N öğelerin sayısıdır.
Kova sıralaması yaygın olarak kullanılır -
- Kayan nokta değerleri ile.
- Giriş bir aralıkta eşit olarak dağıtıldığında.
Kova sıralamasını gerçekleştirmenin temel fikri şu şekilde verilmiştir:
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
Şimdi kova sıralama algoritmasını görelim.
Algoritma
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
Dağılım-toplama yaklaşımı
Bucket sort algoritmasını scatter-gather yaklaşımıyla anlayabiliriz. Burada verilen elemanlar öncelikle kovalara dağılır. Dağılımın ardından her bir gruptaki öğeler, kararlı bir sıralama algoritması kullanılarak sıralanır. Sonunda sıralanan öğeler sırayla toplanacak.
Kova sıralama sürecini anlamak için sıralanmamış bir diziyi ele alalım. Bir örnek üzerinden kova sıralamasını anlamak daha kolay olacaktır.
Dizinin elemanları şöyle olsun:
Şimdi 0 ila 25 aralığında paketler oluşturun. Paket aralıkları 0-5, 5-10, 10-15, 15-20, 20-25'tir. Elemanlar kova aralığına göre kovalara yerleştirilir. Bir öğenin değerinin 16 olduğunu varsayalım; bu durumda öğe, pakete 15-20 aralığında eklenecektir. Benzer şekilde dizinin her öğesi buna göre eklenecektir.
Bu aşama şu şekilde bilinmektedir: dizi elemanlarının saçılması .
Şimdi, düzenlemek her kova ayrı ayrı. Her bir bölümün öğeleri, kararlı sıralama algoritmalarından herhangi biri kullanılarak sıralanabilir.
Sonunda, toplamak her bir kovadaki öğelerin sırayla sıralanması
Artık dizi tamamen sıralanmıştır.
Kova sıralama karmaşıklığı
Şimdi en iyi durumda, ortalama durumda ve en kötü durumda kova sıralamanın zaman karmaşıklığını görelim. Ayrıca kova sıralamasının alan karmaşıklığını da göreceğiz.
1. Zaman Karmaşıklığı
| Dava | Zaman | Karmaşıklık |
|---|---|---|
| En iyi senaryo | O(n + k) | |
| Ortalama Durum | O(n + k) | |
| En kötü durumda | Açık2) |
Kova elemanlarını sıralamak için ekleme sıralamasını kullanırsak, genel karmaşıklık doğrusal olacaktır, yani O(n + k), burada O(n) kovaları yapmak içindir ve O(k) kova elemanlarını sıralamak içindir en iyi durumda doğrusal zaman karmaşıklığına sahip algoritmalar kullanmak.
Kova sıralamasının en iyi durum zaman karmaşıklığı şudur: O(n + k) .
Öğeler ters sırada olduğunda karmaşıklık daha da kötüleşecektir.
Kova sıralamasının en kötü zaman karmaşıklığı Açık2) .
2. Uzayın Karmaşıklığı
| Uzay Karmaşıklığı | O(n*k) |
| Stabil | EVET |
- Kova sıralamasının uzay karmaşıklığı O(n*k)'dir.
Kova sıralamasının uygulanması
Şimdi farklı programlama dillerinde kova sıralama programlarını görelim.
Program: C dilinde kova sıralamasını uygulayan bir program yazın.
#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></=>