🧩 7.10: Sıralama Örnek Sorular

# =========================================
# K'INCI EN BÜYÜK ELEMANI BULMA
# =========================================

import heapq

def kinci_en_buyuk_siralama(arr, k):
    """
    Yöntem 1: Sıralama ile
    Zaman: O(n log n)
    Alan: O(n) (sort için)
    """
    return sorted(arr, reverse=True)[k-1]

def kinci_en_buyuk_heap(arr, k):
    """
    Yöntem 2: Min-Heap ile
    Zaman: O(n log k)
    Alan: O(k)
    
    Fikir: K elemanlı min-heap tut.
    - Yeni eleman heap'in minimum'undan büyükse, 
      minimum'u çıkar ve yeni elemanı ekle.
    - Sonunda heap'in minimum'u (root) k'ıncı en büyük!
    """
    # İlk k elemanla heap oluştur
    heap = arr[:k].copy()
    heapq.heapify(heap)
    
    # Kalan elemanları işle
    for i in range(k, len(arr)):
        if arr[i] > heap[0]:  # heap[0] = minimum
            heapq.heapreplace(heap, arr[i])
    
    return heap[0]

def quickselect(arr, k):
    """
    Yöntem 3: QuickSelect
    Zaman: O(n) average, O(n²) worst
    Alan: O(1)
    
    Quick Sort'un partitioning fikrini kullan,
    ama sadece k'ıncı elemanın olduğu tarafa git.
    """
    # k'ıncı en büyük = (n-k)'ıncı en küçük (0-indexed)
    target = len(arr) - k
    
    def partition(left, right, pivot_idx):
        pivot = arr[pivot_idx]
        # Pivot'u sona taşı
        arr[pivot_idx], arr[right] = arr[right], arr[pivot_idx]
        store_idx = left
        
        for i in range(left, right):
            if arr[i] < pivot:
                arr[i], arr[store_idx] = arr[store_idx], arr[i]
                store_idx += 1
        
        arr[store_idx], arr[right] = arr[right], arr[store_idx]
        return store_idx
    
    def select(left, right):
        if left == right:
            return arr[left]
        
        # Orta elemanı pivot olarak seç
        pivot_idx = (left + right) // 2
        pivot_idx = partition(left, right, pivot_idx)
        
        if target == pivot_idx:
            return arr[target]
        elif target < pivot_idx:
            return select(left, pivot_idx - 1)
        else:
            return select(pivot_idx + 1, right)
    
    return select(0, len(arr) - 1)

# ============ TEST ============
print("🎯 K'INCI EN BÜYÜK ELEMAN")
print("=" * 50)

arr1 = [3, 2, 1, 5, 6, 4]
k1 = 2

print(f"Dizi: {arr1}, k={k1}")
print(f"Sıralama ile: {kinci_en_buyuk_siralama(arr1, k1)}")
print(f"Heap ile: {kinci_en_buyuk_heap(arr1, k1)}")
print(f"QuickSelect ile: {quickselect(arr1.copy(), k1)}")

print()
arr2 = [3, 2, 3, 1, 2, 4, 5, 5, 6]
k2 = 4
print(f"Dizi: {arr2}, k={k2}")
print(f"Sıralama ile: {kinci_en_buyuk_siralama(arr2, k2)}")

# =========================================
# DUTCH NATIONAL FLAG (3-WAY PARTITIONING)
# =========================================

def dutch_flag_counting(arr):
    """
    Yöntem 1: Counting Sort yaklaşımı
    Zaman: O(n) (2 geçiş)
    Alan: O(1)
    """
    count = [0, 0, 0]
    for x in arr:
        count[x] += 1
    
    idx = 0
    for num in range(3):
        for _ in range(count[num]):
            arr[idx] = num
            idx += 1
    return arr

def dutch_flag_partition(arr):
    """
    Yöntem 2: Three-way Partitioning (Dijkstra)
    Zaman: O(n) (TEK geçiş!)
    Alan: O(1)
    
    low: 0'ların biteceği yer (sol taraf)
    mid: şu an incelenen index
    high: 2'lerin başlayacağı yer (sağ taraf)
    """
    low = 0
    mid = 0
    high = len(arr) - 1
    
    print(f"Başlangıç: {arr}")
    print("-" * 40)
    
    while mid <= high:
        if arr[mid] == 0:
            # 0 görünce sola at
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
            print(f"0 bulundu, swap(low,mid): {arr}")
        elif arr[mid] == 1:
            # 1 yerinde, sadece ilerle
            mid += 1
            print(f"1 bulundu, mid++: {arr}")
        else:  # arr[mid] == 2
            # 2 görünce sağa at
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
            # mid artmaz! Swap edilen değeri kontrol etmeli
            print(f"2 bulundu, swap(mid,high): {arr}")
    
    return arr

# ============ TEST ============
print("🇳🇱 DUTCH NATIONAL FLAG")
print("=" * 50)

arr1 = [2, 0, 2, 1, 1, 0]
print(f"\n📍 Test 1: {arr1}")
dutch_flag_partition(arr1.copy())
print(f"Sonuç: {dutch_flag_partition([2, 0, 2, 1, 1, 0])}")

print("\n" + "=" * 50)
arr2 = [2, 0, 1]
print(f"\n📍 Test 2: {[2, 0, 1]}")
result = dutch_flag_partition(arr2)
print(f"Sonuç: {result}")

# =========================================
# NEREDEYSE SIRALI DİZİYİ SIRALAMA
# =========================================

import heapq

def sort_nearly_sorted_insertion(arr, k):
    """
    Yöntem 1: Insertion Sort
    Zaman: O(n * k)
    Alan: O(1)
    
    Her eleman max k adım kayar.
    """
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # Maximum k adım geriye bak
        while j >= max(0, i - k) and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

def sort_nearly_sorted_heap(arr, k):
    """
    Yöntem 2: Min-Heap
    Zaman: O(n * log k)
    Alan: O(k)
    
    k+1 elemanlık sliding window heap kullan.
    """
    n = len(arr)
    
    # İlk k+1 elemanla heap oluştur
    heap = arr[:k+1].copy()
    heapq.heapify(heap)
    
    result_idx = 0
    
    print(f"Başlangıç heap (ilk {k+1} eleman): {heap}")
    
    # Kalan elemanları işle
    for i in range(k + 1, n):
        # Heap'ten minimum'u çıkar ve sonuca ekle
        arr[result_idx] = heapq.heappop(heap)
        result_idx += 1
        
        # Yeni elemanı heap'e ekle
        heapq.heappush(heap, arr[i])
        print(f"Min çıktı: {arr[result_idx-1]}, heap: {heap}")
    
    # Kalan elemanları boşalt
    while heap:
        arr[result_idx] = heapq.heappop(heap)
        result_idx += 1
    
    return arr

# ============ TEST ============
print("📊 NEREDEYSE SIRALI DİZİYİ SIRALAMA")
print("=" * 50)

arr = [6, 5, 3, 2, 8, 10, 9]
k = 3

print(f"Orijinal: {arr}")
print(f"k = {k} (her eleman max {k} uzaklıkta)")
print()

# Heap yöntemi
result = sort_nearly_sorted_heap(arr.copy(), k)
print(f"\n✅ Sıralı (Heap): {result}")

# Insertion sort karşılaştırması
result2 = sort_nearly_sorted_insertion(arr.copy(), k)
print(f"✅ Sıralı (Insertion): {result2}")

print("\n" + "=" * 50)
print("⏱️ Karmaşıklık:")
print(f"   Insertion Sort: O(n*k) = O({len(arr)}*{k}) = O({len(arr)*k})")
print(f"   Min-Heap: O(n*log k) = O({len(arr)}*log{k}) ≈ O({len(arr)*2})")

# =========================================
# İKİ SIRALI DİZİYİ BİRLEŞTİR (MERGE)
# =========================================

def merge_sorted_arrays(arr1, arr2):
    """
    Two Pointer ile birleştirme
    Zaman: O(n + m)
    Alan: O(n + m)
    """
    result = []
    i, j = 0, 0
    
    print(f"arr1: {arr1}")
    print(f"arr2: {arr2}")
    print("-" * 40)
    
    # İki dizi de bitene kadar karşılaştır
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            print(f"arr1[{i}]={arr1[i]} eklendi")
            i += 1
        else:
            result.append(arr2[j])
            print(f"arr2[{j}]={arr2[j]} eklendi")
            j += 1
    
    # Kalan elemanları ekle
    while i < len(arr1):
        result.append(arr1[i])
        i += 1
    
    while j < len(arr2):
        result.append(arr2[j])
        j += 1
    
    return result

# ============ TEST ============
print("🔗 İKİ SIRALI DİZİYİ BİRLEŞTİR")
print("=" * 50)

arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]

result = merge_sorted_arrays(arr1, arr2)
print(f"\n✅ Birleşik: {result}")

print("\n" + "=" * 50)
print("\n📍 Farklı uzunluklar:")
arr3 = [1, 2, 3]
arr4 = [4, 5, 6, 7, 8, 9]
result2 = merge_sorted_arrays(arr3, arr4)
print(f"✅ Birleşik: {result2}")

# =========================================
# ARALIKLARI BİRLEŞTİR (MERGE INTERVALS)
# =========================================

def merge_intervals(intervals):
    """
    Örtüşen aralıkları birleştir
    Zaman: O(n log n) - sıralama
    Alan: O(n) - sonuç listesi
    """
    if not intervals:
        return []
    
    # Başlangıç noktasına göre sırala
    intervals.sort(key=lambda x: x[0])
    print(f"Sıralı: {intervals}")
    
    result = [intervals[0]]
    
    for i in range(1, len(intervals)):
        current = intervals[i]
        last = result[-1]
        
        # Birleşebilir mi? (öncekinin sonu >= sonrakinin başı)
        if last[1] >= current[0]:
            # Birleştir: sonuç aralığının sonunu güncelle
            result[-1][1] = max(last[1], current[1])
            print(f"{last} + {current} → birleşti: {result[-1]}")
        else:
            # Ayrı aralık
            result.append(current)
            print(f"{current} ayrı eklendi")
    
    return result

# ============ TEST ============
print("📅 MERGE INTERVALS")
print("=" * 50)

intervals1 = [[1,3], [2,6], [8,10], [15,18]]
print(f"Giriş: {intervals1}")
result1 = merge_intervals([x.copy() for x in intervals1])
print(f"✅ Sonuç: {result1}")

print("\n" + "=" * 50)
intervals2 = [[1,4], [4,5]]
print(f"\nGiriş: {intervals2}")
result2 = merge_intervals([x.copy() for x in intervals2])
print(f"✅ Sonuç: {result2}")

print("\n" + "=" * 50)
intervals3 = [[1,4], [0,4]]  # Sırasız
print(f"\nGiriş (sırasız): {intervals3}")
result3 = merge_intervals([x.copy() for x in intervals3])
print(f"✅ Sonuç: {result3}")