Sayma mantığı

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.

Örnek çözümü göster

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

Kendini test et

Counting sort ne zaman verimlidir?
- Her zaman
- Küçük tamsayı aralığında
- Sadece büyük dizilerde
- Sadece metinde
Cevabı göster

Küçük tamsayı aralığında — Küçük tamsayı aralığında

Aralık boyutu

k = max(arr) - min(arr) + ____

Cevabı göster

k = max(arr) - min(arr) + 1

Sayma mantığı: kavramları eşleştir

Counting sort

Karşılaştırmaz
Maliyet

O(n+k)
Bellek

O(k)
Aralık

Dar olmalı

Sıradaki ders: Sayı dizisi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler