Basamak dolaşma
- Algoritmalar kursu
- Orta seviye
- Ders 18/80
- 4 dk
En düşük başamaktan başlayıp her basamak için sıralama yapmayı öğrenirsin.
Basamak dolaşma
Her basamak geçişinde, tüm elemanları o basamağa göre sıralarız. Bu, counting sort kullanarak yapılır.
Basamak 0'dan 9'a kadar olduğu için aralık k=10'dur; counting sort çok hızlıdır. Her geçiş O(n + 10) = O(n).
d basamak için toplam d geçiş yapılır; toplam O(dn).
Kararlı alt sıralama
Radix sort'un çalışması, alt sıralayıcının kararlı olmasına bağlıdır. Kararlı değilse, önceki basamakların sırası bozulur ve sonuç yanlış olur.
Counting sort, sondan başa yerleştirme ile kararlıdır. Bu yüzden radix sort'un doğal seçimidir.
Eğer alt sıralayıcı kararlı değilse, radix sort kullanılamaz; çünkü her geçiş önceki sıralamayı bozar.
Uygulama Basamaklı counting sort
counting_by_digit(arr, d) yaz. Diziyi d. basamağa göre kararlı sırala. print(counting_by_digit([170, 45, 75, 90], 0)) ile [170, 90, 45, 75] yazdır.
Başlangıç kodu
def counting_by_digit(arr, d):
# d. basamağa göre sıralaÖrnek çözüm
def get_digit(n, d):
return n // (10 ** d) % 10
def counting_by_digit(arr, d):
# d. basamağa göre sırala
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
print(counting_by_digit([170, 45, 75, 90], 0))Beklenen çıktı
[170, 90, 45, 75]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Basamak aralığı
k = ____ # 0-9 aralığık = 10 # 0-9 aralığıAçıklama: 10 doğru.
2 Basamak dolaşma: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Basamak |
0-9 |
Alt sıralayıcı |
Counting sort |
Kararlı |
Şart |
Geçiş |
O(n) |
3 Radix sort neden counting sort kullanır?
- Daha az bellek
- Daha kolay
- Kararlı ve hızlı Doğru cevap
- Rastgele
Açıklama: Kararlı ve hızlı