Radix Sort

Radix Sort, rəqəmlərin və ya simvolların hər bir mövqeyini (radix) ayrı-ayrılıqda sıralayan qeyri-müqayisəli bir sıralama alqoritmidir. Bu alqoritm, counting sort kimi köməkçi alqoritmlərdan istifadə edərək hər bir rəqəm mövqeyini sıralayır.

Radix Sort-un Əsas Xüsusiyyətləri

• Qeyri-müqayisəli: Elementləri birbaşa müqayisə etmir
• Rəqəm əsaslı: Hər bir rəqəm mövqeyini ayrı-ayrılıqda işləyir
• Stabil: Eyni dəyərə malik elementlərin nisbi sırası qorunur
• Məhdud Məlumat: Yalnız müəyyən növ məlumatlar üçün uyğundur

Radix Sort-un İşləmə Prinsipi

1. Ən böyük rəqəmi tap: Neçə rəqəm mövqeyi olduğunu müəyyən et
2. LSD-dən başla: Least Significant Digit-dən (ən sağ rəqəm) başla
3. Counting Sort tətbiq et: Hər bir rəqəm üçün counting sort istifadə et
4. Növbəti rəqəmə keç: Soldan bir rəqəm irəli get
5. Təkrarla: Bütün rəqəm mövqeləri bitənə qədər davam et

Radix Sort-un Java-da İmplementasiyası

Koda bax

import java.util.Arrays;

public class RadixSort {
    
    // Ana sıralama metodu
    public static void radixSort(int[] arr) {
        if (arr.length <= 1) return;
        
        // Ən böyük elementi tap
        int max = getMax(arr);
        
        // Hər bir rəqəm üçün counting sort et
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }
    
    // Ən böyük elementi tapan köməkçi metod
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
    
    // Müəyyən rəqəm mövqeyi üçün counting sort
    private static void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // Çıxış massivi
        int[] count = new int[10]; // 0-dan 9-a qədər rəqəmlər üçün
        
        // count massivini sıfırla
        Arrays.fill(count, 0);
        
        // Hər rəqəmin sayını hesabla
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        
        // count[i] indi i rəqəminin mövqeyini göstərir
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        
        // Çıxış massivini qur (sağdan sola stabil olmaq üçün)
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        
        // Çıxış massivini əsas massivə köçür
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
    
    // String massivi üçün radix sort
    public static void radixSortStrings(String[] arr) {
        if (arr.length <= 1) return;
        
        // Ən uzun string-in uzunluğunu tap
        int maxLength = 0;
        for (String str : arr) {
            if (str.length() > maxLength) {
                maxLength = str.length();
            }
        }
        
        // Sağdan sola hər bir mövqe üçün
        for (int pos = maxLength - 1; pos >= 0; pos--) {
            countingSortForStrings(arr, pos);
        }
    }
    
    // String-lər üçün counting sort
    private static void countingSortForStrings(String[] arr, int pos) {
        int n = arr.length;
        String[] output = new String[n];
        int[] count = new int[256]; // ASCII simvollar üçün
        
        Arrays.fill(count, 0);
        
        // Hər simvolun sayını hesabla
        for (int i = 0; i < n; i++) {
            char ch = pos < arr[i].length() ? arr[i].charAt(pos) : 0;
            count[ch]++;
        }
        
        // count[i] indi i simvolunun mövqeyini göstərir
        for (int i = 1; i < 256; i++) {
            count[i] += count[i - 1];
        }
        
        // Çıxış massivini qur
        for (int i = n - 1; i >= 0; i--) {
            char ch = pos < arr[i].length() ? arr[i].charAt(pos) : 0;
            output[count[ch] - 1] = arr[i];
            count[ch]--;
        }
        
        // Çıxış massivini əsas massivə köçür
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
    
    // Test
    public static void main(String[] args) {
        // Integer massivi üçün test
        int[] arr = {170, 45, 75, 90, 2, 802, 24, 66};
        
        System.out.println("Original array:");
        printArray(arr);
        
        radixSort(arr);
        
        System.out.println("\nSorted array:");
        printArray(arr);
        
        // String massivi üçün test
        String[] strArr = {"abc", "car", "code", "book", "zoo"};
        
        System.out.println("\nOriginal string array:");
        printStringArray(strArr);
        
        radixSortStrings(strArr);
        
        System.out.println("\nSorted string array:");
        printStringArray(strArr);
    }
    
    // Integer massivini çap etmək üçün köməkçi metod
    private static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    
    // String massivini çap etmək üçün köməkçi metod
    private static void printStringArray(String[] arr) {
        for (String str : arr) {
            System.out.print(str + " ");
        }
        System.out.println();
    }
}

Zaman və Yaddaş Mürəkkəbliyi

• Zaman Mürəkkəbliyi:
  • Ən yaxşı hal: O(d × (n + k)) - d: rəqəm sayı, k: radix (10)
  • Orta hal: O(d × (n + k))
  • Ən pis hal: O(d × (n + k))
• Yaddaş Mürəkkəbliyi: O(n + k), əlavə massivlər üçün

Radix Sort-un Üstünlükləri və Çatışmazlıqları

Üstünlüklər

• Böyük massivlər üçün çox sürətli ola bilər
• Stabil sıralama alqoritmidir
• Müqayisə əməliyyatı tələb etmir
• Parallelləşdirmə üçün uyğundur

Çatışmazlıqlar

• Yalnız müəyyən məlumat növləri üçün uyğundur (integer, string)
• Əlavə yaddaş tələb edir
• Neqativ ədədlər üçün əlavə işləmə tələb edir
• Cache performansı yaxşı deyil
• Floating point ədədlər üçün mürəkkəb implementasiya