Javascript Radix Sort Algoritması

Herkese merhaba, Javascript yazılarımıza kaldığımız yerden devam ediyoruz. Bu yazımızda sıralama algoritmalarından biri olan radix sort algoritmasını anlatacağım. Hadi başlayalım !

Radix Sort Algoritması Nedir ?

Radix sort, sıralama algoritmalarından biridir ve özellikle sayılarla çalışırken etkili bir şekilde kullanılabilir. Bu algoritma, sayıları basamaklarına ayırarak sıralama yapar.

Radix sort algoritmasını yazmak için öncelikle, sayıları basamaklarına ayırmak için bir fonksiyon yazmanız gerekecektir. Bu fonksiyon, sayının belirli bir basamağındaki rakamı döndürecektir.

Javascript Radix Sort Algoritması Kodu

Örneğin, 1234 sayısının 3. basamağındaki rakamı 2’dir. Bu nedenle, aşağıdaki gibi bir fonksiyon yazabilirsiniz:

function getDigit(num, place) {
    return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

Bu fonksiyon, num argümanındaki sayının, place argümanındaki basamağındaki rakamı döndürür. Örneğin, getDigit(1234, 3) çağrısı 2 döndürecektir.

Şimdi, radix sort algoritmasını yazabiliriz. Bu algoritma, sayıları basamaklarına göre sıralamak için bir dizi işlem yapar.

function radixSort(arr) {
    const maxDigitCount = mostDigits(arr);
    for (let k = 0; k < maxDigitCount; k++) {
        let digitBuckets = Array.from({length: 10}, () => []);
        for (let i = 0; i < arr.length; i++) {
            let digit = getDigit(arr[i], k);
            digitBuckets[digit].push(arr[i]);
        }
        arr = [].concat(...digitBuckets);
    }
    return arr;
}

Bu kod, arr dizisindeki sayıları basamaklarına göre sıralar. İlk önce, dizideki en büyük sayının kaç basamağı olduğunu belirlemek için mostDigits() fonksiyonunu çağırırız:

function mostDigits(arr) {
    let maxDigits = 0;
    for (let i = 0; i < arr.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(arr[i]));
    }
    return maxDigits;
}

Bu fonksiyon, arr dizisindeki en büyük sayının kaç basamağı olduğunu döndürür. Bu bilgi, radix sort algoritmasındaki işlemler için gereklidir.

Sonra, her bir basamak için ayrı bir işlem yaparız. Bu işlem, digitBuckets adlı bir boş dizi oluşturmakla başlar. Bu dizi, her bir rakama karşılık gelen bir dizi içerecektir. Örneğin, digitBuckets[0] dizi içinde 0 rakamına sahip sayıları içerecektir.

Daha sonra, arr dizisindeki sayıları, k. basamağına göre digitBuckets dizisine atarız. Bu işlemi yapmak için getDigit() fonksiyonunu kullanırız.

En sonunda, digitBuckets dizisini birleştirerek arr dizisinin yeni sırasını elde ederiz ve bu işlemi basamak sayısı kadar tekrarlarız. Bu şekilde, arr dizisi basamaklarına göre sıralanmış olacaktır.

Radix Sort Algoritması İşlem Adımları

Örneğin, [23, 345, 5467, 12, 2345, 9852] dizisi için radixSort() fonksiyonu aşağıdaki gibi çalışacaktır:

• maxDigitCount = 4 (en büyük sayı 9852, dört basamaklı)
  • 1. basamağa göre sıralama
    • digitBuckets[0] = [12]
    • digitBuckets[1] = [23]
    • digitBuckets[2] = [2345]
    • digitBuckets[3] = [345]
    • digitBuckets[4] = []
    • digitBuckets[5] = [5467]
    • digitBuckets[6] = []
    • digitBuckets[7] = []
    • digitBuckets[8] = []
    • digitBuckets[9] = [9852]
    • arr = [12, 23, 2345, 345, 5467, 9852]
  • 2. basamağa göre sıralama:
    • digitBuckets[0] = [12]
    • digitBuckets[1] = []
    • digitBuckets[2] = [2345]
    • digitBuckets[3] = [345]
    • digitBuckets[4] = [5467]
    • digitBuckets[5] = []
    • digitBuckets[6] = []
    • digitBuckets[7] = []
    • digitBuckets[8] = [9852]
    • digitBuckets[9] = [23]
    • arr = [12, 23, 2345, 345, 5467, 9852]
  • 3. basamağa göre sıralama:
    • digitBuckets[0] = [12, 23]
    • digitBuckets[1] = []
    • digitBuckets[2] = [2345]
    • digitBuckets[3] = [345]
    • digitBuckets[4] = [5467]
    • digitBuckets[5] = []
    • digitBuckets[6] = []
    • digitBuckets[7] = []
    • digitBuckets[8] = [9852]
    • digitBuckets[9] = []
    • arr = [12, 23, 345, 2345, 5467, 9852]
  • 4. basamağa göre sıralama
    • digitBuckets[0] = [12, 23, 345, 2345]
    • digitBuckets[1] = []
    • digitBuckets[2] = []
    • digitBuckets[3] = []
    • digitBuckets[4] = [5467]
    • digitBuckets[5] = []
    • digitBuckets[6] = []
    • digitBuckets[7] = []
    • digitBuckets[8] = [9852]
    • digitBuckets[9] = []
    • arr = [12, 23, 345, 2345, 5467, 9852]

Sonuç

Sonuç olarak, radix sort algoritması sayıları basamak olarak sıralamak için kullanılabilecek etkili bir yöntemdir. Bu algoritma, sayıları basamaklarına ayırarak ve her basamaktaki sayıları sıraya koyarak çalışır. Radix sort algoritması, büyük sayı dizileri üzerinde çalışırken özellikle faydalıdır. Ancak, dizideki en büyük sayının basamak sayısı çok yüksekse, radix sort yavaşlayabilir ve diğer sıralama algoritmaları daha etkili olabilir.

Evet Javascript ile radix sort algoritmasının kullanımı bu şekilde yapılmakta. Tüm Javascript yazılarımıza buraya, sıralama algoritmaları ile ilgili yazılarımıza buraya tıklayarak ulaşabilirsiniz. Herkese hayırlı günler.