Bu yazımızda Radix sıralama algoritmasını tartışacağız. Radix sıralaması, tamsayılar için kullanılan doğrusal sıralama algoritmasıdır. Radix sıralamada en az anlamlı basamaktan başlayarak en anlamlı basamağa doğru basamak basamak sıralama yapılır.
Taban sıralama işlemi, öğrenci adlarının alfabetik sıraya göre sıralanmasına benzer şekilde çalışır. Bu durumda İngilizce'deki 26 alfabeden dolayı oluşan 26 taban vardır. İlk geçişte öğrencilerin isimleri, isimlerinin ilk harfine göre büyükten küçüğe doğru gruplandırılır. Daha sonra ikinci geçişte isimler, isimlerinin ikinci harfine göre artan sıraya göre gruplandırılır. Ve sıralanmış listeyi bulana kadar süreç devam ediyor.
dar açı
Şimdi Radix sıralama algoritmasını görelim.
Algoritma
radixSort(arr) max = largest element in the given array d = number of digits in the largest element (or, max) Now, create d buckets of size 0 - 9 for i -> 0 to d sort the array elements using counting sort (or any stable sort) according to the digits at the ith place
Radix sıralama algoritmasının çalışması
Şimdi Radix sıralama algoritmasının çalışmasına bakalım.
Taban sıralamasının sıralamasında kullanılan adımlar aşağıdaki gibi listelenmiştir:
- Öncelikle en büyük elemanı bulmamız gerekiyor (varsayalım) maksimum ) verilen diziden. Sanmak 'X' rakam sayısı olsun maksimum . 'X' hesaplanır çünkü tüm elemanların önemli yerlerinden geçmemiz gerekir.
- Bundan sonra önemli yerlerin her birini tek tek geçin. Burada, her önemli yerin rakamlarını sıralamak için herhangi bir kararlı sıralama algoritması kullanmak zorundayız.
Şimdi bir örnek kullanarak taban sıralamasının işleyişini detaylı olarak görelim. Daha net anlamak için sıralanmamış bir diziyi alalım ve bunu taban sıralamasını kullanarak sıralamaya çalışalım. Açıklamayı daha net ve kolay hale getirecektir.
Verilen dizideki en büyük eleman 736 olduğu 3 içindeki rakamlar. Böylece döngü üç defaya kadar çalışacaktır (yani yüzlerce yer ). Bu, diziyi sıralamak için üç geçişin gerekli olduğu anlamına gelir.
Şimdi ilk önce elemanları birlik basamağa göre sıralayın (ör. x = 0 ). Burada elemanları sıralamak için sayarak sıralama algoritmasını kullanıyoruz.
Geçiş 1:
İlk geçişte liste 0 basamağındaki rakamlara göre sıralanır.
İlk geçişten sonra dizi elemanları -
Geçiş 2:
Bu geçişte liste sonraki anlamlı basamaklara (yani 10. basamaklara) göre sıralanır.oyer).
İkinci geçişten sonra dizi elemanları -
3. Geçiş:
Bu geçişte liste sonraki anlamlı basamaklara (yani 100. basamaklara) göre sıralanır.oyer).
Üçüncü geçişten sonra dizi elemanları -
Artık dizi artan düzende sıralanıyor.
Radix sıralama karmaşıklığı
Şimdi Radix sıralamasının zaman karmaşıklığını en iyi durum, ortalama durum ve en kötü durumda görelim. Ayrıca Radix sıralamasının uzay karmaşıklığını da göreceğiz.
Java'da dizeyi int'ye dönüştürün
1. Zaman Karmaşıklığı
| Dava | Zaman Karmaşıklığı |
|---|---|
| En iyi senaryo | Ω(n+k) |
| Ortalama Durum | θ(nk) |
| En kötü durumda | O(nk) |
Radix sıralama, karşılaştırmalı sıralama algoritmalarından daha iyi olan karşılaştırmasız bir sıralama algoritmasıdır. O(n logn) karmaşıklığına sahip karşılaştırmalı algoritmalardan daha iyi olan doğrusal zaman karmaşıklığına sahiptir.
2. Uzayın Karmaşıklığı
| Uzay Karmaşıklığı | O(n + k) |
| Stabil | EVET |
- Radix sıralamasının uzay karmaşıklığı O(n + k)'dir.
Radix sıralamasının uygulanması
Şimdi Radix sıralamasının farklı programlama dillerindeki programlarını görelim.
Program: C dilinde Radix sıralamasını uygulayan bir program yazın.
#include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) { printf('%d ', a[i]); } printf('
'); int main() a[]="{181," 289, 390, 121, 145, 736, 514, 888, 122}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarray(a,n); radixsort(a, n); printf('after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-8.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) cout< <a[i]<<' '; } int main() { a[]="{171," 279, 380, 111, 135, 726, 504, 878, 112}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarray(a,n); radixsort(a, n); cout<<'
after applying radix sort, the printarray(a, return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-9.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C#.</p> <pre> using System; class RadixSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countingSort(int[] a, int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements static void printArray(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{161," 269, 370, 101, 125, 716, 54, 868, 12}; int n="a.Length;" console.write('before sorting array elements are -
'); printarray(a,n); radixsort(a, n); console.write('
after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-10.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in Java.</p> <pre> class RadixSort { int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{151," 259, 360, 91, 115, 706, 34, 858, 2}; n="a.length;" radixsort r1="new" radixsort(); system.out.print('before sorting array elements are -
'); r1.printarray(a,n); r1.radixsort(a, n); system.out.print('
after applying radix sort, the r1.printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-11.webp" alt="Radix Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>