Basamak dolaşma

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.

Örnek çözümü göster

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))

Kendini test et

Basamak aralığı

k = ____  # 0-9 aralığı

Cevabı göster

k = 10  # 0-9 aralığı

Basamak dolaşma: kavramları eşleştir

Basamak

0-9
Alt sıralayıcı

Counting sort
Kararlı

Şart
Geçiş

O(n)
Radix sort neden counting sort kullanır?
- Daha az bellek
- Daha kolay
- Kararlı ve hızlı
- Rastgele
Cevabı göster

Kararlı ve hızlı — Kararlı ve hızlı

Sıradaki ders: Kararlı alt sıralama

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler