Radix mantığı

Sayıları basamak basamak sıralayan algoritmayı öğrenirsin.

Radix mantığı

Radix sort, sayıları basamak basamak sıralar. Önce birler basamağına göre, sonra onlar, sonra yüzler... Her başamakta kararlı bir alt sıralayıcı (genelde counting sort) kullanılır.

En az anlamlı başamaktan (LSD) başlayarak en çok anlamlıya doğru ilerleriz. Kararlılık sayesinde önceki basamakların sırası bozulmaz.

d basamak sayısı, k taban olmak üzere maliyet O(d(n + k)). Büyük sayılar için bile etkilidir.

LSD ve MSD

LSD radix sort en az anlamlı başamaktan başlar. Her başamakta tüm diziyi yeniden sıralar. Kararlılık olduğu için sonunda doğru sıra elde edilir.

MSD radix sort en çok anlamlı başamaktan başlar ve her grubu recursion ile ayırır. Daha karmaşıktır ama bazı durumlarda daha az geçiş yapar.

LSD daha kolay uygulanır ve genelde tercih edilir.

Uygulama Basamak al

get_digit(n, d) yaz. n sayısının d basamağını (0=birler) döndür. print(get_digit(738, 1)) ile 3 yazdır.

Örnek çözümü göster

def get_digit(n, d):
    # d. basamağı döndür
    return n // (10 ** d) % 10
print(get_digit(738, 1))

Kendini test et

Radix sort hangi alt sıralayıcıyı kullanır?
- Quick sort
- Kararlı counting sort
- Heap sort
- Selection sort
Cevabı göster

Kararlı counting sort — Kararlı counting sort

Basamak sayısı

d = len(str(____))

Cevabı göster

d = len(str(max(arr)))

Radix mantığı: kavramları eşleştir

LSD

Birler önce
MSD

Yüzler önce
Alt sıralayıcı

Counting sort
Maliyet

O(d(n+k))

Sıradaki ders: Basamak dolaşma

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler