Çıktı dizisi

Sayım dizisini kullanıp kararlı çıktı dizisi üretmeyi öğrenirsin.

Çıktı dizisi

Çıktı dizisi, sayı dizisinin birikimli toplamından üretilir. Her eleman, birikimli count'ın gösterdiği konuma yerleştirilir; böylece doğru sıralı konum bulunur.

Kararlılık için diziyi sondan başa dolaşırız: output[count[arr[i]] - 1] = arr[i], sonra count[arr[i]] -= 1. Bu, aynı anahtara sahip elemanların sırasını korur.

Sondan başa gitmek, eşit elemanların göreli sırasını korur. Bu sayede counting sort kararlıdır ve radix sort'un temelidir.

Kararlılık

Counting sort, sondan başa yerleştirme sayesinde kararlıdır. İlk geçen eşit eleman, sıralı dizide de önce kalır; bu sıra bozulmadan korunur.

Bu, satellite verisi olan kayıtları sıralarken önemlidir: eşit anahtarlı kayıtların orijinal sırası korunur ve ikincil bilgi kaybolmaz.

Radix sort'un kararlılığı, bu counting sort kararlılığına dayanır; bu yüzden radix sort her başamakta counting sort kullanır.

Uygulama Counting sort

counting_sort(arr) yaz. Sayı dizisi + birikimli + geriye yerleştir. print(counting_sort([4, 2, 2, 8, 3, 3, 1])) ile [1, 2, 2, 3, 3, 4, 8] yazdır.

Örnek çözümü göster

def counting_sort(arr):
    # Sayarak sırala
    if not arr:
        return []
    k = max(arr) + 1
    count = [0] * k
    for x in arr:
        count[x] += 1
    for i in range(1, k):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output
print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

Kendini test et

Çıktı dizisi: kavramları eşleştir

Çıktı

output
Birikimli

Konum
Geriye dolaş

Kararlı
count -= 1

Yeri aç
Counting sort neden kararlıdır?
- Rastgele sıralar
- Karşılaştırma yapmaz
- Sadece küçük dizide
- Sondan başa yerleştirir
Cevabı göster

Sondan başa yerleştirir — Sondan başa yerleştirir

Yerleştirme

output[count[arr[i]] - ____] = arr[i]

Cevabı göster

output[count[arr[i]] - 1] = arr[i]

Sıradaki ders: Özet - Counting sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler