Radix Sort Algoritması

Radiks sort algoritması, 1887 yılında Herman Hollerith’in geliştirdiği “tabulating machine” için kullandığı yönteme dayanır.

• Yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir.
• Algoritma O(n) zaman karmaşıklığına sahiptir.
• Alan maliyeti yüksektir.
• Çok fazla miktarda sayı sıralanacaksa yönetimi zordur.
• İki farklı şekilde kullanılabilir. En anlamlı basamağa göre(most significant digit) sıralama ve en anlamsız basamağa göre(least significant digit) sıralama.

Örnek vermek gerekirse;

156,38,147,159,254,300,29,79 sayılarını hep birlikte sıralayalım

1. adımda tüm sayılarımızın aynı sayıda haneden oluşması gerekir. Bunun için iki basamaklı sayılarımızın başına 0 yazıyoruz.

156,038,147,159,254,300,029,079

2. adımda sıralamamıza başlıyoruz .(ben en değersiz basamağa göre sıralama yapacağım) birler basamağındaki sayıların değerlerine göre sıralamaya başlıyorum.

300,254,156,147,38,159,029,079

3. adımda onlar basamağına göre sıralamamızı yapıyoruz.

300,029,038,147,245,156,159,079

4.adımda yüzler basamağına göre sıralamamızı yapıyoruz.

029,038,079,147,156,159,254,300

// C++ implementation of Radix Sort
#include<iostream>
using namespace std;
 
// A utility function to get maximum value in arr[]
int getMax(int arr[], int n)
{
    int mx = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > mx)
            mx = arr[i];
    return mx;
}
 
// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
    int output[n]; // output array
    int i, count[10] = {0};
 
    // Store count of occurrences in count[]
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%10 ]++;
 
    // Change count[i] so that count[i] now contains actual
    //  position of this digit in output[]
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];
 
    // Build the output array
    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
        count[ (arr[i]/exp)%10 ]--;
    }
 
    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}
 
// The main function to that sorts arr[] of size n using 
// Radix Sort
void radixsort(int arr[], int n)
{
    // Find the maximum number to know number of digits
    int m = getMax(arr, n);
 
    // Do counting sort for every digit. Note that instead
    // of passing digit number, exp is passed. exp is 10^i
    // where i is current digit number
    for (int exp = 1; m/exp > 0; exp *= 10)
        countSort(arr, n, exp);
}
 
// A utility function to print an array
void print(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {156,38,147,159,254,300,29,79};
    int n = sizeof(arr)/sizeof(arr[0]);
    radixsort(arr, n);
    print(arr, n);
    return 0;
}

Çıktı:

Yararlandığım kaynaklar:

http://www.geeksforgeeks.org/radix-sort/

https://en.wikipedia.org/wiki/Radix_sort