Radix mantığı
- Algoritmalar kursu
- Orta seviye
- Ders 17/80
- 4 dk
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.
Başlangıç kodu
def get_digit(n, d):
# d. basamağı döndürÖrnek çözüm
def get_digit(n, d):
# d. basamağı döndür
return n // (10 ** d) % 10
print(get_digit(738, 1))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Radix sort hangi alt sıralayıcıyı kullanır?
- Quick sort
- Kararlı counting sort Doğru cevap
- Heap sort
- Selection sort
Açıklama: Kararlı counting sort
2 Basamak sayısı
d = len(str(____))d = len(str(max(arr)))Açıklama: max(arr) doğru.
3 Radix mantığı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
LSD |
Birler önce |
MSD |
Yüzler önce |
Alt sıralayıcı |
Counting sort |
Maliyet |
O(d(n+k)) |