Çıktı dizisi
- Algoritmalar kursu
- Orta seviye
- Ders 15/80
- 4 dk
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.
Başlangıç kodu
def counting_sort(arr):
# Sayarak sıralaÖrnek çözüm
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]))Beklenen çıktı
[1, 2, 2, 3, 3, 4, 8]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Çıktı dizisi: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Çıktı |
output |
Birikimli |
Konum |
Geriye dolaş |
Kararlı |
count -= 1 |
Yeri aç |
2 Counting sort neden kararlıdır?
- Rastgele sıralar
- Karşılaştırma yapmaz
- Sadece küçük dizide
- Sondan başa yerleştirir Doğru cevap
Açıklama: Sondan başa yerleştirir
3 Yerleştirme
output[count[arr[i]] - ____] = arr[i]output[count[arr[i]] - 1] = arr[i]Açıklama: 1 doğru.