🔢 7.8: Counting Sort (Sayma Sıralaması)

# ====================================
# COUNTING SORT ALGORİTMASI
# ====================================

def counting_sort(arr):
    """
    Counting Sort - Non-comparison sıralama
    
    Zaman: O(n + k) - n: eleman sayısı, k: değer aralığı
    Alan: O(n + k) - count ve output dizileri
    Stable: Evet (sondan başa tarama ile)
    
    Kısıtlamalar:
    - Sadece non-negative integer
    - k çok büyükse verimsiz
    """
    if len(arr) == 0:
        return arr
    
    # Adım 1: Min ve max bul
    min_val = min(arr)
    max_val = max(arr)
    k = max_val - min_val + 1  # Aralık
    
    print(f"📊 Dizi: {arr}")
    print(f"   Min: {min_val}, Max: {max_val}, Aralık (k): {k}")
    
    # Adım 2: Sayma dizisi oluştur
    count = [0] * k
    
    # Adım 3: Elemanları say
    for x in arr:
        count[x - min_val] += 1
    print(f"\n🔢 Sayma dizisi: {count}")
    
    # Adım 4: Kümülatif toplam
    for i in range(1, k):
        count[i] += count[i - 1]
    print(f"📈 Kümülatif: {count}")
    
    # Adım 5: Çıktı dizisi oluştur (sondan başa - stability için)
    output = [0] * len(arr)
    
    for i in range(len(arr) - 1, -1, -1):
        x = arr[i]
        idx = x - min_val
        output[count[idx] - 1] = x
        count[idx] -= 1
    
    print(f"\n✅ Sıralı: {output}")
    return output

# ============ TEST ============
print("=" * 50)
print("COUNTING SORT")
print("=" * 50)

dizi = [4, 2, 2, 8, 3, 3, 1]
counting_sort(dizi)

print("\n" + "=" * 50)
print("NEGATİF SAYILARLA TEST")
print("=" * 50)

dizi2 = [4, -2, 2, -8, 3, -3, 1]
counting_sort(dizi2)