Taban Sıralaması (Radix Sort)

#Nasıl çalışır?

Taban sıralaması (radix sort) sayıları basamak basamak sıralar. Bu derste kullanılan LSD (en önemsiz basamaktan başlayan) türü önce birler, sonra onlar, sonra yüzler basamağına göre sıralar.

Her turda kararlı bir sıralama (genellikle counting sort) kullanılır. Kararlılık şarttır: onlar basamağı eşit olan sayılar, önceki turda birler basamağına göre kazandıkları sırayı korumalıdır.

Son basamak turu bitince sayılar tamamen sıralanmış olur ve bu süreçte hiçbir karşılaştırma yapılmaz.

#Canlı animasyon

for exp = 1, 10, 100, … while exp <= max:
  digit(v) = (v / exp) mod 10
  stable counting sort of a by digit(v)
  // after the pass, a is sorted by its last digits

#Adım adım

1. 01En büyük sayının basamak sayısını bul.
2. 02Birler basamağına göre kararlı bir şekilde sırala.
3. 03Onlar basamağına göre kararlı bir şekilde sırala.
4. 04En büyük sayının tüm basamakları bitene kadar her basamak için tekrarla.
5. 05Dizi sıralanmıştır.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def sort_by_digit(a: list[int], exp: int) -> list[int]:
    """One stable counting-sort pass by the digit at `exp` (1, 10, 100, ...)."""
    count = [0] * 10
    for v in a:
        count[(v // exp) % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]
    output = [0] * len(a)
    # From the right, so numbers with the same digit keep their order.
    for v in reversed(a):
        d = (v // exp) % 10
        count[d] -= 1
        output[count[d]] = v
    return output


def radix_sort(a: list[int]) -> list[int]:
    """LSD radix sort for non-negative integers: ones digit first, then tens, ..."""
    exp = 1
    while a and max(a) // exp > 0:
        a = sort_by_digit(a, exp)
        exp *= 10
    return a


print(*radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

#Karmaşıklık

d basamak sayısı, b tabandır (burada 10). Basamak sayısı sabitse (örneğin 32 bitlik tam sayılar) süre doğrusaldır. Uzunlukları çok farklı ya da çok uzun anahtarlarda d büyür ve avantaj azalır.

#Ne zaman kullanılır?

Çok sayıda tam sayıyı, sabit uzunluklu anahtarları (posta kodu, telefon numarası, tarih) ya da eşit uzunluktaki dizgileri sıralarken karşılaştırmalı sıralamalardan hızlı olabilir. Ekran kartlarındaki paralel sıralamalarda da sık kullanılır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.