Özet - Radix sort
- Algoritmalar kursu
- Orta seviye
- Ders 20/80
- 4 dk
Radix sort uygulayıp sonucu yazdıran mini görev yaparsın.
Özet - Radix sort
Radix sort: basamak basamak, LSD'den başlayarak, kararlı counting sort ile. Karşılaştırmasız, O(dn).
d basamak sayısıdır; tamsayılar için log k kadardır (k en büyük değer). Büyük sayılar için bile etkilidir.
Negatif sayılar için kaydırma gerekir. Kararlılık şarttır; aksi halde sonuç yanlış olur.
Uygulama Özet: radix sort
radix_sort(arr) yaz. print(radix_sort([3,1,4,1,5,9,2,6])) ile [1, 1, 2, 3, 4, 5, 6, 9] yazdır.
Başlangıç kodu
def radix_sort(arr):
# Basamak basamak sıralaÖrnek çözüm
def get_digit(n, d):
return n // (10 ** d) % 10
def counting_by_digit(arr, d):
count = [0] * 10
for x in arr:
count[get_digit(x, d)] += 1
for i in range(1, 10):
count[i] += count[i - 1]
output = [0] * len(arr)
for i in range(len(arr) - 1, -1, -1):
digit = get_digit(arr[i], d)
output[count[digit] - 1] = arr[i]
count[digit] -= 1
return output
def radix_sort(arr):
# Basamak basamak sırala
if not arr:
return arr
max_digits = len(str(max(arr)))
for d in range(max_digits):
arr = counting_by_digit(arr, d)
return arr
print(radix_sort([3, 1, 4, 1, 5, 9, 2, 6]))Beklenen çıktı
[1, 1, 2, 3, 4, 5, 6, 9]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Radix sort: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Yöntem |
LSD |
Alt sıralayıcı |
Counting sort |
Maliyet |
O(dn) |
Kararlı |
Şart |
2 Başlangıç
Soru
En az anlamlı basamak: d = ____
Cevap
En az anlamlı basamak: d = 0Açıklama: 0 doğru.
3 Radix sort karşılaştırma yapar mı?
- Hayır Doğru cevap
- Sadece küçük dizide
- Sadece büyük dizide
- Evet
Açıklama: Hayır