Kararlı alt sıralama
- Algoritmalar kursu
- Orta seviye
- Ders 19/80
- 4 dk
Her başamakta kararlı bir alt sıralama kullanmanın önemini öğrenirsin.
Kararlı alt sıralama
Tam radix sort, basamak dolaşma adımını her basamak için tekrarlar. En az anlamlı başamaktan başlar, en çok anlamlıya kadar gider.
Her geçiş kararlı olduğu için, bir önceki geçişin sırası korunur ve yeni basamak bilgi ekler. Sonunda dizi tam sıralanır.
Basamak sayısı d = len(str(max(arr))). Toplam maliyet O(dn).
Negatif sayılar
Radix sort varsayılan olarak negatif olmayan tamsayıları sıralar. Negatif sayılar için iki yaygın yöntem vardır.
Birincisi: tüm sayılara sabit bir kaydırma ekleyip pozitif yap, sırala, sonra kaydırmayı çıkar. İkincisi: işaret ve mutlak değere göre ayrı grupla.
Her iki yöntem de O(dn) maliyeti korur, ama uygulama daha dikkatli ister.
Uygulama Radix sort
radix_sort(arr) yaz. LSD yöntemiyle basamak basamak sırala. print(radix_sort([170, 45, 75, 90, 2, 24])) ile [2, 24, 45, 75, 90, 170] 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([170, 45, 75, 90, 2, 24]))Beklenen çıktı
[2, 24, 45, 75, 90, 170]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kararlı alt sıralama: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
LSD |
Başlangıç |
Geçiş |
Kararlı |
Basamak sayısı |
d |
Toplam |
O(dn) |
2 Radix sort kaç geçiş yapar?
- 1
- log n
- n
- d (basamak sayısı) Doğru cevap
Açıklama: d (basamak sayısı)
3 Döngü sınırı
for d in range(____):for d in range(max_digits):Açıklama: max_digits doğru.