Sayma mantığı
- Algoritmalar kursu
- Orta seviye
- Ders 13/80
- 4 dk
Her değerin sayısını sayıp kümülatif toplamla diziyi sıralamayı öğrenirsin.
Sayma mantığı
Counting sort, karşılaştırma yapmadan sıralar. Her elemanın kaç kez geçtiğini sayar, sonra sıralı çıktıyı bu sayılardan üretir.
Anahtarlar küçük tamsayı aralığında olduğunda O(n + k) çalışır; k anahtar aralığıdır. Karşılaştırmalı sıralamalardan hızlıdır.
Ancak aralık büyükse k belleği patlar. Bu yüzden yalnızca küçük aralıklı tamsayı anahtarlar için uygundur.
Aralık maliyeti
Counting sort, 0'dan max(arr)'a kadar bir sayı dizisi oluşturur. Aralık k = max - min + 1.
Bellek O(k). Eğer k çok büyükse (ör. 0'dan milyona), bu diziyi tutmak pahalıdır.
Bu yüzden counting sort, anahtarların yoğun olduğu dar aralıklarda en iyisidir. Negatif sayılar için kaydırma (offset) gerekir.
Uygulama Eleman say
count_value(arr, v) yaz. arr içinde v'nin kaç kez geçtiğini say. print(count_value([3, 1, 4, 1, 5, 1], 1)) ile 3 yazdır.
Başlangıç kodu
def count_value(arr, v):
# v'yi sayÖrnek çözüm
def count_value(arr, v):
# v'yi say
count = 0
for x in arr:
if x == v:
count += 1
return count
print(count_value([3, 1, 4, 1, 5, 1], 1))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Counting sort ne zaman verimlidir?
- Her zaman
- Küçük tamsayı aralığında Doğru cevap
- Sadece büyük dizilerde
- Sadece metinde
Açıklama: Küçük tamsayı aralığında
2 Aralık boyutu
k = max(arr) - min(arr) + ____k = max(arr) - min(arr) + 1Açıklama: 1 doğru.
3 Sayma mantığı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Counting sort |
Karşılaştırmaz |
Maliyet |
O(n+k) |
Bellek |
O(k) |
Aralık |
Dar olmalı |