Sıralama algoritmaları: analiz, alt sınır, counting ve radix sort

SEN2211’in sonunda bubble, selection ve insertion sort gibi basit $O(n^2)$ sıralamaları gördün. Bu derste soru seviyesi bir basamak yukarı çıkıyor. Sınavda üç tip soru gelir: iz sür (merge’den önceki yarılar ne, ilk partition’dan sonra dizi ne, buildHeap’ten sonra heap ne), analiz et (en iyi, ortalama, en kötü durum, kaç karşılaştırma), karşılaştır (hangisi stabil, hangisi yerinde, ne zaman hangisi).

Altın kurallar:

1. Merge sort her durumda $O(n \log n)$, ama $O(n)$ ek bellek ister.
2. Quicksort ortalamada en hızlısı, ama kötü pivotla $O(n^2)$ olur.
3. Heapsort her durumda $O(n \log n)$ ve yerinde, ama stabil değil.
4. Karşılaştırma yapan hiçbir sıralama en kötü durumda $\Omega(n \log n)$‘den iyi olamaz.
5. Counting ve radix sort bu sınırı aşar, çünkü karşılaştırma yapmaz; anahtarlara ek varsayım koyar.

Merge sort

Böl ve yönet (divide and conquer). Diziyi ortadan ikiye böl, iki yarıyı özyinelemeli sırala, sonra iki sıralı yarıyı tek geçişte birleştir (merge). Merge adımı her iki listenin başına bakar, küçüğü çıktıya yazar.

static void mergeSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;          // 0 ya da 1 eleman: zaten sıralı
    int mid = (lo + hi) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);         // O(hi - lo + 1)
}

[42, 17, 8, 93, 25, 61, 4, 30] için merge çağrılarının sırası (her satır bir merge sonrası o aralığın durumu):

merge [0..1] -> [17, 42]
merge [2..3] -> [8, 93]
merge [0..3] -> [8, 17, 42, 93]
merge [4..5] -> [25, 61]
merge [6..7] -> [4, 30]
merge [4..7] -> [4, 25, 30, 61]
merge [0..7] -> [4, 8, 17, 25, 30, 42, 61, 93]
toplam karşılaştırma: 17

Dikkat et: sol yarı tamamen bitmeden sağ yarıya geçilmez. “İkinci merge hangisi?” sorusunda cevap [2..3], [4..5] değil.

Analiz

Yineleme bağıntısı (recurrence):

$T(n) = 2T(n/2) + cn, \qquad T(1) = c$

Özyineleme ağacının her seviyesinde toplam iş $cn$, seviye sayısı $\log_2 n$. Sonuç $T(n) = O(n \log n)$. Bu süre girdiden bağımsız: sıralı, ters sıralı, rastgele hepsinde aynı. Ek bellek $O(n)$, çünkü merge geçici dizi kullanır.

Quicksort

Bir pivot seç. Diziyi pivottan küçükler sola, büyükler sağa gelecek şekilde böl (partition). Pivot artık son yerinde. İki tarafı özyinelemeli sırala. Birleştirme adımı yok, iş partition’da.

Bu sayfada Lomuto şemasını kullanıyoruz: pivot son eleman, i küçükler bölgesinin sonunu tutar.

static int partition(int[] a, int lo, int hi) {
    int p = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] < p) { i++; swap(a, i, j); }
    swap(a, i + 1, hi);            // pivot yerine
    return i + 1;
}

[29, 71, 12, 55, 8, 40, 33] üzerinde tam iz:

partition [0..6] pivot=33 -> [29,12,8,33,71,40,55]
partition [0..2] pivot=8  -> [8,12,29,33,71,40,55]
partition [1..2] pivot=29 -> [8,12,29,33,71,40,55]
partition [4..6] pivot=55 -> [8,12,29,33,40,55,71]

İlk partition’da 29, 12, 8 pivottan küçük olduğu için öne toplandı; 33 indeks 3’e oturdu ve bir daha hiç yer değiştirmedi.

Analiz

En kötü durumda bağıntı $T(n) = T(n-1) + cn$ olur, toplam $n(n-1)/2$ karşılaştırma. Son eleman pivot olduğunda zaten sıralı dizi tam bu durumu üretir. Pratik çözümler: rastgele pivot ya da median-of-three (ilk, orta, son elemanın ortancası). Küçük alt dizilerde (n < 10 civarı) insertion sort’a geçmek de yaygın.

TUZAK · “quicksort her zaman n log n”. Değil. Ortalama ve en iyi durum $O(n \log n)$, en kötü $O(n^2)$. Sınavda “worst case” soruluyorsa cevap $O(n^2)$.

Heapsort

Heap’leri 7. haftada ayrıntılı göreceğiz. Şimdilik bilmen gereken: max-heap, her düğümün çocuklarından büyük ya da eşit olduğu tam ikili ağaç (complete binary tree) ve dizide saklanır. 0 indeksli dizide i’nin çocukları 2i+1 ve 2i+2.

Heapsort iki aşamalı:

1. buildHeap: son iç düğümden (n/2 - 1) köke kadar her düğümü aşağı süz (percolate down). Süre $O(n)$.
2. n - 1 kez deleteMax: kökü (en büyük) heap’in son elemanıyla takas et, heap boyutunu 1 azalt, yeni kökü aşağı süz. Her biri $O(\log n)$.

[6, 3, 9, 1, 8, 2] için:

buildHeap   -> [9, 8, 6, 1, 3, 2]
deleteMax 1 -> [8, 3, 6, 1, 2 | 9]
deleteMax 2 -> [6, 3, 2, 1 | 8, 9]
deleteMax 3 -> [3, 1, 2 | 6, 8, 9]
deleteMax 4 -> [2, 1 | 3, 6, 8, 9]
deleteMax 5 -> [1 | 2, 3, 6, 8, 9]

| işaretinin sağı sıralı bölge. Max-heap kullanınca dizi artan sırada biter, çünkü her adımda en büyük sona yazılır. Toplam süre her durumda $O(n \log n)$, ek bellek $O(1)$.

Karşılaştırmalı sıralamanın alt sınırı

Sadece a[i] < a[j] gibi karşılaştırmalarla çalışan her algoritma bir karar ağacı (decision tree) ile gösterilebilir. Her iç düğüm bir karşılaştırma, her yaprak girdinin bir sıralaması (permutation).

• n farklı eleman için $n!$ olası sıra var. Algoritma hepsini ayırt etmeli: en az $n!$ yaprak.
• Yüksekliği $h$ olan ikili ağaçta en fazla $2^h$ yaprak olur.
• $2^h \ge n! \Rightarrow h \ge \log_2(n!)$.
• Stirling yaklaşımıyla $\log_2(n!) = \Theta(n \log n)$.

Ağacın yüksekliği en kötü durumdaki karşılaştırma sayısıdır. Sonuç:

$\text{worst-case comparisons} \ge \lceil \log_2 n! \rceil = \Omega(n \log n)$

Bu yüzden merge sort ve heapsort asimptotik olarak optimal karşılaştırmalı sıralamalardır.

Counting sort

Anahtarlar 0..k arasında tam sayıysa, karşılaştırmadan sıralayabilirsin. Her değerin kaç kez geçtiğini say, prefix toplamla her değerin çıktıdaki konumunu bul, girdiyi sağdan sola gezerek yerleştir.

[2, 5, 3, 0, 2, 3, 0, 3], k = 5:

count  = [2, 0, 2, 3, 0, 1]
prefix = [2, 2, 4, 7, 7, 8]
output = [0, 0, 2, 2, 3, 3, 3, 5]

prefix[3] = 7 demek: 3’lerin sonuncusu çıktının 6. indeksine (7 - 1) gider. Her yerleştirmede sayaç bir azalır. Sağdan sola gezmek eşit anahtarların sırasını korur: sıralama stabil. Süre $O(n + k)$, bellek $O(n + k)$. k çok büyükse (örn. 32 bitlik sayılar) pratik değil.

Radix sort

Çok basamaklı sayıları en düşük basamaktan (LSD, least significant digit) başlayarak, her basamak için stabil bir kova/counting geçişiyle sırala.

[329, 457, 657, 839, 436, 720, 355]:

birler  -> [720, 355, 436, 457, 657, 329, 839]
onlar   -> [720, 329, 436, 839, 355, 457, 657]
yüzler  -> [329, 355, 436, 457, 657, 720, 839]

İkinci geçişte 720 ile 329’un onlar basamağı 2, ikisi aynı kovada. Birinci geçişteki sıralarını (720 önce) korudular. Her geçiş stabil olmak zorunda, yoksa önceki basamakların emeği kaybolur.

Süre: d basamak, taban b için $O(d(n + b))$. d ve b sabitse lineer.

Özet tablo

Sık yapılan hatalar

static void merge(int[] a, int lo, int mid, int hi) {
    int[] tmp = new int[hi - lo + 1];
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    for (k = 0; k < tmp.length; k++) a[lo + k] = tmp[k];
}