🔢 7.9: Radix Sort (Basamak Sıralaması)

# ====================================
# RADIX SORT (LSD) ALGORİTMASI
# ====================================

def counting_sort_by_digit(arr, exp):
    """
    Belirli bir basamağa göre Counting Sort uygula.
    
    exp: 1 (birler), 10 (onlar), 100 (yüzler), ...
    """
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 0-9 arası basamaklar
    
    # Sayma: Her basamağın kaç kez göründüğünü say
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1
    
    # Kümülatif toplam
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # Çıktı oluştur (sondan başa - stability için)
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    
    # Orijinal diziye kopyala
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    """
    Radix Sort (LSD - Least Significant Digit)
    
    Zaman: O(d * n) - d: basamak sayısı
    Alan: O(n + 10) = O(n)
    Stable: Evet
    """
    if len(arr) == 0:
        return arr
    
    # Maksimum değeri bul (basamak sayısı için)
    max_val = max(arr)
    
    print(f"📊 Orijinal: {arr}")
    print(f"   Max değer: {max_val}")
    print("=" * 50)
    
    # Her basamak için Counting Sort
    exp = 1  # Birler, onlar, yüzler...
    digit_pos = 1
    
    while max_val // exp > 0:
        print(f"\n🔵 Tur {digit_pos}: {'Birler' if exp == 1 else 'Onlar' if exp == 10 else 'Yüzler' if exp == 100 else f'{exp}ler'} basamağı (exp={exp})")
        counting_sort_by_digit(arr, exp)
        print(f"   Sonuç: {arr}")
        
        exp *= 10
        digit_pos += 1
    
    return arr

# ============ TEST ============
print("🔢 RADIX SORT (LSD)")
print("=" * 50)

dizi = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(dizi)
print(f"\n✅ Sıralı dizi: {dizi}")

print("\n" + "=" * 50)
print("BÜYÜK SAYILARLA TEST")
print("=" * 50)

dizi2 = [329, 457, 657, 839, 436, 720, 355]
radix_sort(dizi2)
print(f"\n✅ Sıralı dizi: {dizi2}")