Radix Sıralama Algoritması Açıklaması

Radix Sıralama, sayıları basamak basamak sıralayan, karşılaştırma tabanlı olmayan bir sıralama algoritmasıdır. Öğeleri doğrudan karşılaştırmak yerine, her basamak konumunu, en anlamsız basamaktan veya en anlamlı basamaktan başlayarak işler ve her adımda sayıları düzenlemek için kararlı bir sıralama yöntemi kullanır.

Radix Sıralama, sınırlı sayıda basamağa sahip tam sayıları sıralarken güçlüdür. Sayarak Sıralama ile yakından bağlantılıdır çünkü Sayarak Sıralama, sayıları her basamağa göre sıralamak için kararlı bir alt rutin olarak yaygın şekilde kullanılır.

Giriş

Çoğu sıralama algoritması değerleri birbiriyle karşılaştırır. Kabarcık Sıralama komşuları karşılaştırır, Seçmeli Sıralama en küçük öğeyi bulur, Eklemeli Sıralama değerleri doğru konuma ekler ve Hızlı Sıralama değerleri bir pivot etrafında böler.

Radix Sıralama farklı bir strateji kullanır. Tam sayıları doğrudan karşılaştırmaz. Bunun yerine, tek tek basamaklara bakar ve sayıları her seferinde bir basamak konumuna göre sıralar.

Bu durum, Radix Sıralama'yı önemli bir algoritma yapar çünkü sıralamanın bazen geleneksel karşılaştırmalar olmadan da yapılabileceğini gösterir. Veriler uygun olduğunda, Radix Sıralama çok verimli olabilir ve doğrusal benzeri bir performans elde edebilir.

Radix Sıralama Nedir?

Radix Sıralama, sayıları basamaklarını işleyerek sıralayan bir sıralama algoritmasıdır. "Radix" kelimesi, sayı sisteminin tabanını ifade eder. Onluk sistemde, basamaklar 0'dan 9'a kadar değiştiği için radix 10'dur.

Örneğin, 472 sayısının üç basamak konumu vardır:

  • Birler basamağı: 2

  • Onlar basamağı: 7

  • Yüzler basamağı: 4

Radix Sıralama, bir sayı listesini önce birler basamağına, sonra onlar basamağına, sonra yüzler basamağına ve bu şekilde devam ederek sıralayabilir.

Ana fikir basittir:

  • Kaç basamak konumuna ihtiyaç olduğunu bilmek için en büyük sayıyı bulun.

  • Diziyi birler basamağına göre sıralayın.

  • Diziyi onlar basamağına göre sıralayın.

  • Diziyi yüzler basamağına göre sıralayın.

  • Tüm basamak konumları işlenene kadar devam edin.

Tüm basamak konumları kararlı bir sıralama yöntemi kullanılarak işlendikten sonra, dizi tamamen sıralanmış olur.

Radix Sıralama Neden Kararlı Bir Sıralamaya İhtiyaç Duyar?

Radix Sıralama kararlılığa bağlıdır. Kararlı bir sıralama algoritması, eşit anahtarlara sahip öğelerin göreceli sırasını korur.

Bu önemlidir çünkü Radix Sıralama her seferinde bir basamağı sıralar. Daha sonraki bir basamağa göre sıralama yaparken, önceki basamak sıralamasının oluşturduğu sıra bozulmamalıdır.

Örneğin, iki sayının onlar basamağı aynıysa, birler basamağı sıralamasından gelen önceki sıralamaları değişmeden kalmalıdır. Kararlılık olmadan, basamak basamak ilerleyen işlem yanlış bir nihai sonuç verebilir.

Bu nedenle Sayarak Sıralama, Radix Sıralama içinde yaygın olarak kullanılır. Kararlı Sayarak Sıralama, aynı basamağa sahip sayıların sırasını korurken değerleri belirli bir basamağa göre sıralayabilir.

LSD Radix Sıralama ve MSD Radix Sıralama

Radix Sıralama'nın iki yaygın yaklaşımı vardır: LSD Radix Sıralama ve MSD Radix Sıralama.

LSD Radix Sıralama, En Anlamsız Basamak Radix Sıralaması anlamına gelir. En sağdaki basamaktan, yani birler basamağından başlar, sonra sola doğru onlar, yüzler, binler ve daha yüksek konumlara doğru ilerler.

MSD Radix Sıralama, En Anlamlı Basamak Radix Sıralaması anlamına gelir. En soldaki basamaktan başlar ve sağa doğru ilerler.

Bu makale, LSD Radix Sıralama'ya odaklanmaktadır çünkü anlaması daha kolaydır ve Sayarak Sıralama ile Radix Sıralama açıklanırken yaygın olarak öğretilir.

LSD Radix Sıralama Nasıl Çalışır?

LSD Radix Sıralama, sayıları en anlamsız basamaktan en anlamlı basamağa doğru işler. Onluk sayılarda bu, birler basamağından başlayıp, sonra onlar basamağına, sonra yüzler basamağına ve bu şekilde devam etmek anlamına gelir.

Algoritma şu şekilde çalışır:

  1. Dizideki maksimum değeri bulun.

  2. Birler basamağını temsil eden 1 basamak konumuyla başlayın.

  3. Tüm sayıları mevcut basamağa göre kararlı bir sıralama algoritması kullanarak sıralayın.

  4. Basamak değerini 10 ile çarparak bir sonraki basamak konumuna geçin.

  5. Maksimum sayının işlenecek başka basamağı kalmayana kadar tekrarlayın.

Önemli olan nokta, her basamak düzeyindeki sıralama adımının kararlı olması gerektiğidir.

Manuel Çalıştırma Örneği

Aşağıdaki diziyi LSD Radix Sıralama kullanarak manuel olarak sıralayalım:

[170, 45, 75, 90, 802, 24, 2, 66]

Maksimum değer:

802

802 üç basamaklı olduğundan, Radix Sıralama üç basamak konumunu işleyecektir:

  • Birler basamağı

  • Onlar basamağı

  • Yüzler basamağı

Geçiş 1: Birler Basamağına Göre Sıralama

İlk olarak, sayıları birler basamaklarına göre sıralarız.

Number: 170  Ones digit: 0
Number: 45   Ones digit: 5
Number: 75   Ones digit: 5
Number: 90   Ones digit: 0
Number: 802  Ones digit: 2
Number: 24   Ones digit: 4
Number: 2    Ones digit: 2
Number: 66   Ones digit: 6

Şimdi sayıları, göreceli sıralarını koruyarak birler basamağına göre grupluyoruz:

Digit 0: 170, 90
Digit 1:
Digit 2: 802, 2
Digit 3:
Digit 4: 24
Digit 5: 45, 75
Digit 6: 66
Digit 7:
Digit 8:
Digit 9:

Birler basamağına göre sıraladıktan sonra dizi şu hale gelir:

[170, 90, 802, 2, 24, 45, 75, 66]

Bu dizi henüz tamamen sıralanmadı. Sadece birler basamağına göre sıralandı.

Geçiş 2: Onlar Basamağına Göre Sıralama

Şimdi mevcut diziyi onlar basamağına göre sıralıyoruz.

Current array:
[170, 90, 802, 2, 24, 45, 75, 66]

Onlar basamakları şunlardır:

Number: 170  Tens digit: 7
Number: 90   Tens digit: 9
Number: 802  Tens digit: 0
Number: 2    Tens digit: 0
Number: 24   Tens digit: 2
Number: 45   Tens digit: 4
Number: 75   Tens digit: 7
Number: 66   Tens digit: 6

Şimdi sayıları, sıralarını koruyarak onlar basamağına göre grupluyoruz:

Digit 0: 802, 2
Digit 1:
Digit 2: 24
Digit 3:
Digit 4: 45
Digit 5:
Digit 6: 66
Digit 7: 170, 75
Digit 8:
Digit 9: 90

Onlar basamağına göre sıraladıktan sonra dizi şu hale gelir:

[802, 2, 24, 45, 66, 170, 75, 90]

Dizi hala tamamen sıralanmış değil, ancak kararlı sıralama önceki geçişi koruduğu için artık birler ve onlar basamaklarının sırasına birlikte uymaktadır.

Geçiş 3: Yüzler Basamağına Göre Sıralama

Şimdi mevcut diziyi yüzler basamağına göre sıralıyoruz.

Current array:
[802, 2, 24, 45, 66, 170, 75, 90]

Yüzler basamakları şunlardır:

Number: 802  Hundreds digit: 8
Number: 2    Hundreds digit: 0
Number: 24   Hundreds digit: 0
Number: 45   Hundreds digit: 0
Number: 66   Hundreds digit: 0
Number: 170  Hundreds digit: 1
Number: 75   Hundreds digit: 0
Number: 90   Hundreds digit: 0

Şimdi sayıları, sıralarını koruyarak yüzler basamağına göre grupluyoruz:

Digit 0: 2, 24, 45, 66, 75, 90
Digit 1: 170
Digit 2:
Digit 3:
Digit 4:
Digit 5:
Digit 6:
Digit 7:
Digit 8: 802
Digit 9:

Yüzler basamağına göre sıraladıktan sonra dizi şu hale gelir:

[2, 24, 45, 66, 75, 90, 170, 802]

Nihai Sıralanmış Dizi

[2, 24, 45, 66, 75, 90, 170, 802]

Bu manuel çalıştırma, Radix Sıralama'nın nihai sırayı kademeli olarak nasıl oluşturduğunu gösterir. Her geçiş bir basamak konumuna göre sıralama yapar ve kararlılık, önceki basamak sıralamasının doğru kalmasını sağlar.

Bir Basamak Nasıl Çıkarılır?

Radix Sıralama, bir sayıdan belirli bir basamağı çıkarmak için bir yönteme ihtiyaç duyar. Onluk sayılar için bölme ve modulo işlemlerini kullanabiliriz.

Belirli bir basamak değerindeki basamağı çıkarmak için:

digit = Math.floor(number / place) % 10

Örneğin, 170 sayısı için:

  • Birler basamağı: Math.floor(170 / 1) % 10 = 0

  • Onlar basamağı: Math.floor(170 / 10) % 10 = 7

  • Yüzler basamağı: Math.floor(170 / 100) % 10 = 1

PHP'de aynı fikir şu şekilde yazılabilir:

$digit = intdiv($number, $place) % 10;

Basamak değeri 1'den başlar ve her geçişten sonra 10 ile çarpılır.

Radix Sıralama Algoritma Adımları

LSD Radix Sıralama algoritması şu adımlar kullanılarak açıklanabilir:

  1. Giriş dizisindeki maksimum değeri bulun.

  2. Başlangıç basamak değerini 1 olarak ayarlayın.

  3. Diziyi mevcut basamak değerindeki basamağa göre sıralamak için kararlı bir sıralama algoritması kullanın.

  4. Basamak değerini 10 ile çarpın.

  5. Maksimum değerin basamak değerine bölümü 0'dan büyük olduğu sürece tekrarlayın.

  6. Sıralanmış diziyi döndürün.

Sayarak Sıralama, her basamak 0 ile 9 arasında olduğu için genellikle kararlı basamak sıralama algoritması olarak kullanılır.

Sözde Kod (Pseudocode)

radixSort(array):
    max = find maximum value in array
    place = 1

    while max / place > 0:
        countingSortByDigit(array, place)
        place = place * 10

    return array

Yardımcı fonksiyon, diziyi bir basamak konumuna göre sıralar:

countingSortByDigit(array, place):
    count = array of size 10 filled with 0
    output = array of same size as input

    for each number in array:
        digit = (number / place) % 10
        count[digit] = count[digit] + 1

    for i from 1 to 9:
        count[i] = count[i] + count[i - 1]

    for i from length(array) - 1 down to 0:
        digit = (array[i] / place) % 10
        position = count[digit] - 1
        output[position] = array[i]
        count[digit] = count[digit] - 1

    copy output back to array

Yardımcı fonksiyon, bir basamak konumuna uygulanan kararlı bir Sayarak Sıralama'dır.

PHP'de Radix Sıralama Örneği

İşte negatif olmayan tam sayılar için temiz bir PHP Radix Sıralama uygulaması:

<?php

function radixSort(array $numbers): array
{
    if ($numbers === []) {
        return [];
    }

    $max = max($numbers);

    for ($place = 1; intdiv($max, $place) > 0; $place *= 10) {
        $numbers = countingSortByDigit($numbers, $place);
    }

    return $numbers;
}

function countingSortByDigit(array $numbers, int $place): array
{
    $length = count($numbers);
    $output = array_fill(0, $length, 0);
    $count = array_fill(0, 10, 0);

    foreach ($numbers as $number) {
        $digit = intdiv($number, $place) % 10;
        $count[$digit]++;
    }

    for ($i = 1; $i < 10; $i++) {
        $count[$i] += $count[$i - 1];
    }

    for ($i = $length - 1; $i >= 0; $i--) {
        $digit = intdiv($numbers[$i], $place) % 10;
        $position = $count[$digit] - 1;

        $output[$position] = $numbers[$i];
        $count[$digit]--;
    }

    return $output;
}

$numbers = [170, 45, 75, 90, 802, 24, 2, 66];

print_r(radixSort($numbers));

Çıktı şöyle olacaktır:

Array
(
    [0] => 2
    [1] => 24
    [2] => 45
    [3] => 66
    [4] => 75
    [5] => 90
    [6] => 170
    [7] => 802
)

Bu uygulama, her basamak konumu için kararlı Sayarak Sıralama kullanır. Sayı dizisi yalnızca 10 konuma sahiptir çünkü onluk basamaklar 0'dan 9'a kadar değişir.

JavaScript'te Radix Sıralama Örneği

İşte aynı algoritmanın JavaScript'te uygulanmış hali:

function radixSort(numbers) {
    if (numbers.length === 0) {
        return [];
    }

    const max = Math.max(...numbers);

    for (let place = 1; Math.floor(max / place) > 0; place *= 10) {
        numbers = countingSortByDigit(numbers, place);
    }

    return numbers;
}

function countingSortByDigit(numbers, place) {
    const output = new Array(numbers.length);
    const count = new Array(10).fill(0);

    for (const number of numbers) {
        const digit = Math.floor(number / place) % 10;
        count[digit]++;
    }

    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (let i = numbers.length - 1; i >= 0; i--) {
        const digit = Math.floor(numbers[i] / place) % 10;
        const position = count[digit] - 1;

        output[position] = numbers[i];
        count[digit]--;
    }

    return output;
}

const numbers = [170, 45, 75, 90, 802, 24, 2, 66];

console.log(radixSort(numbers));

Çıktı şöyle olacaktır:

[2, 24, 45, 66, 75, 90, 170, 802]

JavaScript sürümü, PHP sürümüyle aynı mantığı takip eder. Kararlı bir Sayarak Sıralama yardımcısı kullanarak basamak konumuna göre tekrar tekrar sıralama yapar.

Sayarak Sıralama Neden Radix Sıralama İçinde Kullanılır?

Sayarak Sıralama, Radix Sıralama için iyi bir yardımcıdır çünkü her basamağın küçük ve sabit bir aralığı vardır. Onluk sayılarda, her basamak yalnızca 0 ile 9 arasında olabilir.

Bu, sayım dizisinin her basamak geçişi için her zaman 10 boyutunda olduğu anlamına gelir:

Digit values: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Basamak aralığı küçük olduğu için, Sayarak Sıralama, Radix Sıralama içinde çok verimli hale gelir.

Sayarak Sıralama, kümülatif sayımlarla uygulandığında kararlılık da sağlar. Bu kararlılık, Radix Sıralama'nın doğru nihai sırayı üretmesi için gereklidir.

Radix Sıralama'nın Zaman Karmaşıklığı

Zaman karmaşıklığı, bir algoritmanın çalışma süresinin giriş boyutu arttıkça nasıl büyüdüğünü açıklar. Radix Sıralama, öğe sayısına, basamak konumu sayısına ve her basamak için kullanılan taban veya aralığa bağlıdır.

Radix Sıralama'nın standart zaman karmaşıklığı şöyledir:

O(d × (n + k))

Burada:

  • n öğe sayısıdır.

  • d basamak konumu sayısıdır.

  • k olası basamak değerlerinin aralığıdır.

Onluk LSD Radix Sıralama'da k genellikle 10'dur çünkü basamaklar 0'dan 9'a kadar değişir.

Bu nedenle onluk sayılar için bu genellikle şöyle yazılır:

O(d × n)

Bu basitleştirilmiş form, k bir sabit olarak kabul edildiğinde kullanılır.

Radix Sıralama Neden O(d × (n + k))'dir?

Her basamak konumu için Radix Sıralama, kararlı bir Sayarak Sıralama gerçekleştirir.

Basamağa göre Sayarak Sıralama şunları alır:

O(n + k)

En büyük sayı d basamaklıysa, algoritma bu işlemi d kez tekrarlar.

Bu nedenle, toplam zaman karmaşıklığı şöyle olur:

O(d × (n + k))

Eğer k 10'a sabitlenirse, formül şuna yaklaşır:

O(d × n)

Eğer d de küçük ve sınırlıysa, Radix Sıralama doğrusal zamana yakın davranabilir.

En İyi Durum Zaman Karmaşıklığı

Radix Sıralama'nın en iyi durum zaman karmaşıklığı şöyledir:

O(d × (n + k))

Radix Sıralama, giriş dizisi zaten sıralanmış olsa bile her basamak konumunu işlemek zorundadır. Eklemeli Sıralama'dan farklı olarak, veriler zaten sıralı olduğu için O(n) olmaz.

Ortalama Durum Zaman Karmaşıklığı

Ortalama durum zaman karmaşıklığı da şöyledir:

O(d × (n + k))

Algoritma, girişin orijinal sırasından bağımsız olarak aynı basamak basamak ilerleyen süreci takip eder.

En Kötü Durum Zaman Karmaşıklığı

En kötü durum zaman karmaşıklığı şöyledir:

O(d × (n + k))

Bunun nedeni, Radix Sıralama'nın kötü pivotlara veya tersine çevrilmiş dizilere bağlı olmamasıdır. Performansı esas olarak basamak sayısına ve basamak aralığına bağlıdır.

Ancak, sayıların çok fazla basamağı varsa, d büyür. Bu durumda, Radix Sıralama daha az pratik hale gelebilir.

Radix Sıralama'nın Bellek Karmaşıklığı

Radix Sıralama genellikle ek bellek gerektirir çünkü kararlı Sayarak Sıralama bir çıktı dizisi ve bir sayım dizisi kullanır.

Bellek karmaşıklığı şöyledir:

O(n + k)

Burada n öğe sayısı ve k basamak aralığıdır.

Onluk basamaklar için k 10'dur, bu nedenle ana ek bellek n boyutundaki çıktı dizisinden gelir.

Bu nedenle, Radix Sıralama, yaygın kararlı uygulamasında genellikle yerinde sıralama algoritması olarak kabul edilmez.

Radix Sıralama Kararlı mıdır?

Radix Sıralama, dahili basamak sıralama algoritması kararlıysa kararlıdır.

LSD Radix Sıralama, kararlı Sayarak Sıralama kullandığında, tüm algoritma kararlı hale gelir. Bu, eşit değerlerin göreceli sıralarını koruduğu anlamına gelir.

Dahili sıralama adımı kararlı değilse, Radix Sıralama başarısız olabilir çünkü sonraki basamak geçişleri, önceki basamak geçişlerinin oluşturduğu sıralamayı bozabilir.

Yani doğru cevap şudur:

  • Kararlı Sayarak Sıralama ile Radix Sıralama: kararlı.

  • Kararsız basamak sıralama ile Radix Sıralama: kararlı olduğu garanti edilmez.

Radix Sıralama Karşılaştırma Tabanlı Bir Algoritma mıdır?

Radix Sıralama karşılaştırma tabanlı bir sıralama algoritması değildir. Öğeleri birbiriyle tekrar tekrar karşılaştırarak sıralama yapmaz.

Bunun yerine, basamak çıkarma ve kararlı dağıtım kullanır. Bu nedenle Radix Sıralama, doğru koşullar altında bazen karşılaştırma tabanlı algoritmalardan daha hızlı performans gösterebilir.

Karşılaştırma tabanlı sıralama algoritmaları, genel sıralama için O(n log n) alt sınıra sahiptir. Radix Sıralama, sayısal basamak yapısı ve sınırlı basamak aralığı gibi veriler hakkındaki varsayımları kullanarak bu sınırlamadan kaçınır.

Radix Sıralama vs Sayarak Sıralama

Sayarak Sıralama ve Radix Sıralama yakından ilişkilidir, ancak aynı değildir.

Sayarak Sıralama, tam değerleri doğrudan sayar. Tam değer aralığı küçük olduğunda iyi çalışır. Örneğin, 0'dan 100'e kadar sınav puanlarını sıralamak, iyi bir Sayarak Sıralama kullanım durumudur.

Radix Sıralama, değerleri basamak basamak sıralar. Tam değer aralığı büyük olabilen, ancak her basamağın küçük bir aralığı olan durumlarda kullanışlıdır.

  • Sayarak Sıralama, tüm değeri bir indeks olarak kullanır.

  • Radix Sıralama, her seferinde bir basamak kullanır.

  • Sayarak Sıralama'nın zaman karmaşıklığı O(n + k)'dir.

  • Radix Sıralama'nın zaman karmaşıklığı O(d × (n + k))'dir.

  • Sayarak Sıralama daha basittir.

  • Aralık çok büyük olduğunda Radix Sıralama, doğrudan Sayarak Sıralama'dan daha büyük sayıları daha verimli bir şekilde işleyebilir.

Pratikte, Radix Sıralama genellikle dahili olarak Sayarak Sıralama kullanır.

Radix Sıralama vs Hızlı Sıralama

Hızlı Sıralama, karşılaştırma tabanlı bir sıralama algoritmasıdır. Bir pivot seçerek ve diziyi o pivot etrafında bölerek çalışır.

Radix Sıralama, karşılaştırma tabanlı olmayan bir algoritmadır. Değerleri basamak konumlarına göre sıralar.

  • Hızlı Sıralama'nın ortalama zaman karmaşıklığı O(n log n)'dir.

  • Radix Sıralama'nın zaman karmaşıklığı O(d × (n + k))'dir.

  • Hızlı Sıralama birçok karşılaştırılabilir veri türü için çalışır.

  • Radix Sıralama, tam sayılar veya sabit uzunluklu anahtarlar için en iyi şekilde çalışır.

  • Hızlı Sıralama yerinde (in-place) olabilir.

  • Radix Sıralama genellikle ek bellek gerektirir.

Hızlı Sıralama daha geneldir. Radix Sıralama daha özelleşmiştir, ancak veriler varsayımlarına uyduğunda çok hızlı olabilir.

Radix Sıralama vs Birleştirmeli Sıralama

Birleştirmeli Sıralama, garantili O(n log n) zaman karmaşıklığına sahip kararlı karşılaştırma tabanlı bir sıralama algoritmasıdır. Radix Sıralama, karşılaştırma tabanlı değildir ve uygun tam sayı verileri için daha hızlı olabilir.

Ana farklılıklar şunlardır:

  • Birleştirmeli Sıralama öğeleri karşılaştırır.

  • Radix Sıralama basamakları işler.

  • Birleştirmeli Sıralama genel karşılaştırılabilir değerler için çalışır.

  • Radix Sıralama, tam sayılar veya sabit boyutlu anahtarlar için en iyi şekilde çalışır.

  • Birleştirmeli Sıralama'nın zaman karmaşıklığı O(n log n)'dir.

  • Radix Sıralama'nın zaman karmaşıklığı O(d × (n + k))'dir.

  • Her ikisi de genellikle ek bellek gerektirir.

Birleştirmeli Sıralama daha genel ve tahmin edilebilirken, Radix Sıralama daha veriye özeldir ve basamak sayısı sınırlı olduğunda daha hızlı olabilir.

Farklı Uzunluktaki Sayıları İşleme

Radix Sıralama, farklı basamak uzunluklarına sahip sayıları işleyebilir. Daha kısa sayılar, önde sıfırları varmış gibi muamele görür.

Örneğin:

2 can be treated as 002
24 can be treated as 024
802 stays as 802

Bu nedenle, yüzler basamağı geçişi sırasında 2, 24, 45 ve 90 gibi sayıların yüzler basamağı 0'dır.

Algoritmanın fiziksel olarak sıfır eklemesine gerek yoktur. Basamak çıkarma, basamak değeri sayıdan büyük olduğunda doğal olarak 0 döndürür.

Negatif Sayıları İşleme

Temel Radix Sıralama uygulaması genellikle negatif olmayan tam sayılarla çalışır. Negatif sayılar, basamak çıkarma ve sıralama daha karmaşık hale geldiği için ek işlem gerektirir.

Yaygın bir yaklaşım şöyledir:

  1. Negatif sayıları ve negatif olmayan sayıları ayırın.

  2. Negatif sayıları geçici olarak pozitif değerlere dönüştürün.

  3. Her iki grubu ayrı ayrı sıralayın.

  4. Sıralanmış negatif grubu tersine çevirin.

  5. Negatif değerleri geri dönüştürün.

  6. Önce negatifleri, sonra negatif olmayan sayıları birleştirin.

Örneğin:

Input: [-10, 5, -3, 2]

Negatives as positive: [10, 3]
Sorted positives from negatives: [3, 10]
Reverse and restore signs: [-10, -3]

Non-negatives sorted: [2, 5]

Final result: [-10, -3, 2, 5]

Bu ek mantık gereklidir çünkü normal basamak basamak sıralama, negatif olmayan değerleri varsayar.

Pratik Örnek: Öğrenci Kimlik Numaralarını Sıralama

Radix Sıralama, sınırlı sayıda basamağa sahip sayısal kimlik numaralarını sıralarken kullanışlıdır.

Student IDs:
[1203, 1045, 1002, 1320, 1111]

Tüm kimlik numaraları dört basamaklıdır. Radix Sıralama onları basamak basamak sıralayabilir:

Sorted IDs:
[1002, 1045, 1111, 1203, 1320]

Bu tür veriler iyi bir uyum sağlar çünkü her sayının tahmin edilebilir bir basamak yapısı vardır.

Pratik Örnek: Ürün Kodlarını Sıralama

Ürün kodları sayısal ise, Radix Sıralama bunları verimli bir şekilde sıralamak için kullanılabilir.

Product codes:
[501, 120, 305, 220, 110]

Radix Sıralama'dan sonra:

[110, 120, 220, 305, 501]

Ancak, ürün kodları harfler, semboller veya karma formatlar içeriyorsa, algoritma eşleme veya farklı bir yaklaşıma ihtiyaç duyar.

Geliştiriciler Radix Sıralamayı Ne Zaman Kullanmalı?

Geliştiriciler, veriler algoritmanın varsayımlarına uyduğunda Radix Sıralama'yı düşünmelidir.

Radix Sıralama şu durumlarda kullanışlıdır:

  • Değerler negatif olmayan tam sayılardır.

  • Basamak sayısı sınırlıdır.

  • Basamak aralığı küçüktür.

  • Kararlı sıralama faydalıdır.

  • Giriş boyutu, doğrusal benzeri davranıştan faydalanacak kadar büyüktür.

  • Veriler, kimlikler veya kodlar gibi sabit uzunluklu sayısal anahtarlar kullanır.

Bu koşullar doğru olduğunda, Radix Sıralama çok verimli olabilir.

Radix Sıralama Ne Zaman Kullanılmamalıdır?

Radix Sıralama her zaman en iyi seçim değildir.

Geliştiriciler şu durumlarda Radix Sıralama'dan kaçınmalıdır:

  • Veriler sayısal değilse veya basamaklara temiz bir şekilde eşlenemiyorsa.

  • Sayıların çok fazla basamağı varsa.

  • Bellek kullanımı çok düşük olmalıdır.

  • Veri kümesi küçükse ve yerleşik bir sıralama daha basitse.

  • Uygulama, sorunun gerektirdiğinden daha karmaşık hale gelecekse.

  • Sıralama anahtarı karmaşık bir nesne karşılaştırmasıysa.

Birçok gerçek uygulamada, yerleşik sıralama fonksiyonları daha kolay, daha güvenli ve oldukça optimize edilmiştir. Radix Sıralama, varsayımları verilerle çok iyi eşleştiğinde en kullanışlıdır.

Radix Sıralama Uygulanırken Yapılan Yaygın Hatalar

Radix Sıralama, basit algoritmalardan daha fazla hareketli parçaya sahiptir, bu nedenle yeni başlayanlar genellikle basamak çıkarma, döngü koşulları veya kararlılıkta hata yaparlar.

Yaygın hatalar şunlardır:

  • Her basamak geçişi için kararsız bir sıralama yöntemi kullanmak.

  • Tüm basamak konumlarını işlemeyi unutmak.

  • Yanlış basamağı çıkarmak.

  • Maksimum değer için yanlış döngü koşulunu kullanmak.

  • Farklı basamak uzunluklarına sahip sayıları göz ardı etmek.

  • Ek işlem yapmadan negatif sayıları sıralamaya çalışmak.

  • Radix Sıralama'yı Sayarak Sıralama ile karıştırmak.

  • Onluk basamaklar için sayım dizisinin 10 konuma sahip olması gerektiğini unutmak.

En önemli hata, kararlılığı göz ardı etmektir. Kararlı basamak sıralaması olmadan, LSD Radix Sıralama yanlış sonuçlar verebilir.

Radix Sıralamayı Anlamak İçin Pratik Kontrol Listesi

Daha gelişmiş sıralama algoritmalarına geçmeden önce, geliştiriciler şu soruları yanıtlayabilmelidir:

  • Radix ne anlama gelir?

  • LSD ve MSD Radix Sıralama arasındaki fark nedir?

  • LSD Radix Sıralama neden birler basamağından başlar?

  • Radix Sıralama neden kararlı sıralamaya ihtiyaç duyar?

  • Sayarak Sıralama, Radix Sıralama'ya nasıl yardımcı olur?

  • Bir sayıdan basamak nasıl çıkarılır?

  • Zaman karmaşıklığı neden O(d × (n + k))'dir?

  • Radix Sıralama neden genellikle yerinde değildir?

  • Radix Sıralama, karşılaştırma tabanlı sıralamadan ne zaman daha iyidir?

Bu sorular açıksa, geliştirici sadece kod ezberlemek yerine Radix Sıralama'nın arkasındaki gerçek mantığı anlamıştır.

Radix Sıralama'nın Avantajları

Radix Sıralama, uygun verilerle kullanıldığında çeşitli avantajlara sahiptir.

  • Uygun durumlarda O(n log n) karşılaştırma tabanlı algoritmalardan daha hızlı olabilir.

  • Doğrudan öğe karşılaştırmalarına dayanmaz.

  • Sınırlı basamak uzunluğuna sahip tam sayılar için iyi çalışır.

  • Kararlı Sayarak Sıralama ile uygulandığında kararlı olabilir.

  • Kimlikleri, kodları ve sabit uzunluklu sayısal anahtarları sıralamak için kullanışlıdır.

  • Basamak işleme ve kararlı alt sıralama gibi önemli fikirleri öğretir.

Bu avantajlar, Radix Sıralama'yı veri yapıları ve algoritmalar eğitiminde önemli bir algoritma yapar.

Radix Sıralama'nın Dezavantajları

Radix Sıralama'nın ayrıca önemli sınırlamaları vardır.

  • Tüm veri türleri için genel amaçlı bir sıralama algoritması değildir.

  • Genellikle ek bellek gerektirir.

  • Basit sıralama algoritmalarından daha karmaşıktır.

  • Negatif sayılar için özel işlem gerektirir.

  • Sayıların çok fazla basamağı olduğunda verimli olmayabilir.

  • Kararlı bir dahili sıralama algoritmasına bağlıdır.

Radix Sıralama güçlüdür, ancak yalnızca veri yapısı ve değer formatı uygun olduğunda.

Sonuç

Radix Sıralama, sayıları basamak basamak sıralayan, karşılaştırma tabanlı olmayan bir sıralama algoritmasıdır. LSD Radix Sıralama'da, algoritma en anlamsız basamaktan başlar ve en anlamlı basamağa doğru ilerler.

Algoritma, her basamak konumu için kararlı Sayarak Sıralama'yı yardımcı olarak yaygın bir şekilde kullanır. Kararlılık esastır çünkü her geçiş, önceki basamak geçişlerinin oluşturduğu sırayı korumalıdır.

Radix Sıralama'nın zaman karmaşıklığı O(d × (n + k))'dir; burada n öğe sayısı, d basamak konumu sayısı ve k basamak aralığıdır. Onluk sayılar için k genellikle 10'dur, bu da Radix Sıralama'yı basamak sayısı sınırlı olduğunda verimli kılar.

Radix Sıralama her sorun için her zaman en iyi seçim değildir. Ek bellek gerektirir, negatif olmayan tam sayılarla en iyi şekilde çalışır ve negatif sayılar veya karmaşık veri türleri için ek mantığa ihtiyaç duyar.

Algoritma öğrenen geliştiriciler için Radix Sıralama değerlidir çünkü sıralama hakkında farklı bir düşünme biçimi sunar. Tam değerleri karşılaştırmak yerine, tamamen sıralanmış bir sonuç üretmek için basamakları, kararlı sıralamayı ve tekrar eden geçişleri kullanır. Radix Sıralama'yı anlamak, geliştiricinin Sayarak Sıralama, kararlılık ve karşılaştırma tabanlı olmayan algoritmalar hakkındaki anlayışını da güçlendirir.