Sıralama II: merge sort, quick sort, heap sort

13. haftadaki üç algoritma O(n²): bir milyon elemanda yaklaşık 10¹² adım, saatler. Bu hafta böl ve yönet (divide and conquer) fikriyle O(n log n)‘e iniyoruz: aynı milyon eleman 2 · 10⁷ adım, saniyenin altında. İki ana algoritma var: merge sort işi birleştirme adımında yapar, quick sort işi bölme adımında yapar. Üçüncüsü heap sort, bir sonraki dersin veri yapısı olan heap’i kullanır; burada genel fikrini görüyoruz. Sınavda merge adımlarının sırası, partition izi ve karşılaştırma tablosu sorulur.

Altın kurallar:

1. Merge sort: böl (kolay), birleştir (asıl iş). Her durumda O(n log n), O(n) ek bellek, kararlı.
2. Quick sort: bölümle (asıl iş), birleştirme yok. Ortalama O(n log n), kötü pivotta O(n²).
3. Partition sonrası pivot nihai yerindedir. İki taraf kendi içinde sırasızdır.
4. İz yazarken hangi partition şemasının kullanıldığına bak. Bu sayfada Lomuto, pivot = son eleman.

Merge sort

Fikir: tek elemanlı dizi zaten sıralıdır. Diziyi ikiye böl, her yarıyı (özyinelemeyle) sırala, sonra iki sıralı yarıyı birleştir.

static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return;               // 0 ya da 1 eleman
    int mid = (lo + hi) / 2;
    mergeSort(a, tmp, lo, mid);
    mergeSort(a, tmp, mid + 1, hi);
    merge(a, tmp, lo, mid, hi);
}

static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    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 = lo; k <= hi; k++) a[k] = tmp[k];
}

merge, 4. haftada bağlı listede yazdığımız birleştirmenin dizi versiyonu. Fark: dizide yerinde birleştiremezsin, yardımcı bir diziye (tmp) yazıp geri kopyalarsın.

İz: {38, 27, 43, 3, 9, 82, 10}

                [38, 27, 43, 3, 9, 82, 10]
               /                          \
      [38, 27, 43, 3]                [9, 82, 10]
       /          \                   /        \
   [38, 27]     [43, 3]           [9, 82]      [10]
    /    \       /   \             /   \
  [38]  [27]   [43]  [3]         [9]  [82]

Birleştirmeler (program çıktısı, gerçekleştiği sırayla):

merge [38] + [27] -> [27, 38]
merge [43] + [3] -> [3, 43]
merge [27, 38] + [3, 43] -> [3, 27, 38, 43]
merge [9] + [82] -> [9, 82]
merge [9, 82] + [10] -> [9, 10, 82]
merge [3, 27, 38, 43] + [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]
[3, 9, 10, 27, 38, 43, 82] comps=14

TUZAK · Birleştirme sırası seviye seviye değildir. Özyineleme sol tarafı tamamen bitirip sonra sağa geçer. [9, 82]‘nin birleşmesi, [3, 27, 38, 43] oluştuktan sonra gelir. “Önce bütün ikilileri birleştir” diye yazarsan sıra yanlış olur (o, aşağıdan yukarı merge sort’un sırasıdır).

Karmaşıklık

$T(n) = 2T(n/2) + n$ → $O(n \log n)$ (11. hafta). Bölme her zaman ortadan olduğu için en iyi, ortalama, en kötü aynı. Tek merge’de karşılaştırma sayısı en az küçük yarının boyu, en fazla $n_1 + n_2 - 1$:

merge [1, 2, 3, 4] + [5, 6, 7, 8] -> [1, 2, 3, 4, 5, 6, 7, 8]
comps=4
merge [1, 3, 5, 7] + [2, 4, 6, 8] -> [1, 2, 3, 4, 5, 6, 7, 8]
comps=7

Quick sort

Fikir: bir pivot seç. Diziyi, pivottan küçükler solda ve büyükler sağda olacak şekilde yeniden düzenle (partition). Pivot artık nihai yerindedir. Sol ve sağ tarafı özyinelemeyle sırala. Birleştirme adımı yok; her şey yerinde olur.

Lomuto partition (pivot = son eleman)

static int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;                 // küçükler bölgesinin sonu
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;   // pivotu yerine koy
    return i + 1;
}

static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

{7, 2, 9, 4, 3, 8, 5} üzerinde ilk partition, adım adım:

pivot=5 start [7, 2, 9, 4, 3, 8, 5]
j=0 a[j]>=pivot, skip     [7, 2, 9, 4, 3, 8, 5]
j=1 a[j]<pivot, i=0 swap -> [2, 7, 9, 4, 3, 8, 5]
j=2 a[j]>=pivot, skip     [2, 7, 9, 4, 3, 8, 5]
j=3 a[j]<pivot, i=1 swap -> [2, 4, 9, 7, 3, 8, 5]
j=4 a[j]<pivot, i=2 swap -> [2, 4, 3, 7, 9, 8, 5]
j=5 a[j]>=pivot, skip     [2, 4, 3, 7, 9, 8, 5]
place pivot at 3 -> [2, 4, 3, 5, 9, 8, 7]

Döngü boyunca dizi dört bölgeye ayrılır:

[ lo .. i ]     < pivot
[ i+1 .. j-1 ]  >= pivot
[ j .. hi-1 ]   henüz bakılmadı
[ hi ]          pivot

Bütün sıralama:

partition [0..6] pivot 5 at 3 -> [2, 4, 3, 5, 9, 8, 7]
partition [0..2] pivot 3 at 1 -> [2, 3, 4, 5, 9, 8, 7]
partition [4..6] pivot 7 at 4 -> [2, 3, 4, 5, 7, 8, 9]
partition [5..6] pivot 9 at 6 -> [2, 3, 4, 5, 7, 8, 9]
[2, 3, 4, 5, 7, 8, 9] comps=11

İPUCU · Başka partition şemaları. Ders kitabı ve bazı hocalar ilk elemanı ya da üç elemanın medyanını (median-of-three) pivot alır ve iki uçtan içeri yürüyen Hoare tarzı bir partition kullanır. Ara durumlar farklı çıkar ama değişmeyen kural aynı: partition sonunda pivot yerinde, solu küçük, sağı büyük. Sınavda hangi şemanın istendiğini oku.

En kötü durum

Pivot her seferinde en büyük (ya da en küçük) elemansa bölme “n − 1 ve 0” olur. Son eleman pivot alınan quick sort’a sıralı bir dizi vermek tam bunu yapar:

partition [0..5] pivot 6 at 5 -> [1, 2, 3, 4, 5, 6]
partition [0..4] pivot 5 at 4 -> [1, 2, 3, 4, 5, 6]
partition [0..3] pivot 4 at 3 -> [1, 2, 3, 4, 5, 6]
partition [0..2] pivot 3 at 2 -> [1, 2, 3, 4, 5, 6]
partition [0..1] pivot 2 at 1 -> [1, 2, 3, 4, 5, 6]
comps=15

$T(n) = T(n-1) + n$ → O(n²). n = 1000, 2000, 4000 için 499 500, 1 999 000, 7 998 000 karşılaştırma: tam n(n−1)/2. Çözüm: pivotu rastgele seç ya da ilk, orta ve son elemanın medyanını al. Ortalama durumda bölmeler dengeli olur ve O(n log n) elde edilir.

Heap sort (genel bakış)

Max-heap: her düğümün kendi çocuklarından büyük ya da eşit olduğu, dizide saklanan tam ikili ağaç. Dizide indeks i’nin çocukları 2i + 1 ve 2i + 2, ebeveyni (i − 1) / 2. En büyük eleman her zaman kökte (indeks 0).

Heap sort iki aşamalıdır:

1. Heap kur. Son iç düğümden (indeks n/2 − 1) başlayıp köke doğru her düğümü aşağı süz (sift down): düğüm büyük çocuğundan küçükse takas et, devam et. Toplam O(n).
2. Çıkar. Kökü (en büyük) dizinin sonuyla takas et, heap’i bir küçült, yeni kökü aşağı süz. n − 1 kez tekrarla. Her süzme O(log n).

static void siftDown(int[] a, int i, int n) {
    while (2 * i + 1 < n) {
        int c = 2 * i + 1;                         // sol çocuk
        if (c + 1 < n && a[c + 1] > a[c]) c++;     // büyük çocuk
        if (a[i] >= a[c]) break;
        int t = a[i]; a[i] = a[c]; a[c] = t;
        i = c;
    }
}

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;
        siftDown(a, 0, end);
    }
}

{4, 10, 3, 5, 1}:

max-heap: [10, 5, 3, 4, 1]
extract 10 -> [5, 4, 3, 1, 10]
extract 5 -> [4, 1, 3, 5, 10]
extract 4 -> [3, 1, 4, 5, 10]
extract 3 -> [1, 3, 4, 5, 10]

Her zaman O(n log n), O(1) ek bellek. Ama kararsız ve önbellek dostu olmadığı için pratikte quick sort’tan yavaştır. Heap yapısının ayrıntısı SEN2212’de.

Ölçüm: n log n

Rastgele dizilerde karşılaştırma sayısı:

n=10000 merge comps=120464 quick comps=154970  n*log2(n)=132877
n=20000 merge comps=260792 quick comps=342401  n*log2(n)=285754
n=40000 merge comps=561703 quick comps=701837  n*log2(n)=611508
n=80000 merge comps=1203361 quick comps=1545944  n*log2(n)=1303017

İkisi de n log₂ n ile aynı büyüklükte ve n iki katına çıkınca yaklaşık 2.1-2.2 katına çıkıyor (karesel olsaydı 4). Quick sort daha çok karşılaştırma yapmasına rağmen pratikte genellikle daha hızlıdır: yardımcı dizi yok, kopyalama yok.

Bütün sıralamalar: karşılaştırma tablosu

Kararlılık testi: anahtarları (2a, 2b, 1) olan kayıtlara tek bir Lomuto partition uygulanınca

after one Lomuto partition: [1, 2b, 2a]

Pivot 1 başa takas edilirken 2a sona fırladı. Merge sort aynı girdide 1 2a 2b verir.

Sık yapılan hatalar

merge [38] + [27] -> [27, 38]
merge [43] + [3] -> [3, 43]
merge [27, 38] + [3, 43] -> [3, 27, 38, 43]
merge [9] + [82] -> [9, 82]
merge [9, 82] + [10] -> [9, 10, 82]
merge [3, 27, 38, 43] + [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]

j=0  7 >= 5 atla       [7, 2, 9, 4, 3, 8, 5]
j=1  2 < 5, i=0 takas  [2, 7, 9, 4, 3, 8, 5]
j=2  9 atla
j=3  4 < 5, i=1 takas  [2, 4, 9, 7, 3, 8, 5]
j=4  3 < 5, i=2 takas  [2, 4, 3, 7, 9, 8, 5]
j=5  8 atla
pivot'u i+1 = 3'e koy  [2, 4, 3, 5, 9, 8, 7]

partition [0..6] pivot 5 at 3 -> [2, 4, 3, 5, 9, 8, 7]
partition [0..2] pivot 3 at 1 -> [2, 3, 4, 5, 9, 8, 7]
partition [4..6] pivot 7 at 4 -> [2, 3, 4, 5, 7, 8, 9]
partition [5..6] pivot 9 at 6 -> [2, 3, 4, 5, 7, 8, 9]

static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];   // <= kararlılık için
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];          // kalan sol
    while (j <= hi)  tmp[k++] = a[j++];          // kalan sağ
    for (k = lo; k <= hi; k++) a[k] = tmp[k];    // geri kopyala
}

static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    mergeSort(a, tmp, lo, mid);
    mergeSort(a, tmp, mid + 1, hi);
    merge(a, tmp, lo, mid, hi);
}

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

static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);    // pivot HARİÇ
    quickSort(a, p + 1, hi);
}