Radix Sort alqoritmi

[codex]

Radix Sort — müqayisəyə əsaslanmayan (non-comparative) sıralama alqoritmidir. Bu alqoritm elementləri rəqəmlərinə (yəni rəqəm mövqelərinə) görə bucket adlı qruplara bölərək işləyir. Əməliyyat ya ən az əhəmiyyətli rəqəmdən (LSD - least significant digit) başlayaraq, ya da ən çox əhəmiyyətli rəqəmdən (MSD - most significant digit) başlayaraq aparılır. Bu proses, bütün rəqəmlər nəzərə alınana qədər davam edir.

Radix Sort, xüsusilə tam ədədlərin sıralanmasında effektivdir və O(nk) (k = ən böyük rəqəm sayı) kimi xətti zaman mürəkkəbliyinə malikdir. Bu, onu böyük verilənlər üçün ənənəvi müqayisəyə əsaslanan sıralama alqoritmlərindən daha sürətli edir. Lakin bu alqoritm üçün bütün ədədlərin eyni sayda rəqəmə sahib olması və ya bərabərləşdirilməsi vacibdir.

---

İmplementasiya

getDigit - Verilmiş ədədin istənilən rəqəmini almaq

Bu funksiya num ədədinin i-ci mövqedəki rəqəmini qaytarır:

const getDigit = (number, i) => {
  return Math.floor(Math.abs(number) / Math.pow(10, i)) % 10;
}

---

digitCount - Ədədin neçə rəqəmdən ibarət olduğunu qaytarmaq

Bu funksiya ədədin neçə rəqəmdən ibarət olduğunu tapır:

const digitCount = (number) => {
  return Math.floor(Math.log10(Math.abs(number))) + 1;
}

---

mostDigits - Massivdə ən çox rəqəmə sahib ədədin rəqəm sayını tapmaq

Bu funksiya bir massivdəki ən böyük rəqəm sayını tapır:

const mostDigits = (numberArray) => {
  let max = 0;
  for (let i = 0; i < numberArray.length; i++) {
    max = Math.max(max, digitCount(numberArray[i]));
  }
  return max;
}

---

Radix Sort-un özünün tətbiqi

1. Bir massiv qəbul edən radixSort funksiyasını yaradın;
2. Ən böyük ədədin neçə rəqəmə sahib olduğunu mostDigits funksiyası ilə tapın;
3. k = 0-dan başlayaraq bu ən böyük rəqəm sayına qədər dövr yaradın;
4. Hər iterasiyada:
   • digitBuckets adlı 0-dan 9-a qədər 10 boş qutu yaradın;
   • Ədədləri k-cı rəqəmlərinə görə uyğun qutulara yerləşdirin;
5. Massivi bucket-lərdəki dəyərlərlə yenidən qurun ([].concat(...digitBuckets));
6. Sonda sıralanmış massivi qaytarın;

Tam Həll:

const radixSort = (array) => {
  const largest = mostDigits(array);

  for (let k = 0; k < largest; k++) {
    const digitBuckets = Array.from({ length: 10 }, () => []);
    
    for (let i = 0; i < array.length; i++) {
      const digit = getDigit(array[i], k);
      digitBuckets[digit].push(array[i]);
    }

    array = [].concat(...digitBuckets);
  }

  return array;
}

---

Nəticə

Radix Sort — sadə, amma güclü bir alqoritmdir. Xüsusilə tam ədədlərlə işləyən və böyük verilənlərdə performans tələb edən sistemlərdə çox istifadə olunur. Əgər ədədlər eyni uzunluqda deyilsə, 0 ilə doldurularaq eyni uzunluğa gətirilə bilər. Radix Sort-un müqayisəyə əsaslanan sort alqoritmlərindən fərqli olaraq rəqəm əsaslı olması onu unikal və fərqli edir.

[codex]

Radix Sort-un Java proqramlaşdırma dilində implementasiyası

import java.util.ArrayList;
import java.util.List;

public class RadixSort {

    // Ədədin müəyyən mövqedəki rəqəmini qaytarır
    public static int getDigit(int num, int place) {
        return (int)(Math.abs(num) / Math.pow(10, place)) % 10;
    }

    // Ədədin neçə rəqəmdən ibarət olduğunu tapır
    public static int digitCount(int num) {
        if (num == 0) return 1;
        return (int)Math.floor(Math.log10(Math.abs(num))) + 1;
    }

    // Massivdə ən çox rəqəmə sahib ədədin rəqəm sayını tapır
    public static int mostDigits(int[] nums) {
        int maxDigits = 0;
        for (int num : nums) {
            maxDigits = Math.max(maxDigits, digitCount(num));
        }
        return maxDigits;
    }

    // Radix Sort-un əsas funksiyası
    public static int[] radixSort(int[] nums) {
        int maxDigitCount = mostDigits(nums);

        for (int k = 0; k < maxDigitCount; k++) {
            List<List<Integer>> digitBuckets = new ArrayList<>();

            // 0-dan 9-a qədər 10 bucket (siyahı) yaradılır
            for (int i = 0; i < 10; i++) {
                digitBuckets.add(new ArrayList<>());
            }

            // Ədədlər müvafiq bucket-lərə yerləşdirilir
            for (int num : nums) {
                int digit = getDigit(num, k);
                digitBuckets.get(digit).add(num);
            }

            // Bütün bucket-lər birləşdirilərək yeni massiv yaradılır
            int index = 0;
            for (List<Integer> bucket : digitBuckets) {
                for (int num : bucket) {
                    nums[index++] = num;
                }
            }
        }

        return nums;
    }

    // Test məqsədli əsas metod
    public static void main(String[] args) {
        int[] data = {170, 45, 75, 90, 802, 24, 2, 66};
        int[] sorted = radixSort(data);

        for (int num : sorted) {
            System.out.print(num + " ");
        }
    }
}

Nəticə:

2 24 45 66 75 90 170 802