Özet - Counting sort
- Algoritmalar kursu
- Orta seviye
- Ders 16/80
- 4 dk
Counting sort uygulayıp sonucu yazdıran mini görev yaparsın.
Özet - Counting sort
Counting sort: say + birikimli + geriye yerleştir. Karşılaştırmasız, O(n + k), kararlı. k anahtar aralığıdır.
Küçük tamsayı aralığında hızlıdır; büyük aralıkta bellek patlar. Negatif değerler için kaydırma gerekir.
Radix sort'un alt sıralayıcısı olarak kullanılır; bu sayede büyük sayılar da sıralanabilir.
Uygulama Özet: counting sort
counting_sort(arr) yaz. print(counting_sort([5,1,4,2,8,2])) ile [1, 2, 2, 4, 5, 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([5, 1, 4, 2, 8, 2]))Beklenen çıktı
[1, 2, 2, 4, 5, 8]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Counting sort: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Maliyet |
O(n+k) |
Bellek |
O(k) |
Kararlı |
Evet |
Aralık |
Dar olmalı |
2 Birikimli
Soru
count[i] ____count[i-1]
Cevap
count[i] +=count[i-1]Açıklama: += doğru.
3 Counting sort karşılaştırma yapar mı?
- Hayır Doğru cevap
- Sadece küçük dizide
- Sadece büyük dizide
- Evet, her zaman
Açıklama: Hayır