Bölüm 20: İleri Sıralama Algoritmaları

20.1Sıralamayı hızlandırmak: parçala ve yönet

20.1.1Temel sıralamaların sınırı

Seçimli sıralama her turda kalan öğelerin en küçüğünü bulur ve onu yerine koyar. Kabarcık sıralaması komşu öğeleri karşılaştırarak en büyüğü sona taşır. İkisi de her turda tek bir öğeyi kesin yerine yerleştirir. Ne var ki bir sonraki tur yine n − 1 öğelik bir problemle başlar. Problem her turda yalnız bir öğe küçülür ve toplam iş n + (n − 1) + … + 1, yani n² mertebesinde olur. Eklemeli sıralama neredeyse sıralı veride doğrusal sürer, ama genel girdide o da n²'ye çıkar.

Bu sınırı aşmak için öğeleri yerleştirmek yetmez; problemi her adımda hızla küçültmek gerekir. Karşılaştırmaya dayanan her sıralama algoritması için bilinen bir alt sınır da vardır. n öğenin n! dizilişinden doğrusunu bulmak için en kötü durumda en az ⌈lg n!⌉ ≈ n lg n − 1,44 n karşılaştırma gerekir. Burada lg, 2 tabanlı logaritmadır. Bu notun algoritmaları bu alt sınıra katsayısı küçük bir çarpanla yaklaşır.

20.1.2Parçala ve yönet

Hızlı sıralama ve birleştirme sıralaması bu yöntemin iki farklı yorumudur. Hızlı sıralama işin ağır kısmını bölerken yapar: diziyi öyle iki parçaya ayırır ki soldakilerin hepsi sağdakilerden küçük ya da onlara eşit olur. Bu durumda birleştirmeye gerek kalmaz; iki parça ayrı ayrı sıralanınca bütün dizi sıralanmış olur. Birleştirme sıralaması ise tam tersini yapar. Diziyi düşünmeden ortadan ikiye böler, işin ağır kısmını iki sıralı yarıyı birleştirirken yapar.

Her iki algoritmanın da maliyeti bir yineleme bağıntısı (recurrence relation) ile yazılır. n öğeli problemin maliyeti, daha küçük problemlerin maliyetleri ve bölme ya da birleştirme işinin maliyeti cinsinden ifade edilir. Örneğin her adımda iki yarıya bölen ve bölme işi n süren bir algoritmanın maliyeti C_n = 2C_n/2 + n bağıntısına uyar.

Notta sıralanan diziler hep int dizisidir. Karşılaştırma ve takas için temel sıralamalarda kullanılan iki makro aynen korunur:

#define kucuk(A, B) ((A) < (B))
#define SWAP(A, B) do { int t_ = (A); (A) = (B); (B) = t_; } while (0)

kucuk(A, B), A < B ise doğrudur. Karşılaştırmayı tek bir yerde toplamak, sayaç eklemeyi ya da öğe türünü değiştirmeyi kolaylaştırır. Bu notun ölçümlerinde karşılaştırmalar bu makroya bir sayaç eklenerek sayılmıştır. SWAP iki argümanlıdır ve geçici değişkeni kendi içinde tanımlar. Gövdenin do { … } while (0) içine alınması, makronun if (…) SWAP(x, y); else … gibi bir yerde tek bir deyim gibi davranmasını sağlar. Gövde yalnız süslü ayraçla yazılsaydı, sondaki noktalı virgül else'i boşa düşürür ve derleme hatası verirdi.

20.2Hızlı sıralama

Hızlı sıralama (quick sort), C. A. R. (Tony) Hoare'un 1962'de yayımladığı algoritmadır. Türkçede “çabuk sıralama” adıyla da anılır. Ortalama durumda n lg n ile orantılı sürer; en kötü durumda n²'ye çıkar. Yardımcı olarak yalnız küçük bir yığın kullanır. Kararlı (stable) değildir, yani eşit anahtarlı öğelerin girişteki göreli sırasını korumaz. Bu kusuruna karşın bilinen en hızlı genel amaçlı sıralama algoritmalarından biridir. Standart C kitaplığındaki qsort adı da bu algoritmadan gelir.

Aşağıdaki kod R. Sedgewick'in Algorithms in C kitabından alınmıştır. Sedgewick, Donald Knuth'un doktora öğrencisidir ve hızlı sıralama üzerine kapsamlı çalışmalar yapmıştır. Kod kısa ve dikkatle yazılmıştır; her satırın bir görevi vardır.

20.2.1quicksort1

int bol(int a[], int L, int R);

void quicksort1(int a[], int L, int R) {
    if (R <= L) return;
    int i = bol(a, L, R);
    quicksort1(a, L, i - 1);
    quicksort1(a, i + 1, R);
}

Yordam a[L..R] aralığını sıralar. Bütün diziyi sıralamak için quicksort1(a, 0, n - 1) çağrılır. İlk satırdaki prototip, bol'un tanımı daha aşağıda olsa bile derleyicinin çağrıyı denetleyebilmesi içindir.

• if (R <= L) return; özyinelemenin taban durumudur. R < L ise aralık boştur, R = L ise tek öğe vardır. İki durumda da yapılacak iş yoktur.
• int i = bol(a, L, R); aralığı bölümler. bol bir öğeyi, pivotu (pivot), sıralı dizide duracağı konuma koyar ve bu konumu döndürür. Dönüşte a[L..i-1]'deki her öğe pivottan küçük ya da ona eşit, a[i+1..R]'deki her öğe pivottan büyük ya da ona eşittir.
• İki özyinelemeli çağrı pivotun solunu ve sağını ayrı ayrı sıralar. Pivot yerindedir; bir daha hiçbir çağrı ona dokunmaz.

Yordamın doğruluğu bu üç satırdan kolayca çıkar. Sol parça sıralandığında, her öğesi pivottan büyük olmadığı için hepsi pivotun solunda doğru sırada durur. Sağ parça için de aynı şey geçerlidir. Bütün iş bol'dadır.

20.2.2Bölümleme: bol()

int bol(int a[], int L, int R) {
    int i = L - 1, j = R, v = a[R]; // pivot a[R]
    for (;;) {
        while (kucuk(a[++i], v))
            ;
        while (kucuk(v, a[--j]))
            if (j == L) break;
        if (i >= j) break;
        SWAP(a[i], a[j]);
    }
    SWAP(a[i], a[R]);
    return i;
}

bol pivot olarak en sağdaki öğeyi, v = a[R]'yi seçer. İki indis kullanır: i soldan sağa, j sağdan sola tarar. Satır satır:

• Satır 2. i = L - 1 ve j = R ile başlanır. Taramalar ++i ve --j ile önce ilerleyip sonra baktığı için ilk bakılan öğeler a[L] ve a[R-1]'dir. Pivotun kendisi taramaya girmez.
• Satır 4–5. i, v'den büyük ya da ona eşit ilk öğede durur. Bu döngüde sınır denetimi yoktur ve gerek de yoktur. En kötü durumda i, R'ye ulaşır ve a[R] = v, kucuk(v, v) yanlış olduğu için taramayı durdurur. Pivot burada doğal bir bekçi (sentinel) görevi görür.
• Satır 6–7. j, v'den küçük ya da ona eşit ilk öğede durur. Bu taramanın solunda bekçi yoktur: pivot aralığın en küçük öğesiyse j dizinin başından taşabilirdi. if (j == L) break; satırı bunu önler.
• Satır 8. i >= j ise indisler buluşmuş ya da çaprazlanmıştır. Bütün öğeler taranmıştır ve döngü biter.
• Satır 9. Aksi hâlde a[i] sağ tarafa, a[j] sol tarafa aittir; ikisi de yanlış taraftadır. Takas edilince ikisi de doğru tarafa geçer ve taramalar kaldıkları yerden sürer.
• Satır 11–12. Döngüden çıkıldığında a[i], sağ tarafın ilk öğesidir. Pivot onunla takas edilir ve i döndürülür.

Bölümleme değişmezi şekildeki dört bölgeyle anlatılır. Döngünün her adımında a[L..i]'nin solundaki öğeler v'den büyük değildir, a[j..R-1]'in sağındakiler v'den küçük değildir. Arada henüz taranmamış bir bölge kalır. Her takas taranmamış bölgeyi iki öğe daraltır. İndisler çaprazlandığında bu bölge boşalır.

Eşit anahtarlarda iki taramanın da durması bilinçli bir tercihtir. Bütün öğeleri eşit bir dizi düşünelim. Taramalar eşitte durmasaydı i hep sona kadar giderdi. Bölme hep n − 1 ve 0 öğelik parçalar üretir, süre n²'ye çıkardı. Eşitte durulunca gereksiz görünen takaslar yapılır, ama indisler ortada buluşur.

bol'un maliyeti n = R − L + 1 öğeli aralık için Θ(n)'dir. i yalnız sağa, j yalnız sola gider. İkisi buluşana kadar her öğeye bir kez bakılır; çaprazlanmada en çok birkaç öğeye ikinci kez bakılır. Karşılaştırma sayısı n ya da n + 1'dir. Ek bellek birkaç değişkendir: O(1).

20.2.3Kod izleme: bol(a, 0, 9)

Dizi [37, 15, 24, 33, 49, 11, 51, 77, 72, 48] olsun. Pivot v = a[9] = 48'dir. Tablo her adımda indislerin nerede durduğunu ve dizinin hâlini verir; şekil önemli dört anı gösterir.

Son durumda 48'in solunda 37, 15, 24, 33, 11 vardır ve hepsi 48'den küçüktür. Sağında 51, 77, 72, 49 vardır ve hepsi büyüktür. İki tarafın kendi içinde sıralı olmadığına dikkat edilmelidir. Bölümleme yalnız pivotun yerini kesinleştirir: veriler sıralansaydı 48 tam 5. konumda olurdu. Bu izlemede n + 1 = 11 karşılaştırma yapılmıştır: i taraması 6, j taraması 5 kez bakmıştır. 4 ve 5. konumlara iki tarama da bakmıştır; fazladan karşılaştırma çaprazlanmadan gelir.

20.2.4Kod izleme: quicksort1(a, 0, 9)

Aynı dizi bu kez quicksort1 ile baştan sona sıralansın. Tablo her bol çağrısını, döndürdüğü konumu ve sonraki dizi durumunu verir. Özyineleme önce sol parçayı tamamen bitirir, sonra sağ parçaya geçer. Bu yüzden çağrı yığını sol parçalarda derinleşir.

bol(0, 4)'te pivot 11, aralığın en küçüğüdür. i hemen a[0] = 37'de durur. j ise sola doğru 33, 24, 15'i geçer ve j == L denetimiyle 0'da durur. Çaprazlanma olur, pivot 0. konuma gelir ve 37 sona geçer. Sol parça boştur. Bu, j döngüsündeki sınır denetiminin iş başında görüldüğü andır.

Toplam 17 quicksort1 çağrısı yapılır. Sekizi bol çağırır ve her biri bir pivotu kesin yerine koyar. Kalan dokuzu boş ya da tek öğeli aralıkla çağrılır ve hemen döner: (0, −1), (1, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6), (8, 8), (10, 9). Her bol çağrısı iki alt çağrı ürettiği için yaprak sayısı iç düğüm sayısından bir fazladır: 8 + 9 = 17. En derin anda yığında main'in üstünde altı quicksort1 çerçevesi vardır: (0, 9), (0, 4), (1, 4), (1, 3), (1, 2) ve (1, 1).

20.2.5Neden hızlı?

Kabarcık ya da seçimli sıralamada da her adımda bir öğe için doğru konum bulunur. Fark şuradadır: onlar bir öğeyi yerine koyar ama problemi küçültmeye katkı yapamaz. Sonraki adımın alt problemi n − 1 öğeliktir. Hızlı sıralama pivotu yerine koyarken problemi de iki küçük parçaya ayırır. İyi bir bölmede iki parçanın her biri yaklaşık n/2 öğelidir. Bir sonraki düzeyde dört parça n/4 öğelidir, ve böyle sürer. lg n düzeyden sonra parçalar tek öğeye iner. Her düzeyde bölümleme işinin toplamı n civarındadır; bu yüzden toplam iş n lg n mertebesindedir.

Bu nottaki hızlı sıralama sürümlerinin hepsi aynı bol'u kullanır. Bu kadar kısa kodlar bir kez okumakla kavranmaz; farklı dizilerle birkaç kez izlenmeli ve mantığından yeniden yazılmalıdır.

20.2.6Algoritma ve bilgisayar

Öğrencilerin sık sorduğu bir soru şudur: Hoare bu algoritmayı 1960'larda nerede denedi, nasıl test etti? “Algoritma” kelimesi nereden geliyor; 8. yüzyılda el-Harezmî'nin dizüstü bilgisayarı mı vardı?

Cevap algoritma kavramının kendisindedir. Algoritma, konuyu hiç bilmeyen birinin adım adım işleteceği ve doğru sonuca ulaşacağı kesin bir yöntemdir; tanımında bilgisayar geçmez. 1960'larda bilgisayarlar zaten vardı, ama bir algoritmanın doğruluğu ve maliyeti kâğıt üzerinde kanıtlanır; makalesinin yayımlanması yeterlidir. Bu ders de bu yüzden bilgisayardan bağımsızdır.

Kelimenin kökü de bunu doğrular. El-Harezmî (780–850), Bağdat'taki Beytü'l-Hikme'de çalışmış bir matematikçi ve gökbilimcidir. Birinci ve ikinci dereceden denklemlerin sistematik çözümünü veren el-Kitâbü'l-Muhtasar fî Hisâbi'l-Cebr ve'l-Mukâbele kitabını yazmıştır. “Cebir” ve Batı dillerindeki “algebra” bu kitaptaki el-cebr yönteminin adından gelir. “Algoritma” ise el-Harezmî'nin adının Latince biçimi Algoritmi'den türemiştir. El-Harezmî onluk konumsal sayı sistemini Batı'ya tanıtan eserleriyle de bilinir.

20.3Hızlı sıralamanın analizi

Hızlı sıralamanın süresini belirleyen tek şey, bol'un aralığı nasıl böldüğüdür. Her bol çağrısı kendi aralığının boyu kadar iş yapar. Bölmeler dengeliyse özyineleme ağacı sığ kalır, dengesizse ağaç bir zincire döner. Bu kesimde maliyet karşılaştırma sayısıyla ölçülür, çünkü sıralamanın asıl işi karşılaştırmadır ve takas sayısı onunla orantılıdır. C_n, n öğeli bir diziyi sıralarken yapılan karşılaştırma sayısını gösterir.

20.3.1En kötü durum: sıralı dizi

Dizi zaten sıralı olsun. Pivot a[R] her seferinde aralığın en büyük öğesidir. i taraması bütün aralığı geçip R'de durur; j ilk baktığı öğede durur. Pivot yerinde kalır ve sol parça n − 1 öğeli, sağ parça boştur. Sonraki çağrı yine en büyük öğeyi pivot alır ve yine bir eksik boyla devam eder. Toplam iş

n + (n − 1) + … + 2 + 1 = n(n + 1)/2 = O(n²)

olur. Kesin sayı da hesaplanabilir. Boyu s olan aralıkta bol tam s + 1 karşılaştırma yapar: i taraması s, j taraması 1. Boyları n, n − 1, …, 2 olan n − 1 aralık bölümlenir. n = 10 için toplam 11 + 10 + … + 3 = 63 karşılaştırmadır.

Ayrıca özyineleme derinliği n − 1'e çıkar; büyük sıralı diziler, yığın boyu küçük sistemlerde yığın taşmasına (stack overflow) yol açabilir. 100 000 öğelik sıralı dizi -O2 ile 0,95 saniye, aynı boyda rastgele dizi 0,008 saniye sürmüştür (süreler makineye göre değişir). Ters sıralı dizi de aynı ölçüde kötüdür.

20.3.2En iyi durum: tam ortadan bölme

En iyi durumda pivot her seferinde aralığın tam ortancasıdır. i ve j toplam n adım ilerler ve geriye n/2'şer öğeli iki alt problem kalır:

C_n = 2C_n/2 + n, C₁ = 0

Bağıntı kendi içine yerleştirilerek açılır. C_n/2 = 2C_n/4 + n/2 olduğundan C_n = 2(2C_n/4 + n/2) + n = 4C_n/4 + 2n bulunur. Bir adım daha açılınca 8C_n/8 + 3n elde edilir. k adımdan sonra

C_n = 2^k C_n/2^k + k · n

olur. n = 2^k, yani k = lg n alınırsa C_n/2^k = C₁ = 0 olur ve C_n = n lg n bulunur.

Karşılaştırmalı sıralamanın alt sınırı ⌈lg n!⌉ ≈ n lg n − 1,44 n idi. Baş terimin katsayısı yine 1'dir; aradaki fark yalnız 1,44 n kadardır. Asıl soru rastgele bir dizideki davranıştır: “Bunun neresi hızlı?” sorusunun cevabı ortalama durumdadır.

20.3.3Sayım: sıralı ve rastgele girdi

İki uç durum arasındaki farkı somutlaştırmak için bol'daki karşılaştırmalar sayılmıştır. Tablo sıralı ve rastgele girdide karşılaştırma sayısını ve özyineleme derinliğini verir. Derinlik, iç içe bekleyen ve bol çağıran quicksort1 çerçevelerinin en büyük sayısıdır.

Sıralı girdide karşılaştırma sayısı (n + 1)(n + 2)/2 − 3, yani yaklaşık n²/2'dir; derinlik n − 1'dir. n = 1000'de yarım milyon karşılaştırma yapılır. Rastgele girdide sayı n lg n mertebesinde kalır ve derinlik yalnız birkaç lg n kadardır. Aynı boydaki iki girdide iş kırk kat farklıdır. Sıralı ya da neredeyse sıralı veri gerçek hayatta seyrek değildir.

20.3.4Ortalama durum: bağıntının kurulması

Ortalama durum analizi sezgiye değil matematiğe dayanır. Bir para bir milyon kez atılınca tura oranı ½'ye yaklaşır; sonuçların nerede yoğunlaştığını ortalama durum analizi böyle saptar. “Bana göre olasılıklar eşittir” demek yetmez; eşitlik kanıtlanmalıdır.

Girdinin n! dizilişinin hepsi eşit olasılıklı olsun ve anahtarlar birbirinden farklı olsun. Pivot a[R]'dir. Rastgele bir dizilişte en sağdaki öğenin sıralı dizideki sırası 1, 2, …, n değerlerinden her birini eşit olasılıkla, 1/n olasılıkla alır. Pivotun sırası k ise bol onu k. konuma koyar; geriye k − 1 ve n − k öğeli iki alt dizi kalır. Bir şey daha gerekir: alt diziler de rastgele olmalıdır. bol öğeleri yalnız pivotla karşılaştırır, birbirleriyle karşılaştırmaz. Bu yüzden her parçanın kendi içindeki dizilişleri yine eşit olasılıklıdır. Parçalar da aynı analize uyar.

bol pivotla n + 1 karşılaştırma yapar. Bu sayıyı model olarak alırsak ortalama karşılaştırma sayısı şu bağıntıya uyar:

C_n = (n + 1) + (1/n) Σ_k=1ⁿ (C_k−1 + C_n−k), C₀ = C₁ = 0

İlk terim bölümleme işidir. Toplam, k'nın her değeri için iki alt problemin maliyetidir; 1/n çarpanı bu değerlerin eşit olasılıklı olmasından gelir. İki toplam aynı terimleri içerir. k = 1, …, n için C_k−1 terimleri C₀, C₁, …, C_n−1'dir. C_n−k terimleri de aynı değerlerdir, yalnız ters sırada gelir. Öyleyse

Σ_k=1ⁿ (C_k−1 + C_n−k) = 2 Σ_k=1ⁿ C_k−1

yazılabilir. Bağıntının iki yanı n ile çarpılınca kesirden kurtulunur:

n · C_n = n(n + 1) + 2 Σ_k=1ⁿ C_k−1 (1)

Gerçek bol, karşılaştırmalı bir taramada n ya da n + 1 karşılaştırma yapar; indisler aynı konumda buluşursa bir eksik sayar. 20 000 rastgele dizide yapılan denemede çağrıların yaklaşık %90'ı n + 1, kalanı n karşılaştırma yapmıştır. Bu yüzden ölçülen ortalamalar C_n'den biraz küçük çıkar (tablonun son sütunu). Bağıntı küçük bir üst modeldir; asimptotik sonucu değişmez.

20.3.5Çıkarma hilesi ve çözüm

(1) bağıntısındaki toplam her n için bütün önceki değerleri içerir. Bu tür bağıntılar genellikle yerine koyma yöntemiyle çözülür. Horowitz'in kitabı da böyle yapar. Daha kısa bir yol vardır: toplamı ortadan kaldırmak. (1)'de n yerine n − 1 yazılır:

(n − 1) · C_n−1 = (n − 1)n + 2 Σ_k=1ⁿ⁻¹ C_k−1 (2)

(1)'den (2) çıkarılınca iki toplamın ortak terimleri gider; yalnız 2C_n−1 kalır. Sağdaki ilk terimlerin farkı n(n + 1) − n(n − 1) = 2n'dir:

n · C_n − (n − 1) · C_n−1 = 2n + 2C_n−1 ⇒ n · C_n = (n + 1) · C_n−1 + 2n

Artık bağıntı yalnız bir önceki terime bağlıdır. İki yan n(n + 1)'e bölünür:

C_n/(n + 1) = C_n−1/n + 2/(n + 1)

Bu biçimin güzelliği, sol yanla sağdaki ilk terimin aynı kalıpta olmasıdır. D_n = C_n/(n + 1) denirse D_n = D_n−1 + 2/(n + 1) olur. Bu, iterasyonla hemen açılır: D_n = D_n−1 + 2/(n + 1) = D_n−2 + 2/n + 2/(n + 1) = …. Çıkarma adımı (2)'nin n − 1 ≥ 2 için geçerli olmasını ister. Bu yüzden açılım C₂ = 3'te durdurulur; D₂ = 1'dir:

C_n/(n + 1) = 1 + 2(1/4 + 1/5 + … + 1/(n + 1)) (n ≥ 2)

Parantezdeki toplam, harmonik sayı H_n+1 = 1 + 1/2 + … + 1/(n + 1)'den ilk üç terimin çıkarılmış hâlidir. Baskın kısım 2(n + 1)(1/3 + 1/4 + … + 1/(n + 1))'dir ve bu da 2(n + 1) ln n'den küçüktür. H_n ≈ ln n + 0,577 olduğundan

C_n ≈ 2n ln n = 2 ln 2 · n lg n ≈ 1,39 n lg n

bulunur. Son adımda ln n = ln 2 · lg n eşitliği kullanılmıştır; 2 ln 2 ≈ 1,386'dır.

Bağıntı Python ile tam olarak hesaplanıp formülle karşılaştırılmıştır. Tablo sonucu üç boy için verir. Oranın 1'e çok yavaş yaklaştığı görülür. Bunun nedeni, kapalı biçimdeki −cn biçimindeki alt dereceli terimlerdir. Bu terimler n lg n'nin yanında yavaş yavaş önemini yitirir.

Rastgele bir girdide hızlı sıralama en iyi durumundan yalnız %39 kadar fazla karşılaştırma yapar; n² durumunun olasılığı çok küçüktür. İç döngüsü de çok kısadır: bir artırma, bir karşılaştırma ve bir dallanma; öğeler bellekte sırayla okunur.

20.4Hızlı sıralamayı iyileştirmek

quicksort1'in iki zayıf yanı vardır. Birincisi, özyineleme derinliği en kötü durumda n'ye çıkar ve yığını tüketebilir. İkincisi, sıralı ya da ters sıralı girdi onu n²'ye sürükler. Ayrıca küçük parçalarda özyinelemenin maliyeti, yapılan asıl işten fazladır. Bu kesim üç iyileştirmeyi sırayla inceler: açık yığınla özyinelemesiz sürüm, pivotun üç öğenin ortancasından seçilmesi ve küçük parçaların eklemeli sıralamaya bırakılması.

20.4.1Özyinelemesiz sürüm ve açık yığın

Özyinelemeli bir yordam bekleyen işlerini çağrı yığınında tutar; her çağrı parametreleri, yerel değişkenleri ve dönüş adresini taşıyan bir çerçeve (stack frame) açar. quicksort1'in bekleyen her işi bir (L, R) ikilisidir. Bu ikililer diziyle gerçeklenen bir yığına konursa özyineleme gerekmez; çağrı maliyeti kalkar ve hangi işin önce yapılacağı denetim altına girer.

#define YMAX 64     /* > 2·lg n */
static int yigit[YMAX], ust;
void yigit_baslat(void) { ust = 0; }
int yigit_bosmu(void) { return ust == 0; }
void yigit_ekle(int x) { yigit[ust++] = x; }
int yigit_al(void) { return yigit[--ust]; }
#define yigita_at(A, B) \
  do { yigit_ekle(B); yigit_ekle(A); } while (0)

Yığın, boyu YMAX olan static bir int dizisidir. ust, dizide ilk boş hücrenin indisidir; ust == 0 yığının boş olduğunu gösterir. static anahtar sözcüğü, dizinin ve ust'ün yalnız bu kaynak dosyasından görülmesini sağlar ve ikisini program boyunca yaşatır. yigit_ekle değeri yigit[ust]'e yazar ve ust'ü artırır. yigit_al önce ust'ü azaltır, sonra o hücreyi döndürür. İki işlem de O(1)'dir.

yigita_at(A, B) makrosu bir ikiliyi iter. Önce B'yi, sonra A'yı iter. Yığından ilk alınan son itilen olduğu için ilk alınan A olur. quicksort2'de yigita_at(L, R) yazıldığında alma sırası L, ardından R'dir. Makronun gövdesi yine do { … } while (0) içindedir; böylece if–else dallarında tek deyim gibi kullanılabilir. Satır sonundaki ters bölü (\), makro tanımının alt satırda sürdüğünü önişlemciye bildirir.

Yığın taşma denetimi yapmaz; boyu hiçbir girdinin aşamayacağı biçimde seçilmiştir. Teorem 20.2'ye göre yığında en çok ⌊lg n⌋ + 1 ikili, yani 2(⌊lg n⌋ + 1) int bulunur. n < 2³¹ için bu 62'yi aşmaz.

void quicksort2(int a[], int L, int R) {
  yigit_baslat(); yigita_at(L, R);
  while (!yigit_bosmu()) {
    L = yigit_al(); R = yigit_al();
    if (R <= L) continue;
    int i = bol(a, L, R);
    if (i - L > R - i) {       // büyük parça önce
      yigita_at(L, i - 1); yigita_at(i + 1, R);
    } else {
      yigita_at(i + 1, R); yigita_at(L, i - 1);
    }
  }
}

• Satır 2. Yığın boşaltılır ve ilk problem, bütün aralık itilir.
• Satır 3–5. Yığın boşalana kadar bir ikili alınır. Aralık boş ya da tek öğeliyse continue ile sıradaki ikiliye geçilir. Bu satırlar quicksort1'in taban durumunun karşılığıdır.
• Satır 6. Aralık bölümlenir. Sol parça a[L..i-1], sağ parça a[i+1..R]'dir; boyları i − L ve R − i'dir.
• Satır 7–11. Büyük parça önce, küçük parça sonra itilir. Yığın son gireni ilk çıkardığı için bir sonraki turda hep küçük parça işlenir. Boylar eşitse else dalı çalışır ve sol parça üstte kalır.

20.4.2Kod izleme: quicksort2(a, 0, 6)

Dizi [4, 7, 2, 6, 1, 5, 3] olsun. Tablo, yığının her turdaki içeriğini alttan üste doğru verir. Yığında ikililer R, L sırasıyla durur; üstteki iki sayı sıradaki işin L ve R'sidir.

Yığında en çok 3 ikili, yani 6 int beklemiştir. Tek öğeli ve boş aralıklar da itilip alındıktan sonra atılır; bunları önceden denetlemek birkaç işlem kurtarır ama kodu uzatır.

20.4.3Yığın neden küçük kalır?

Aynı sonuç bellek bağıntısından da çıkar: küçük parça en çok yarı boydadır ve her düzey yığına iki int ekler; T_n = T_n/2 + 2, ikili aramadaki gibi T_n = 2 lg n verir. Tablo sınırı ölçümle karşılaştırır. Sıralı girdide yığın neredeyse boş kalır, çünkü küçük parça boştur.

Sıralı girdide yığın küçük kalsa da süre yine n²'dir; quicksort2 100 000 sıralı öğeyi 0,94 saniyede sıralamıştır. Özyinelemesiz sürüm bellek sorununu çözer, süre sorununu çözmez. Süre sorunu pivot seçimiyle çözülür.

20.4.4Üçün ortancası ve küçük parça eşiği

Hızlı sıralama en kötü performansını sıralı veride gösterir. Eklemeli sıralama ise en iyi performansını tam da sıralı veride gösterir. Geliştirilmiş sürüm bu iki gözlemi birleştirir:

#define M 10    /* bu boydan küçük parça kalsın */
void quicksort3(int a[], int L, int R) {
    if (R - L <= M) return;
    SWAP(a[(L + R) / 2], a[R - 1]);
    if (a[R-1] < a[L]) SWAP(a[R-1], a[L]); // a[L] <= a[R-1]
    if (a[R] < a[L]) SWAP(a[R], a[L]);     // a[L] <= a[R]
    if (a[R] < a[R-1]) SWAP(a[R], a[R-1]); // a[R-1] <= a[R]
    int i = bol(a, L + 1, R - 1);
    quicksort3(a, L, i - 1);
    quicksort3(a, i + 1, R);
}
void sirala(int a[], int L, int R) {
    quicksort3(a, L, R);
    insertion(a, L, R);   /* kalan küçük parçalar */
}

Üçün ortancası (median-of-three), kısaca medyan-3, pivotu tek bir öğe yerine üç öğenin ortancası olarak seçer. Bu üç öğe aralığın ilk öğesi, ortadaki öğe ve son öğedir. Satır satır:

• Satır 3. Aralık en çok M + 1 öğeliyse (R − L ≤ M) yordam hiçbir şey yapmadan döner. Bu parçalar sıralanmadan bırakılır.
• Satır 4. Ortadaki öğe a[R-1]'e taşınır. Artık üç aday a[L], a[R-1] ve a[R]'dedir.
• Satır 5–7. Üç “karşılaştır, gerekirse takas et” adımı bu üç öğeyi sıraya koyar. Sonunda a[L] ≤ a[R−1] ≤ a[R] olur ve ortanca a[R-1]'dedir.
• Satır 8. Bölümleme yalnız a[L+1..R-1] üzerinde yapılır. bol bu aralığın son öğesini, yani ortancayı pivot alır.
• Satır 9–10. Pivotun iki yanı özyinelemeli olarak işlenir.

Üç takas satırında argümanların sırası önemlidir. if (kucuk(A, B)) SWAP(A, B) kalıbı “A < B ise takas et” demektir. Takastan sonra B'deki öğe ikisinin küçüğüdür, A'daki büyüğüdür. Koddaki ilk satır if (a[R-1] < a[L]) SWAP(a[R-1], a[L]); biçimindedir ve küçüğü a[L]'ye koyar. Argümanlar (a[L], a[R-1]) sırasıyla verilseydi büyük öğe a[L]'ye giderdi ve bölümleme bozulurdu. Bu yanlış sürüm 1000 rastgele diziyle denenmiş, dizilerin hepsinde en az bir bölümlemede pivotun solunda ondan büyük bir öğe kalmıştır.

Medyan-3'ün iki kazancı vardır. Sıralı ve ters sıralı girdide pivot aralığın ortasından gelir ve n² durumu kalkar. 100 000 öğelik sıralı dizi quicksort1 ile 0,95 saniye, sirala ile 0,001 saniye sürmüştür. Ayrıca uç öğeler doğal bekçiler olur: a[L] ≤ pivot ≤ a[R] olduğu için j taraması en geç a[L]'de durur.

İkinci iyileştirme küçük parça eşiği M'dir. Birkaç öğelik bir aralıkta çağrının ve hazırlığın sabit maliyeti asıl işten büyüktür; quicksort3 R − L ≤ M olan parçalara dokunmaz. Dizi “neredeyse sıralı” kalır: her öğe kendi küçük parçasının içinde yanlış yerdedir, parçalar birbirine göre doğru sıradadır. sirala sonunda tek bir eklemeli sıralama geçişi uygular:

void insertion(int a[], int L, int R) {
    for (int i = L + 1; i <= R; i++) {
        int v = a[i];      // yerleştirilecek
        int j = i - 1;     // a[L..i-1] sıralı
        while (j >= L && a[j] > v) {
            a[j + 1] = a[j]; // sağa kaydır
            j--;
        }
        a[j + 1] = v;
    }
}

Eklemeli sıralamanın maliyeti, öğelerin kaç konum kaydığına bağlıdır. Burada hiçbir öğe kendi parçasının dışına kaymaz. Bu yüzden son geçiş O(n · M), sabit M için doğrusal sürer.

20.4.5Kod izleme: quicksort3(a, 0, 8)

İzlemeyi kısa tutmak için M = 3 alınır. Dizi [8, 3, 5, 1, 9, 2, 7, 6, 4]'tür. Tablo hazırlık adımlarını ve özyinelemeyi verir.

Bu izlemede ilk pivot şanssızdır. Üç aday 8, 9 ve 4'tür; ortancaları 8, dizinin ikinci en büyük öğesidir. Bölme 7'ye 1 olur. Medyan-3 kötü bölmeyi tümüyle önlemez, yalnız olasılığını azaltır. Sol parçada aday öğeler 4, 1 ve 7'dir. Ortanca 4 bu kez parçanın tam ortasına düşer. quicksort3 bittiğinde dizi [1, 3, 2, 4, 6, 5, 7, 8, 9]'dur: parçalar birbirine göre sıralıdır, ama 3 ile 2 ve 6 ile 5 kendi parçalarında yer değiştirmiş durumdadır. Son eklemeli geçiş bu iki çifti iki kaydırmayla düzeltir.

M = 10 ile bu dokuz öğelik dizide quicksort3 ilk satırda döner ve bütün işi eklemeli sıralama yapar. İki sürüm de 3000 rastgele, tekrarlı diziyle sınanmıştır.

20.4.6Eşiğin etkisi ve sınırları

Kaynaklarda 5 ≤ M ≤ 25 aralığındaki eşiklerin süreyi yaklaşık %10 azalttığı belirtilir. Kazanç makineye bağlıdır ve küçüktür; ölçmek için çok tekrar gerekir. Tablo, bir milyon rastgele öğenin sirala ile sıralanma süresini farklı M değerleri için verir. M = 1, eşiğin pratikte kapalı olduğu durumdur: medyan-3 için en az üç öğe gerektiğinden en küçük anlamlı değer budur.

Eşik süreyi %10–15 kısaltmış, 5 ile 50 arasındaki değerler arasında belirgin bir fark çıkmamıştır. Farklar gürültüye yakın olduğu için ölçüm tekrarlanıp ortanca alınmıştır.

Medyan-3'ün bir sınırı vardır. Sıralı ve ters sıralı girdiyi kurtarır, ama her girdiyi kurtarmaz. Ortanca adaylarının hep küçük çıkacağı biçimde özel olarak kurulmuş girdiler yine n² sürer. Rastgele veride bu olasılık ihmal edilebilir; ama girdiyi bir saldırganın seçebildiği sistemlerde, örneğin bir ağ sunucusunda, bu bir zayıflıktır. Kesin çözüm, en kötü durum güvencesi veren hibrit bir yöntemdir: özyineleme fazla derinleşen parçalar heap sort ile sıralanır.

Böyle bir ölçümün bugün birkaç dakika sürmesi de yeni bir durumdur. Eskiden program delikli kartlara aktarılır, bir kişiye günde bir, en çok iki kez derleme sırası gelirdi. Zorunlu stajların bu kıtlık döneminde, uygulama eksikliğini kapatmak için konduğu düşünülebilir. Bugün günde onlarca kez derlemek mümkündür. Dersin amacı da hazır kalıpları uygulayan değil, bir algoritmayı kanıtlayan, ölçen ve gerekirse yenisini kuran, bilim insanı gibi düşünen mühendisler yetiştirmektir.

20.5C kitaplığı ve hibrit sıralamalar

20.5.1qsort

Standart C kitaplığı, <stdlib.h> başlığında genel amaçlı bir sıralama yordamı sunar:

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

Parametreler dizinin adresi, öğe sayısı, bir öğenin bayt cinsinden boyu ve karşılaştırma fonksiyonunun adresidir. qsort öğe türünü bilmez; diziyi size baytlık bloklar olarak görür. İlk parametre bu yüzden bir void işaretçidir (void pointer): her nesnenin adresini taşıyabilen ama tür bilgisi taşımayan işaretçi. void * doğrudan çözülemez; önce gerçek türe dönüştürülür.

Dördüncü parametre bir fonksiyon işaretçisidir (function pointer): iki const void * alıp int döndüren bir fonksiyonun adresi. C'de ayraçsız yazılan fonksiyon adı fonksiyonun adresini verir. qsort iki öğeyi karşılaştırırken bu fonksiyonu öğelerin adresleriyle çağırır; karşılaştırıcı değiştirilerek her tür sıralanabilir.

int artan(const void *p, const void *q) {
    int x = *(const int *)p;
    int y = *(const int *)q;
    return (x > y) - (x < y);  // -1, 0, +1
}
int main(void) {
    int a[] = {37, 15, 24, 33, 49};
    size_t n = sizeof a / sizeof a[0];
    qsort(a, n, sizeof a[0], artan);
    for (size_t i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

Program <stdio.h> ve <stdlib.h> başlıklarıyla derlenir ve 15 24 33 37 49 yazar.

• artan. Gelen void işaretçiler const int *'a dönüştürülür ve çözülür. const, karşılaştırma fonksiyonunun öğeleri değiştirmeyeceğini belirtir. Dönüş değeri (x > y) - (x < y)'dir. C'de bir karşılaştırma işleci doğruysa 1, yanlışsa 0 verir. x > y ise sonuç 1 − 0 = 1, x < y ise 0 − 1 = −1, eşitse 0'dır.
• sizeof a / sizeof a[0]. Dizinin toplam boyu bir öğenin boyuna bölünür. int 4 bayt olduğunda 20 / 4 = 5 bulunur. Bu ifade yalnız dizinin tanımlandığı yerde doğru sonuç verir. Dizi bir fonksiyona parametre olarak geçirildiğinde işaretçiye dönüşür ve sizeof işaretçinin boyunu verir.
• qsort(a, n, sizeof a[0], artan). artan ayraçsız yazılmıştır; çağrılmaz, adresi geçirilir. Öğe boyu sizeof(int) yerine sizeof a[0] ile yazılmıştır. Dizinin türü değişirse bu ifade kendiliğinden doğru kalır.

20.5.2Kod izleme: qsort ve karşılaştırma fonksiyonu

Karşılaştırma fonksiyonu bir sözleşmeye uymalıdır. Birinci öğe ikinciden önce gelmeliyse negatif, sonra gelmeliyse pozitif, ikisi eşitse sıfır döndürür. Dönüş değerinin büyüklüğü önemsizdir, yalnız işareti kullanılır. Fonksiyon tutarlı da olmalıdır: a < b ve b < c diyorsa a < c demelidir. Aynı iki öğe için her çağrıda aynı cevabı vermeli, öğeleri değiştirmemelidir. Bu kurallardan biri bozulursa qsort'un davranışı tanımsızdır: dizi yanlış sıralanabilir, hatta bazı gerçeklemelerde dizinin dışına çıkılabilir.

20.5.3Tutanak sıralamak

Gerçek uygulamalarda sıralanan şey genellikle bir sayı değil, birden çok alanı olan bir tutanaktır (record). Tutanaklar C'de struct ile gösterilir. Sıralamanın hangi alana göre yapılacağını karşılaştırma fonksiyonu belirler:

typedef struct { char ad[20]; int not_; } ogrenci;

int ada_gore(const void *p, const void *q) {
    const ogrenci *x = p, *y = q;
    return strcmp(x->ad, y->ad);        // alfabetik
}
int nota_gore_azalan(const void *p, const void *q) {
    const ogrenci *x = p, *y = q;
    return (y->not_ > x->not_) - (y->not_ < x->not_);
}
/* qsort(s, n, sizeof s[0], ada_gore); */

ogrenci yapısı 20 karakterlik bir ad ve bir not taşır; boyu 24 bayttır. not_'taki alt çizgi, <iso646.h>'teki not makrosuyla ve C++'taki not işleciyle çakışmayı önler.

C'de void * açık dönüştürme yazılmadan başka bir nesne işaretçisine atanabilir; const ogrenci *x = p bu yüzden geçerlidir. strcmp zaten qsort'un sözleşmesine uyan bir değer döndürür. nota_gore_azalan'da x ile y'nin yeri değiştirilerek yüksek not öne alınmıştır.

Bu iki fonksiyon {Zeynep 85, Ali 70, Mehmet 85, Ayse 92, Can 70} dizisiyle denenmiştir. ada_gore ile sıralama Ali, Ayse, Can, Mehmet, Zeynep verir. Bu sıralı dizi ardından nota_gore_azalan ile sıralandığında sonuç Ayse 92, Mehmet 85, Zeynep 85, Can 70, Ali 70 olmuştur. Notu 70 olan iki öğrencinin alfabetik sırası bozulmuştur. Bu bir hata değildir. Standart, qsort'un kararlı olmasını ya da belirli bir algoritmayı kullanmasını istemez. Eşit anahtarlarda sıra önemliyse karşılaştırma fonksiyonuna ikincil bir anahtar eklenir:

int nota_sonra_ada(const void *p, const void *q) {
    const ogrenci *x = p, *y = q;
    int k = (y->not_ > x->not_) - (y->not_ < x->not_);
    if (k != 0) return k;               /* notlar farklı: yüksek not önce */
    return strcmp(x->ad, y->ad);        /* notlar eşit: alfabetik */
}

Bu fonksiyonla sonuç Ayse 92, Mehmet 85, Zeynep 85, Ali 70, Can 70 olur ve girdinin sırasından bağımsızdır.

Kitaplık yordamının bedeli, her karşılaştırmanın bir fonksiyon çağrısı olmasıdır. Bir milyon rastgele int qsort ile 0,21 saniyede, sirala ile 0,10 saniyede sıralanmıştır (-O2; süreler makineye göre değişir). Yine de qsort sınanmış ve her türle çalışan hazır bir yordamdır; çoğu programda doğru seçim odur. Hangi algoritmayı kullandığı gerçeklemeden gerçeklemeye değişir.

20.5.4Hibrit sıralamalar

Tek bir algoritma her durumda en iyi değildir. Hızlı sıralama ortalamada hızlıdır ama en kötü durumda n²'ye çıkar. Heap sort en kötü durumda da n lg n'dir ama sabiti büyüktür. Eklemeli sıralama küçük ve neredeyse sıralı dizilerde rakipsizdir. Hibrit sıralama (hybrid sort) bu güçlü yanları birleştirir:

• Hızlı + eklemeli. Küçük parçalarda özyinelemenin maliyeti baskındır. M'den küçük parçalar eklemeli sıralamayla bitirilir. quicksort3 ile sirala bunun örneğidir.
• Introsort (Musser, 1997). Hızlı sıralamayla başlar ve özyineleme derinliğini izler. Derinlik yaklaşık 2⌊lg n⌋'i aşarsa, bu, bölmelerin kötü gittiğinin işaretidir; o parça heap sort ile sıralanır. Böylece en kötü durum O(n lg n)'ye iner. Küçük parçalar yine eklemeliyle bitirilir. C++ kitaplığındaki std::sort gerçeklemelerinde yaygındır.
• Timsort (Peters, 2002). Birleştirme sıralaması ile eklemeli sıralamayı birleştirir. Verideki hazır sıralı bölümleri, “koşuları” (run) bulur ve onları birleştirir. Gerçek verideki düzeni kullandığı için neredeyse sıralı girdilerde doğrusal süreye yaklaşır. Kararlıdır. Python'un sort'u ve Java'nın nesne dizileri için Arrays.sort'u Timsort'tur.

Ortak fikir üç katmanlıdır: büyük ölçekte iyi asimptotik davranış (n lg n), küçük ölçekte düşük sabit (eklemeli) ve en kötü durum için bir sigorta. Gerçek kitaplıklardaki sıralama yordamları ders kitaplarındaki saf algoritmalardan bu yüzden farklıdır.

20.6Birleştirme sıralaması

20.6.1Fikir

Birleştirme sıralaması (merge sort) John von Neumann'ın 1945'te tanımladığı bir parçala ve yönet algoritmasıdır. Dört cümleyle anlatılır:

1. Liste 0 ya da 1 öğeliyse zaten sıralıdır.
2. Değilse liste olabildiğince eşit iki parçaya ayrılır.
3. Her parça birleştirme sıralaması özyinelemeli uygulanarak sıralanır.
4. Kendi içinde sıralı iki alt liste tek bir sıralı listede birleştirilir.

Algoritma iki gözleme dayanır. Birincisi, küçük bir listeyi sıralamak daha az adım ister. İkincisi, sıralı iki listeden tek bir sıralı liste elde etmek, sırasız iki listeden elde etmekten çok daha ucuzdur. Sıralı iki listenin en küçük öğesi her zaman baştadır; birleştirilmiş listenin sıradaki öğesi bu iki baştan küçük olanıdır. Bu yüzden birleştirme, iki listenin uzunlukları toplamı kadar adımda biter.

Hızlı sıralamada her bölümleme pivotu kesin yerine koyar. Birleştirme sıralamasında bölme sırasında hiçbir öğe yerine oturmaz; algoritma sıralı iki dizinin “sıralı olma” avantajını kullanır. Girdiyi ortadan ikiye bölmek hızlı sıralamada şansa bağlıydı; burada her zaman böyledir.

20.6.2merge: iki uçtan birleştirme

Kod Sedgewick'in kitabındaki sürümdür. Birleştirmeyi yerinde yapmak zordur; bu yüzden a ile aynı boyda yardımcı bir b dizisi kullanılır.

void merge(int a[], int b[], int L, int m, int R) {
    int i, j, k;
    for (i = m + 1; i > L; i--) b[i - 1] = a[i - 1];
    for (j = m; j < R; j++) b[R + m - j] = a[j + 1];
    for (k = L; k <= R; k++)
        if (kucuk(b[j], b[i]))
            a[k] = b[j--];
        else
            a[k] = b[i++];
}

merge(a, b, L, m, R), kendi içinde sıralı olan a[L..m] ve a[m+1..R] yarılarını a[L..R]'de tek bir sıralı dizi olarak birleştirir. Satır satır:

• Satır 3. Sol yarı olduğu gibi b[L..m]'ye kopyalanır. Döngü i = m + 1'den başlar, b[i-1] = a[i-1] ataması yapar ve i = L olunca biter. Döngüden sonra i, sol yarının ilk öğesini gösterir.
• Satır 4. Sağ yarı b[m+1..R]'ye ters sırada kopyalanır. j = m için b[R] = a[m+1], j = R - 1 için b[m+1] = a[R] yazılır. Döngü j = R ile biter; j, sağ yarının en küçük öğesini gösterir.
• Satır 5–9. k, a'da yazılacak konumdur. Her adımda b[i] ile b[j] karşılaştırılır ve küçük olan a[k]'ye yazılır. Sağdan alınırsa j azalır, soldan alınırsa i artar. Eşitlikte kucuk(b[j], b[i]) yanlıştır ve soldaki öğe alınır.

Ters kopyalama kodun en ince noktasıdır. Kopyadan sonra b[L..R] önce artan, sonra azalan, yani bitonik bir dizidir. Sıradan birleştirmede her adımda “bu yarı bitti mi?” denetimi gerekir. Burada sol yarı bitince i sağ yarının büyük öğelerine girer ve bunlar b[j]'den küçük değildir; döngü artık hep j'den alır. Sağ yarı için de durum simetriktir: her yarı ötekinin bekçisidir.

20.6.3Kod izleme: merge(a, b, 0, 2, 6)

a = [3, 5, 7, 4, 5, 6, 10] olsun. Sol yarı a[0..2] = 3 5 7, sağ yarı a[3..6] = 4 5 6 10'dur ve ikisi de sıralıdır. İki kopyalama döngüsünden sonra b = [3, 5, 7, 10, 6, 5, 4] olur; i = 0, j = 6'dır.

k = 5'te sol yarının son öğesi 7 alınır ve i, 3'e, yani sağ yarının içine girer. Bu noktada b[i] = b[j] = 10'dur; aynı hücreyi iki indis birlikte gösterir. Son adımda bu öğeyi i alır. Sonunda i = 4, j = 3'tür; iki indis ortada buluşmuştur. Hiçbir sınır denetimi yapılmamış, buna gerek de olmamıştır. Eşit 5'lerde soldaki, yani b[i] önce alınmıştır.

Birleştirme R − L + 1 öğeyi kopyalar ve her yerleştirmede tam bir karşılaştırma yapar. Zaman maliyeti Θ(R − L + 1)'dir; iki yarının boyu ne olursa olsun bu değişmez.

20.6.4mergesort ve yardımcı dizi

void mergesort(int a[], int b[], int L, int R) {
    if (R <= L) return;
    int m = (R + L) / 2;
    mergesort(a, b, L, m);
    mergesort(a, b, m + 1, R);
    merge(a, b, L, m, R);
}

Yordam aralık boş ya da tek öğeliyse döner. Değilse ortayı m = (R + L) / 2 ile bulur, iki yarıyı sıralar ve birleştirir. Aralık tek sayıda öğeliyse sol yarı bir fazla öğe alır: 17 öğe 9 + 8 diye bölünür.

Yardımcı dizi b parametre olarak geçirilir. Her merge çağrısında yeniden ayrılsaydı her çağrı bir malloc ve bir free yapardı; bu, n − 1 kez bellek isteğinin yükü demektir. Doğrusu, diziyi bir kez ayırıp bütün çağrılara aynı diziyi vermektir. Bunu bir sarmalayıcı fonksiyon yapabilir:

int birlestirme_sirala(int a[], int n) {
    int *b = malloc(n * sizeof *b);   /* a ile aynı boyda */
    if (b == NULL) return 0;          /* bellek yok: sıralanmadı */
    mergesort(a, b, 0, n - 1);
    free(b);
    return 1;
}

malloc'un döndürdüğü işaretçi NULL ise bellek ayrılamamıştır. Bu durumda dizi sıralanmadan 0 döndürülür; çağıran durumu bu dönüş değerinden anlar. n * sizeof *b ifadesi, b'nin gösterdiği türün boyunu kullanır. b'nin türü değişse bile ifade doğru kalır. İş bitince blok free ile geri verilir. free unutulsaydı her çağrıda 4n bayt kaybolurdu; bu bir bellek sızıntısıdır. Sarmalayıcı, 10 öğelik bir diziyle ve sayaçlı bir malloc/free çiftiyle sınanmıştır: bir ayırma, bir geri verme.

20.6.5Kod izleme: dokuz merge çağrısı

Dizi [89, 67, 59, 62, 23, 93, 24, 20, 28, 60] olsun. mergesort(a, b, 0, 9) önce sol yarıyı tamamen sıralar. İlk birleştirme ancak en derindeki (0, 1) çağrısında olur. Tablo on öğe için yapılan dokuz birleştirmeyi sırasıyla verir.

7. birleştirmede dizi değişmez; 28 ve 60 zaten sıralıdır. merge bunu bilmez ve iki öğeyi yine kopyalayıp geri yazar. Birleştirme sıralaması girdinin düzeninden yararlanmaz; analizinin ana sonucu da budur.

20.6.6Çerçeve ağacı

Özyinelemeli çağrıların düzeni bir ağaçla gösterilebilir. Her düğüm bir mergesort çağrısının çerçevesidir ve içinde L, R ve m değerleri durur. Şekil bu ağacı verir. Algoritma soldan derine iner, dönüşte birleştirir. Bir düğümdeki merge ancak iki çocuğunun işi bittikten sonra yapılır; bu, ağacın kök sonda gezinmesidir.

Ağaçta 19 düğüm vardır: 9 iç düğüm merge yapar, 10 yaprak tek öğeli aralıklardır. Ağacın yüksekliği ⌈lg 10⌉ = 4'tür; çağrı yığınında aynı anda en çok beş mergesort çerçevesi bulunur. Sıralı iki kaynaktan tek bir sıralı çıktı üretme mantığı, veri yapılarında “merge” adıyla sık sık karşımıza çıkar.

20.6.7Özyinelemeli satırların sırası

Yordamdaki iki mergesort satırının yerleri değiştirilsin. Önce sağ yarı, sonra sol yarı sıralanır. Ne değişir? Sonuç değişmez, çünkü iki yarı birbirinden bağımsızdır ve merge ikisi de bittikten sonra çağrılır. Değişen, birleştirmelerin sırası ve ara tablolardır. Tablo aynı dizi için yeni sırayı verir.

Çerçeve ağacı aynıdır; yalnız her düğümde önce sağ çocuk gezilir.

20.6.8Analiz ve kararlılık

n öğeli bir dizi ⌈n/2⌉ ve ⌊n/2⌋ öğeli iki yarıya bölünür; birleştirme n karşılaştırma yapar. Karşılaştırma sayısı a_n şu bağıntıya uyar:

a_n = a_⌈n/2⌉ + a_⌊n/2⌋ + n, a₁ = 0

Örneğin 16 öğe 8 + 8, 17 öğe 9 + 8 diye bölünür. n = 2^k ise iki yarı eşittir ve bağıntı a_n = 2a_n/2 + n olur. Bu, hızlı sıralamanın en iyi durum bağıntısıdır ve a_n = n lg n verir.

Sayaçlı çalıştırma bu değerleri doğrulamıştır. 10 öğe için 19 çağrı, 9 birleştirme ve 34 karşılaştırma; 16 öğe için 31 çağrı, 15 birleştirme ve tam 16 · 4 = 64 karşılaştırma; 17 öğe için 33 çağrı ve 70 karşılaştırma yapılmıştır. Bağıntı elle de açılabilir: a₁₀ = 2a₅ + 10, a₅ = a₃ + a₂ + 5 = 5 + 2 + 5 = 12 ve a₁₀ = 34.

Süre dizinin durumundan bağımsızdır: en iyi, ortalama ve en kötü durumun üçü de n lg n'dir; kötü bir girdi yoktur. Bedeli O(n) ek bellektir. Bunu kaldırmanın yolları maliyeti artırır; ek bellek istenmiyorsa heap sort öne çıkar.

Birleştirme, sıralı parçaları sırayla okuyup sırayla yazar. Bu özellik onu, belleğe sığmayan dosyaların diskte sıralanmasının, yani dış sıralamanın temeli yapar: belleğe sığan parçalar sıralanıp diske yazılır, sonra birleştirilir.

Kararlılık konusu bir ayrım gerektirir. Klasik birleştirme, eşitlikte sol yarıdaki öğeyi alır ve kalan öğeleri ayrıca kopyalar; bu birleştirme kararlıdır. Hızlı sıralama ve heap sort kararlı değildir; birleştirme sıralaması bu yönüyle onlardan ayrılır. Ancak buradaki ters kopyalı, bitonik merge kararlı değildir. Sol yarı bittiğinde i sağ yarının ters sıradaki öğelerine girer ve eşit öğeleri ters sırada alır. Dört eşit anahtar [2a, 2b, 2c, 2d] ile sıralama [2a, 2b, 2d, 2c] vermiştir: 2c ile 2d yer değiştirmiştir. Değerleri 0–3 arasında, 2–10 öğelik 1000 rastgele dizide denemede 194 dizide eşitlerin sırası bozulmuştur. Kararlılık gerekiyorsa sağ yarı ters kopyalanmaz ve yarılardan birinin bitip bitmediği denetlenir.

20.7Bağlı birleştirme sıralaması

20.7.1Büyük tutanaklar ve bag alanı

Gerçek uygulamalarda öğe, örneğin bir öğrencinin adını ve adresini taşıyan yüzlerce baytlık bir tutanak olabilir. Böyle tutanakları her birleştirmede iki dizi arasında kopyalamak zaman alır. Çözüm, tutanakları hiç taşımamaktır: her tutanağa bir bag alanı eklenir ve dizinin içinde indislerle bir bağlı liste kurulur. Sıralama yalnız indisleri değiştirir.

typedef struct {
    int anahtar;   /* + büyük veri alanları */
    int bag;       /* sonraki öğenin indisi, 0 = son */
} eleman;

int mergesort(eleman a[], int L, int R) {
    if (R <= L) return L;          /* tek öğeli liste */
    int m = (R + L) / 2;
    int sag = mergesort(a, m + 1, R);
    int sol = mergesort(a, L, m);
    return merge(a, sol, sag);     /* baş indisi */
}

eleman yapısı bir anahtar ve bir bağ taşır. Açıklamadaki “+ büyük veri alanları” ifadesi, gerçek uygulamada yapının çok daha büyük olabileceğini hatırlatır. bag, listede bu öğeden sonra gelen öğenin dizideki indisidir; 0 listenin sonunu gösterir. Bu yüzden veriler a[1..n]'de durur ve a[0] öğe olarak kullanılmaz. a[0], birleştirme sırasında geçici bir liste başı olarak iş görür. Başlangıçta bütün bag alanları 0'dır: her öğe tek başına bir listedir.

mergesort bu kez bir değer döndürür: a[L..R] aralığındaki öğelerden kurulan sıralı listenin baş indisini. Tek öğeli aralıkta liste o öğenin kendisidir ve L döndürülür. Daha büyük aralıkta iki yarı ayrı ayrı sıralanır, döndükleri listeler merge ile birleştirilir ve yeni listenin başı döndürülür.

Kodda sağ yarı önce sıralanır ve bu sıra bilinçli olarak iki ayrı satırda yazılmıştır. İki çağrı merge'ün argümanları olarak yazılsaydı hangisinin önce çalışacağı belli olmazdı: C'de argümanların değerlendirilme sırası belirtilmemiştir. Sonuç aynı çıkar, ama ara durumlar ve elle hazırlanan izleme tablosu derleyiciye göre değişir.

20.7.2Bağlı merge

int merge(eleman a[], int birinci, int ikinci) {
    int sonuc = 0;              // a[0]: geçici baş
    int i1 = birinci, i2 = ikinci;
    while (i1 && i2)
        if (a[i1].anahtar <= a[i2].anahtar) {
            a[sonuc].bag = i1; sonuc = i1;
            i1 = a[i1].bag;
        } else {
            a[sonuc].bag = i2; sonuc = i2;
            i2 = a[i2].bag;
        }
    a[sonuc].bag = i1 ? i1 : i2;
    return a[0].bag;
}

merge(a, birinci, ikinci), başları birinci ve ikinci olan iki sıralı listeyi tek sıralı listede birleştirir ve yeni listenin baş indisini döndürür. Satır satır:

• Satır 2. sonuc, birleşmiş listenin o ana kadarki son öğesidir. Başta liste boştur ve sonuc = 0, yani geçici baş a[0]'dır. Bu küçük hile, “ilk öğe mi?” diye ayrı bir durum yazma zorunluluğunu kaldırır. İlk eklenen öğe de a[sonuc].bag üzerinden, yani a[0].bag'e yazılır.
• Satır 3. i1 ve i2, iki listenin henüz alınmamış ilk öğeleridir.
• Satır 4–11. İki listede de öğe kaldıkça döngü sürer. Küçük anahtarlı öğe birleşmiş listenin sonuna bağlanır (a[sonuc].bag = i1), sonuc ona ilerler ve alınan listenin indisi bir sonraki öğeye geçer. Eşitlikte <= sayesinde birinci listedeki öğe alınır. Birinci liste sol yarıdan geldiği sürece eşit anahtarlar girişteki sıralarını korur; bu sürüm kararlıdır.
• Satır 12. Listelerden biri bitince ötekinin kalanı tek bağla eklenir. Dizi sürümündeki gibi kalan öğeleri tek tek kopyalamaya gerek yoktur; kalan kısım zaten sıralı bir listedir.
• Satır 13. Birleşmiş listenin başı a[0].bag'dedir ve döndürülür.

Bir öğe taşınmaz; yalnız bağlar yeniden yazılır. Bir birleştirmenin maliyeti, döngünün tur sayısı kadardır ve bu sayı iki listenin uzunlukları toplamından azdır. Karşılaştırma sayısı dizi sürümünden biraz küçük çıkar, çünkü listelerden biri bitince karşılaştırma da biter.

20.7.3Kod izleme: son birleştirme

Anahtarlar a[1..10] = 71, 77, 122, 38, 119, 41, 22, 115, 43, 13 olsun. mergesort(a, 1, 10)'un son, dokuzuncu birleştirmesi iki beşer öğelik listeyi birleştirir. Birinci liste (baş 4) 38 → 71 → 77 → 119 → 122, ikinci liste (baş 10) 13 → 22 → 41 → 43 → 115'tir.

Fonksiyon a[0].bag = 10'u döndürür. Bağlar izlenince sıralı liste okunur: 13 → 22 → 38 → 41 → 43 → 71 → 77 → 115 → 119 → 122. Sekiz turda sekiz karşılaştırma yapılmış, kalan iki öğe (119 ve 122) tek bağla eklenmiştir.

20.7.4bag alanlarının değişimi

Tablo bütün sıralama boyunca dokuz birleştirmeyi verir. Kodda sağ yarı önce sıralandığı için ilk birleştirme en sağdaki (9, 10) aralığındadır.

Her satır, dönüş değerinden başlayıp bağlar izlenerek okunur. 4. satırda dönüş 10'dur: 13 → 22 → 41 → 43 → 115; sağ yarı a[6..10] sıralanmıştır. 8. satırda dönüş 4'tür: 38 → 71 → 77 → 119 → 122.

Sonunda öğeler dizide hâlâ eski yerlerindedir; sıralı çıktı listeyi gezerek yazılır (for (p = bas; p; p = a[p].bag)). Ek bellek öğe başına bir int'tir; karşılaştırma sayısı O(n lg n), tutanak taşıma sayısı sıfırdır.

20.7.5Sınav sorusu

Aşağıdaki soru bağlı sürümün bir başka yazımını kullanır. Soruda öğeler a[1..9]'dur ve anahtarlarına göre sıralanır. İstenenler şunlardır: (i) özyinelemeli çağrıların yığın çerçevelerini çizmek ve merge çağrılmışsa dönüş değerini yazmak; (ii) işletim tablosunu merge numaraları, dönüş değerleri ve her adımdaki bag alanlarıyla doldurmak.

int mergesort(eleman a[], int L, int R) {
    int m;
    if (R <= L) return L;
    m = (R + L) / 2;
    return merge(a, mergesort(a, m + 1, R),
                    mergesort(a, L, m));
}

Anahtarlar [1] ?, [2] ?, [3] 18, [4] −5, [5] 27, [6] 11, [7] ?, [8] 83, [9] 30'dur. Soru kâğıdındaki soru işaretleri yerine burada 42, 7 ve 55 alınmıştır. merge, bağlı birleştirme sıralamasındakinin aynısıdır. Sorunun basılı sürümünde else dalında i1 yazılmıştı; bu bir yazım hatasıdır ve doğrusu i2'dir.

Sorunun ilk tuzağı, özyinelemeli çağrıların merge'ün argümanları olmasıdır; hangi yarının önce sıralanacağı derleyiciye kalır. Çözümde argümanların soldan sağa değerlendirildiği, yani önce sağ yarının sıralandığı varsayılır. Çağrı sırası şöyledir: (1, 9) → (6, 9) → (8, 9) → (9, 9) → (8, 8) → (6, 7) → (7, 7) → (6, 6) → (1, 5) → …. İkinci tuzak, merge'e birinci liste olarak sağ yarının geçirilmesidir. Eşitlikte birinci liste önce alındığı için bu yazım kararlı değildir; bu sorudaki anahtarlar farklı olduğundan sonucu etkilemez.

Sonuç listesinin başı 4'tür: −5 → 7 → 11 → 18 → 27 → 30 → 42 → 55 → 83. Tablo, değerlendirme sırası açıkça yazılmış bir C programıyla üretilmiştir. Argümanlar sağdan sola değerlendirilseydi ilk birleştirme (1, 2)'de olur, ara satırlar değişir; son satır ve sonuç aynı kalır.

20.8Heap sort

Birleştirme sıralaması her durumda O(n lg n)'dir ama O(n) ek bellek ister. Hızlı sıralama yerinde çalışır ama en kötü durumda n²'ye çıkar. Heap sort iki iyi özelliği birleştirir: en kötü durumda da O(n lg n) sürer ve fazladan bellek kullanmaz. Bunu, öncelikli kuyrukları gerçeklemekte kullanılan heap yapısını sıralanacak dizinin içinde kurarak yapar.

20.8.1Dizi bir ağaçtır

Dizi a[1..n] olarak düşünülür; a[0] kullanılmaz. Bu dizi bir tam ikili ağaç (complete binary tree) gibi okunur: kök a[1]'dir, a[i]'nin çocukları a[2i] ve a[2i+1]'dir, ebeveyni a[i/2]'dir. Ağacın düğümleri düzey düzey, soldan sağa diziye yerleşir. Bu yüzden hiçbir işaretçi gerekmez; bağlar indis aritmetiğinden çıkar. 1 tabanlı indis bu formülleri sadeleştirir. 0 tabanlı dizide çocuklar 2i + 1 ve 2i + 2 olurdu.

Heap sort iki aşamada çalışır. Önce dizi bir maksimum heap'e çevrilir. Sonra kökteki en büyük öğe dizinin sonuna alınır, heap bir öğe küçülür ve kalan heap düzeltilir. Bu adım n − 1 kez tekrarlanınca dizi küçükten büyüğe sıralanmış olur.

void heapify(int a[], int kok, int n) {
    int t = a[kok], j;
    for (j = 2 * kok; j <= n; j *= 2) {
        if (j < n && a[j] < a[j + 1]) j++; // büyük
        if (t >= a[j]) break;   // t buraya sığar
        a[j / 2] = a[j];        // çocuğu yukarı al
    }
    a[j / 2] = t;
}
void heapsort(int a[], int n) {     /* a[1..n] */
    int i;
    for (i = n / 2; i >= 1; i--)     /* heap kur */
        heapify(a, i, n);
    for (i = n - 1; i >= 1; i--) {   /* sırala */
        SWAP(a[1], a[i + 1]);    /* en büyüğü sona */
        heapify(a, 1, i);            /* heap'i düzelt */
    }
}

20.8.2heapify

heapify(a, kok, n), a[1..n] heap'inde kok düğümünün sol ve sağ alt ağaçları zaten maksimum heap iken kökteki değere uygun yeri arar. Bu, öncelikli kuyruklarda en büyüğü alırken yapılan aşağı kaydırma işleminin aynısıdır; Horowitz'in kitabında adjust adıyla geçer. Satır satır:

• Satır 2. Kökteki değer t'ye alınır. Kökte artık bir “boşluk” vardır. t en sonda bu boşluğun indiği yere yazılacaktır.
• Satır 3. j, boşluğun sol çocuğudur: 2 * kok. Döngü her turda bir düzey aşağı iner (j *= 2) ve j heap'in dışına çıkınca biter.
• Satır 4. Sağ çocuk varsa (j < n) ve sol çocuktan büyükse j sağ çocuğa geçer. j artık büyük çocuğu gösterir.
• Satır 5. t büyük çocuktan küçük değilse boşluk tam yerindedir; döngüden çıkılır.
• Satır 6. Aksi hâlde büyük çocuk boşluğa, yani ebeveynine a[j/2]'ye çıkarılır. Boşluk j'ye iner.
• Satır 8. Döngü nerede biterse bitsin boşluk a[j/2]'dedir ve t oraya yazılır. break ile çıkıldığında j/2 boşluğun kendisidir. Döngü j > n ile bittiğinde de j son boşluğun çocuğu olurdu; j/2 yine boşluğu verir.

Takas yerine kaydırma yapılır: düzey başına bir atama, sonda t için bir atama. heapify'ın maliyeti boşluğun indiği düzey sayısıyla orantılıdır ve lg n'yi aşamaz.

20.8.3Heap kurma

Diziyi heap'e çevirmenin ilk akla gelen yolu, öğeleri boş bir heap'e tek tek eklemektir. Kruskal algoritması gibi uygulamalarda öğeler zaten tek tek geldiği için heap böyle kurulur. Her ekleme O(lg n) sürdüğünden toplam O(n lg n)'dir. Öğeler baştan bir dizide hazırsa daha iyi bir yol vardır: aşağıdan yukarıya heap oluşturma (bottom-up heap construction).

Yapraklar zaten tek öğelik heap'lerdir. i > ⌊n/2⌋ olan düğümlerin çocuğu yoktur, çünkü sol çocukları 2i > n konumuna düşerdi. Bu yüzden döngü ⌊n/2⌋'den başlar ve köke doğru geriye gider: ⌊n/2⌋, ⌊n/2⌋ − 1, …, 1. Her i için düğümün alt ağaçları daha önce düzeltilmiştir; heapify'ın ön koşulu sağlanır. Döngü köke ulaştığında bütün dizi bir maksimum heap'tir.

Horowitz'in örneği [26, 5, 77, 1, 61, 11, 59, 15, 48, 19] dizisidir; n = 10, ⌊n/2⌋ = 5'tir.

Kurma aşaması toplam 5 kaydırma yapmıştır. Sonuç geçerli bir maksimum heap'tir: kök 77'dir ve her düğüm çocuklarından büyüktür. Örneğin a[2] = 61'in çocukları a[4] = 48 ve a[5] = 19'dur.

20.8.4Sıralama aşaması

Dizi heap olduktan sonra en büyük öğe köktedir. Bu öğe dizinin son hücresiyle takas edilir: SWAP(a[1], a[i + 1]). En büyük öğe artık kesin yerindedir. Heap bir öğe küçülür ve a[1..i] olur. Köke gelen öğe heap koşulunu büyük olasılıkla bozar, ama iki alt ağaç hâlâ heap'tir; heapify(a, 1, i) bunu düzeltir. Dizinin sonunda sıralı öğelerin biriktiği bölge her turda bir hücre büyür.

Son turda i = 1'dir. 5 sona gider ve kökte tek öğe, 1 kalır. Tek öğelik bir ağaç zaten heap'tir. heapify(a, 1, 1)'de j = 2 > 1 olduğu için döngüye hiç girilmez ve 1 yerinde kalır. Dizi artık sıralıdır: [1, 5, 11, 15, 19, 26, 48, 59, 61, 77]. Kod ayrıca 1–200 öğelik, tekrarlı anahtarlar içeren 2000 rastgele diziyle sınanmış ve hepsini doğru sıralamıştır.

“Heap'i anladık, ama dizi ne zaman sıralanacak?” sorusunun cevabı, heap'in bir ara düzen olmasıdır: yalnız en büyük öğenin yerini bilir. Sıralama bu bilgiyi n − 1 kez kullanır.

20.8.5Analiz

Kaba analizle heapify en çok lg n kaydırma yapar ve n/2 kez çağrılır: O(n lg n). Bu sınır gevşektir, çünkü çağrıların çoğu küçük alt ağaçlarda yapılır.

İnce analiz için ağaç düzey düzey incelenir. k, ağacın düzey sayısı olsun; k ≈ lg(n + 1)'dir. i. düzeyde en çok 2ⁱ⁻¹ düğüm vardır. Bu düzeydeki bir düğüm en çok k − i düzey aşağı kayabilir. En kötü durumda toplam kaydırma sayısı

Σ_i=1^k 2ⁱ⁻¹(k − i) = k Σ_i=1^k 2ⁱ⁻¹ − Σ_i=1^k i · 2ⁱ⁻¹

olur. İlk toplam geometrik seridir: 2^k − 1. İkinci toplam, geometrik serinin türevinden bulunur. S(y) = 1 + y + … + y^k = (y^k+1 − 1)/(y − 1) olsun. Terim terim türev alınınca S′(y) = Σ_i=1^k i · yⁱ⁻¹ elde edilir; aranan toplam S′(2)'dir. Kesrin türevi alınıp y = 2 konursa S′(2) = (k + 1)2^k − (2^k+1 − 1) = (k − 1)2^k + 1 bulunur. Böylece

k(2^k − 1) − (k − 1)2^k − 1 = 2^k − k − 1

Sınırın sıkı olduğu, en kötü durumu üreten girdiyle gösterilebilir. Artan sıralı bir dizide her iç düğümün değeri bütün alt ağacından küçüktür ve her heapify boşluğu yaprağa kadar indirir. n = 2^k − 1 öğelik artan dizilerde sayılan kaydırma sayısı formülle tam olarak örtüşmüştür (Tablo).

“≤ 2n” sınırı O(n) demektir, o(n) değil: kaydırma sayısı n ile aynı hızda büyür.

Karşılaştırma sayısı da ölçülmüştür. Her kaydırma düzeyinde iki karşılaştırma vardır: iki çocuk arasında ve t ile büyük çocuk arasında. Rastgele dizilerde toplam karşılaştırma 1000 öğe için 16 899, 50 000 öğe için 1,41 milyon, bir milyon öğe için 36,8 milyon çıkmıştır. Bunlar 2n lg n'nin yaklaşık %85–92'sidir. Kurma aşamasının payı küçüktür: bir milyon öğede 1,88 milyon karşılaştırma, yani 2n'den az.

20.8.6İleri heap sort ve veriyi tanımak

Yaklaşık 2n lg n karşılaştırma, hızlı sıralamanın 1,39 n lg n'sinden fazladır ve heap sort belleğe düzensiz erişir. Elli bin civarına kadar veri için makul bir seçimdir; daha büyük veride karşılaştırma sayısını azaltan sürümler vardır.

Bunların en bilineni aşağıdan yukarı heap sort'tur (bottom-up heapsort). Fikri şudur: kökten çıkarılan öğenin yerine gelen t neredeyse her zaman yaprağa kadar iner, çünkü dizinin sonundan gelmiştir ve küçüktür. Öyleyse her düzeyde t ile büyük çocuğu karşılaştırmak çoğu zaman boşunadır. Bottom-up sürümde boşluk, t ile karşılaştırılmadan büyük çocuklar boyunca yaprağa kadar indirilir. Sonra t, yaprakta başlayıp yukarı doğru yerine yerleştirilir. Bu yukarı yürüyüş genellikle bir iki adımda biter. Sonuçta düzey başına iki karşılaştırma yerine çoğunlukla bir karşılaştırma yapılır. Kuramsal olarak bundan da iyi sürümler bilinir.

Sıralanacak verinin bazı özellikleri biliniyorsa algoritma bu özelliklere göre seçilir. Sayarak sıralamada anahtarların küçük bir aralıkta olduğu bilinir ve hiç karşılaştırma yapılmadan doğrusal sürede sıralanır. Shell sıralaması ile kova sıralamasının birlikte kullanıldığı uygulamalar da vardır. Bu yöntemlerin temel birkaç tanesi bilinmeli ve verinin yapısı tanınmalıdır. Basamak sıralaması bu düşüncenin bir başka örneğidir.

20.9Basamak sıralaması

20.9.1Çok anahtarlı sıralama

Bazı sıralamalar birden çok anahtara göre yapılır. Bir kişi listesi önce soyadına, soyadı aynı olanlar ada göre sıralanabilir. Anahtarlar K₀, K₁, …, K_r−1 ile gösterilsin. K₀ en anlamlı anahtardır (most significant digit, MSD), K_r−1 en az anlamlı anahtardır (least significant digit, LSD). Kişi listesi örneğinde soyadı en anlamlı anahtardır. Üç basamaklı bir sayı da aynı biçimde düşünülebilir: yüzler basamağı K₀, onlar K₁, birler K₂'dir.

MSD yolunda önce en anlamlı anahtara göre gruplara ayrılır ve her grup kendi içinde sıralanır; bu yol özyinelemeli ve karmaşıktır. LSD yolu ilk bakışta tersine görünür ama çok daha sadedir.

Kararlılık şartının nedeni şudur. Yüzler geçişinde 208 ile 271'in yüzler basamağı aynıdır, 2'dir. Bu geçiş ikisini ayırt edemez. Doğru sırayı önceki geçişler belirlemiştir: onlar geçişi 208'i (onlar basamağı 0) 271'in (onlar basamağı 7) önüne koymuştur. Yüzler geçişi bu düzeni bozmazsa sonuç doğru olur. Her geçiş bir öncekinin işini korur ve üstüne daha anlamlı bir basamağı ekler.

Basamak sıralaması sayıları birbiriyle hiç karşılaştırmaz. Bu yüzden karşılaştırmasız (non-comparison) bir sıralamadır ve karşılaştırmalı sıralamaların n lg n alt sınırına bağlı değildir. Bunun bedeli, anahtarların yapısının, yani basamakların bilinmesi gerekliliğidir.

20.9.2Veri yapısı ve liste kurma

#define MAX_DIGIT 3
#define RADIX 10
typedef struct oge *oge_gost;
struct oge {
    int deger[MAX_DIGIT];  /* 179 → {1, 7, 9} */
    oge_gost bag;
};

Her öğe bir bağlı liste düğümüdür. deger dizisi sayının basamaklarını tutar: 179 için {1, 7, 9}. deger[0] yüzler (MSD), deger[1] onlar, deger[2] birler (LSD) basamağıdır. Sayılar [0, 999] aralığındadır. bag, listede sonraki düğümün adresidir.

typedef struct oge *oge_gost; yapı tanımından önce gelir ve struct oge'yi gösteren işaretçi türüne ad verir. İşaretçinin boyu yapının içeriğinden bağımsız olduğu için yapı henüz tanımlanmamış olabilir; böylece yapının içinde oge_gost bag; yazılabilir. typedef struct oge {…}; gibi ad verilmeyen bir typedef ise anlamsızdır. x86-64'te sizeof(struct oge) 24 bayttır: 12 baytlık dizi, 4 bayt hizalama boşluğu ve 8 baytlık işaretçi.

Sıralanacak listeyi kurmak da bellek yönetimi ister. Aşağıdaki iki yordam notta eklenmiştir. liste_kur, bir int dizisinden aynı sırada bir liste kurar:

/* 3 basamaklı sayılardan bağlı liste kurar; bellek yetmezse kurulanı geri verir */
oge_gost liste_kur(const int x[], int n) {
    oge_gost bas = NULL, son = NULL;
    for (int k = 0; k < n; k++) {
        oge_gost d = malloc(sizeof *d);
        if (d == NULL) {               /* yarıda kaldı: sızıntı olmasın */
            liste_sil(&bas);
            return NULL;
        }
        d->deger[0] = x[k] / 100;      /* yüzler */
        d->deger[1] = x[k] / 10 % 10;  /* onlar */
        d->deger[2] = x[k] % 10;       /* birler */
        d->bag = NULL;
        if (son) son->bag = d; else bas = d;
        son = d;
    }
    return bas;
}

/* listenin bütün düğümlerini geri verir ve çağıranın işaretçisini NULL yapar */
void liste_sil(oge_gost *pp) {
    while (*pp) {
        oge_gost sonraki = (*pp)->bag;
        free(*pp);
        *pp = sonraki;
    }
}

liste_kur her sayı için bir düğüm ayırır. malloc NULL döndürürse bellek bitmiştir. Bu durumda yarıda kalan liste geri verilmezse o ana kadar ayrılmış düğümler sızar. Yordam bu yüzden önce kurduğu kısmı liste_sil ile siler, sonra NULL döndürür. Basamaklar tamsayı bölmesi ve kalanla ayrılır: 179 / 100 = 1, 179 / 10 % 10 = 7, 179 % 10 = 9. son işaretçisi listenin son düğümünü tutar; yeni düğüm onun arkasına bağlanır ve liste girdi sırasını korur.

liste_sil, parametresini oge_gost *pp, yani işaretçinin işaretçisi olarak alır. Bu sayede düğümleri geri vermekle kalmaz, çağıranın baş işaretçisini de NULL yapar. Döngü her turda sıradaki düğümün adresini önce sonraki'ye alır, sonra düğümü geri verir. Sıra ters olsaydı, yani önce free(*pp) sonra (*pp)->bag okunsaydı, geri verilmiş belleğe erişilirdi. Bu bir tanımsız davranıştır. İki yordam sayaçlı bir malloc/free çiftiyle sınanmıştır: 500 rastgele liste kurulup sıralanıp silinmiş, 74 115 ayırmaya 74 115 geri verme karşılık gelmiştir. Bellek dördüncü düğümde bitirilen bir denemede ilk üç düğüm geri verilmiş ve NULL dönmüştür.

20.9.3radixsort

Sunumdaki döngü gövdesi, kova dizilerinin bildirimiyle birlikte bir fonksiyon olarak yazılırsa şu biçimi alır:

oge_gost radixsort(oge_gost p) {
    oge_gost on[RADIX], arka[RADIX];  /* kova başları ve sonları */
    for (int i = MAX_DIGIT - 1; i >= 0; i--) {
        for (int j = 0; j < RADIX; j++)
            on[j] = arka[j] = NULL;
        for (; p; p = p->bag) {     // dağıt
            int b = p->deger[i];
            if (!on[b]) on[b] = p;
            else arka[b]->bag = p;
            arka[b] = p;
        }
        for (int j = RADIX - 1; j >= 0; j--) // topla
            if (on[j]) { arka[j]->bag = p; p = on[j]; }
    }
    return p;
}

Her basamak değeri için bağlı liste biçiminde bir kova (bucket) vardır. on[j] kovanın ilk, arka[j] son düğümünü gösterir; kuyruktaki gibi, son düğümü tutmak arkaya sabit sürede eklemeyi sağlar.

• Dış döngü. i, MAX_DIGIT - 1'den 0'a iner: önce birler (i = 2), sonra onlar, en son yüzler basamağı işlenir. Bu LSD sırasıdır.
• Kovaları boşaltma. Her geçişin başında on kovanın ön ve arka işaretçileri NULL yapılır.
• Dağıtma. Liste baştan sona gezilir. Her düğümün i. basamağı b'ye alınır. Kova boşsa düğüm kovanın ilk düğümü olur. Değilse kovanın son düğümünün bag'i bu düğüme bağlanır. Her iki durumda da düğüm kovanın yeni sonudur. Düğümler kovaya geliş sırasıyla eklendiği için dağıtma kararlıdır. Döngü p = p->bag ile ilerler. Bu okumada düğümün eski bag'i kullanılır; düğümün kendi bağı daha değiştirilmemiştir, yalnız kovadaki önceki düğümün bağı değişmiştir. Döngü bittiğinde p NULL'dır.
• Toplama. Kovalar 9'dan 0'a gezilir. Dolu her kovanın son düğümü, o ana kadar kurulmuş listenin başına bağlanır (arka[j]->bag = p) ve listenin başı kovanın ilk düğümü olur (p = on[j]). Liste sondan başa doğru kurulur; en son eklenen 0. kova en önde durur. Böylece küçük basamaklı kova öne gelir. İlk eklenen kovanın son düğümünün bag'i, o anda NULL olan p'ye bağlanır; listenin sonu doğru biçimde kapanır.
• Dönüş. Üç geçişten sonra liste sıralıdır ve baş işaretçisi döndürülür.

20.9.4Kod izleme

Liste 179, 208, 306, 093, 859, 984, 055, 009, 271, 033 olsun. Sayılar üç basamaklı yazılmıştır, çünkü yapı her sayının üç basamağını tutar. İlk geçiş birler basamağına göredir. Tablo dağıtımı adım adım verir.

9. kovada 179, 859 ve 009 bu sırayla durur; üçü de girdide bu sırada gelmiştir. Toplama kovaları 9'dan 0'a gezer ve her kovayı listenin önüne bağlar. Sonuçta küçük kova öndedir: 271 093 033 984 055 306 208 179 859 009. Liste artık birler basamağına göre sıralıdır.

İkinci ve üçüncü geçişler aynı biçimde onlar ve yüzler basamaklarına göre yapılır. Tablo her geçişten sonraki listeyi verir.

Onlar geçişinden sonra 0. kovada 306, 208 ve 009 vardır; onlar basamaklarının hepsi 0'dır ve birler geçişinin bıraktığı sırayla dizilmişlerdir. Yüzler geçişinde 0. kovaya 009, 033, 055 ve 093 düşer. Kararlılık sayesinde bu dört öğe onlar geçişindeki sırasını korur ve kova kendiliğinden sıralı çıkar. Üç geçişin sonunda liste sıralıdır. Yordam ayrıca 1–300 öğelik 500 rastgele listeyle sınanmıştır.

20.9.5Analiz

Her geçiş üç iş yapar: RADIX kovayı boşaltır, n düğümü dağıtır ve RADIX kovayı toplar. Geçiş sayısı MAX_DIGIT'tir. Toplam süre

O(MAX_DIGIT · (RADIX + n + RADIX)) = O(MAX_DIGIT · (RADIX + n))

olur. Basamak sayısı d, taban r ile gösterilirse O(d(n + r)) yazılır. Örnekte bu O(3 · (10 + n))'dir ve doğrusal görünür. Ancak bu, sayarak sıralamadaki gibi özel bir durumdur: basamak sayısı ve taban sabit kabul edilmiştir. n farklı sayıyı ayırt etmek için en az log_r n basamak gerekir. Anahtarların aralığı n ile birlikte büyürse d de büyür ve süre yine n lg n mertebesine yaklaşır.

Algoritmanın kullanılabilmesi için veriler (a) pozitif, (b) tamsayı ve (c) küçük bir aralıkta olmalıdır. Aralık büyürse algoritma yine sıralar, ama geçiş sayısı ve karmaşıklık hızla artar. Yalnız tamsayıları sıralayabilmesi gerçek bir dezavantajdır. Kayan noktalı sayılar için uyarlanabilir, ama o uyarlama yapılana kadar öteki algoritmalar işi çoktan bitirmiş olur.

Ek bellek 2 · RADIX işaretçidir: kovaların ön ve arka işaretçileri. Liste yerinde yeniden bağlanır. Her düğümdeki bag işaretçisi de bir bellek maliyetidir, ama bu maliyet bağlı liste gösteriminden gelir, algoritmadan değil. Basamak sıralaması kararlıdır ve karşılaştırma yapmaz.

20.9.6Sınav sorusu: değiştirilmiş radix

Bir öğrenci, yordamın önce en anlamlı basamağı ele alması gerektiğini düşünür. Dış döngüyü for (i = 0; i <= MAX_DIGIT-1; i++), toplama döngüsünü for (j = 0; j <= RADIX_SIZE-1; j++) biçimine getirir. Soru, 346, 180, 008, 930, 023, 451, 670, 098, 203, 007 listesi için yordamı işletmeyi, her adımda listeyi yazmayı ve sonucu yorumlamayı ister.

İki değişikliğin etkisi ayrı ayrı yorumlanır. Birinci değişiklik geçişlerin sırasını tersine çevirir. Son geçiş birler basamağına göre yapıldığı için birler basamağı en anlamlı basamak gibi davranır. Sayılar tersten okunursa sıralıdır: 098, 008, 007 tersten 890, 800, 700'dür. İkinci değişiklik toplama döngüsünü tersine çevirir. Kovalar 0'dan 9'a gezilip her biri listenin önüne bağlandığı için en son eklenen 9. kova öne geçer. Sıra küçükten büyüğe değil, büyükten küçüğe olur. Sonuç olarak liste, tersten okunan sayılara göre azalan sıradadır: 890, 800, 700, 643, 320, 302, 154, 081, 076, 039. Tablo, değiştirilmiş döngülerle yazılmış bir C programıyla üretilmiştir.

MSD ile sıralamak için en anlamlı basamağa göre ayrılan her grubun ayrıca sıralanması gerekir; grupları bir arada tutup sonraki basamağa geçmek önceki geçişin işini bozar.

20.10Karşılaştırma ve seçim

Tablo temel ve ileri sıralama algoritmalarını karşılaştırır; zaman sütunları adım sayısının mertebesidir.

Karşılaştırmalı sıralamada alt sınır ⌈lg n!⌉ ≈ n lg n − 1,44 n'dir. Tablodaki karşılaştırmalı algoritmalardan hızlı sıralamanın ortalaması, birleştirme sıralaması ve heap sort bu sınıra sabit bir çarpan içinde yaklaşır. Sayarak ve basamak sıralaması karşılaştırma yapmadığı için bu sınıra bağlı değildir; buna karşılık anahtarlar hakkında ek bilgiye ihtiyaç duyar.

Kuramsal mertebeler aynı olsa da gerçek süreler farklıdır. Tablo bu nottaki yordamların rastgele int dizilerindeki sürelerini verir.

Bu ölçümde birleştirme sıralaması en hızlısı çıkmıştır. Bitonik merge'ün iç döngüsünde sınır denetimi yoktur ve bellek hep sırayla okunup yazılır; bu düzen modern işlemcilerin önbelleğine çok uygundur. Bedeli, bir milyon öğe için 4 MB'lık ek dizidir. Heap sort en yavaşlardandır, çünkü kökten yaprağa inen yollar bellekte büyük sıçramalar yapar. qsort'un yavaşlığı her karşılaştırmadaki fonksiyon çağrısından gelir. Medyan-3 ve eşikli sirala, quicksort1'den %20 kadar hızlıdır. Bu sonuçlar derleyiciye, işlemciye ve veriye göre değişebilir.

Hangi durumda hangi algoritmanın seçileceği şöyle özetlenebilir:

• Genel amaçlı, bellekte sıralama. Medyan-3 ve küçük parçada eklemeli kullanan hızlı sıralama ya da kitaplıktaki qsort.
• En kötü durum güvencesi. Yerinde çalışan heap sort ya da introsort.
• Kararlılık, bağlı liste ya da disk. Birleştirme sıralaması: kararlıdır, sıralı parçaları birleştirir ve dış sıralamanın temelidir.
• Büyük tutanaklar. Tutanakların kendileri değil, indisleri ya da bağları sıralanır; bağlı birleştirme sıralaması bunun örneğidir.
• Sabit uzunluklu tamsayı anahtarlar. Basamak sıralaması: d geçişin her biri O(n + r).
• Küçük aralıktaki anahtarlar. Sayarak sıralama.

20.11Sık yapılan hatalar

1. bol'daki j döngüsünde j == L sınamasını unutmak: pivot en küçükse dizinin başından taşılır.
2. Sıralı girdide pivotu hep a[R] seçmek: derinlik n, süre n² olur. Çare medyan-3 ya da rastgele pivottur.
3. Özyinelemesiz sürümde parçaları boyuna bakmadan itmek: yığın O(n)'e büyür ve sabit boylu dizi taşar.
4. Medyan-3'te SWAP argümanlarını ters vermek: büyük öğe a[L]'ye gider ve bölümleme bozulur.
5. b[]'yi her çağrıda malloc'lamak (yavaş) ya da hiç ayırmamak (tanımsız davranış); NULL denetimini ve free'yi unutmak.
6. Bağlı merge'ün else dalında i2 yerine i1 yazmak; argümanların değerlendirilme sırasına güvenmek.
7. heapify'da 1 tabanlı formülleri 0 tabanlı diziyle kullanmak.
8. qsort karşılaştırıcısında return x - y; yazmak ya da tutarsız bir karşılaştırıcı kullanmak.
9. Basamak sıralamasında düğümü kovanın önüne eklemek: dağıtım kararsızlaşır ve sonuç yanlış çıkar.

20.12Alıştırmalar ve çözümleri

Cevaplar sunumdakilerle aynıdır; burada çözüm adımları da verilmiş ve kodlar çalıştırılarak doğrulanmıştır.

1. [5, 9, 1, 7, 3] için bol(a, 0, 4) sonucunda dizi ve dönüş değeri nedir?

Çözüm. Pivot v = a[4] = 3'tür. i, a[0] = 5'te durur (5 ≥ 3). j, 7'yi geçer ve a[2] = 1'de durur (1 ≤ 3). i = 0 < j = 2: takas, dizi [1, 9, 5, 7, 3]. Sonra i, a[1] = 9'da; j, 9'u geçip a[0] = 1'de durur. i = 1 ≥ j = 0: çaprazlandı. Pivot a[1] ile takas edilir. Dizi [1, 3, 5, 7, 9], dönüş değeri 1'dir.

2. Hızlı sıralama (quicksort1) 8 öğelik sıralı bir dizide kaç bol çağrısı yapar? Özyineleme derinliği nedir?

Çözüm. Pivot her seferinde aralığın en büyüğüdür ve yerinde kalır. Boyları 8, 7, …, 2 olan aralıklar bölümlenir: 7 bol çağrısı. Her bölümleme bir öncekinin içinde yapıldığı için iç içe bekleyen ve bol çağıran çerçeve sayısı n − 1 = 7'dir. Karşılaştırma sayısı 9 + 8 + … + 3 = 42'dir.

3. Birleştirme sıralaması 16 öğe için kaç merge çağrısı yapar? En çok kaç karşılaştırma yapılır?

Çözüm. Çerçeve ağacının 16 yaprağı ve 16 − 1 = 15 iç düğümü vardır: 15 merge çağrısı. Bu nottaki merge her yerleştirmede tam bir karşılaştırma yapar. Ağacın lg 16 = 4 düzeyinin her birinde toplam 16 öğe birleştirilir: 4 × 16 = 64 karşılaştırma. Sayı girdiden bağımsızdır; sayaçlı çalıştırma da 64 vermiştir.

4. [4, 10, 3, 5, 1] (a[1..5]) için heap kurma sonrası dizi nedir?

Çözüm. ⌊5/2⌋ = 2'den başlanır. heapify(a, 2, 5): t = 10, çocuklar 5 ve 1; 10 ≥ 5, değişiklik yok. heapify(a, 1, 5): t = 4, çocuklar 10 ve 3; 10 yukarı çıkar. Boşluk 2'ye iner; çocuklar 5 ve 1, 4 < 5: 5 yukarı çıkar. Boşluk 4'e iner; çocuğu yoktur ve 4 oraya yazılır. Sonuç [10, 5, 3, 4, 1]'dir.

5. Basamak sıralaması 170, 45, 75, 90, 802, 24, 2, 66 listesinde birler geçişinden sonra hangi sırayı verir?

Çözüm. Birler basamakları sırasıyla 0, 5, 5, 0, 2, 4, 2, 6'dır. Kovalar: 0: 170, 090; 2: 802, 002; 4: 024; 5: 045, 075; 6: 066. Kararlı dağıtım ve toplama sonucu 170 090 802 002 024 045 075 066 verir. Sonraki iki geçiş 802 002 024 045 066 170 075 090 ve 002 024 045 066 075 090 170 802 listelerini üretir.

6. Heap sort neden kararlı değildir? Küçük bir örnek verin.

Çözüm. [2a, 2b, 1] dizisi zaten bir maksimum heap'tir. İlk turda kökteki 2a sona taşınır: [1, 2b, 2a]. heapify 2b'yi köke çıkarır, ikinci turda 2b ikinci konuma gider. Sonuç [1, 2b, 2a]'dır ve eşit anahtarların sırası değişmiştir. Heap sort öğeleri uzak konumlar arasında takas eder; bu uzak takaslar eşitlerin göreli sırasını korumaz.

20.13Özet

• Hızlı sıralama. bol pivotu kesin yerine koyar ve aralığı ikiye ayırır. En iyi n lg n, ortalama ≈ 1,39 n lg n, en kötü n² karşılaştırma; yerinde, kararsız. Pivot i'nin bekçisidir, j için j == L gerekir.
• Ortalama durum. Yineleme bağıntısı çıkarma hilesiyle C_n/(n + 1) = C_n−1/n + 2/(n + 1) biçimine getirilir ve harmonik sayılarla çözülür.
• İyileştirmeler. Büyük parça önce itilirse açık yığında en çok ⌊lg n⌋ + 1 ikili bekler. Medyan-3 sıralı girdideki n²'yi kaldırır; küçük parçalar eklemeliye bırakılır. Introsort en kötü durumu heap sort'la O(n lg n)'ye indirir.
• qsort. void * ve fonksiyon işaretçisiyle her türü sıralar; karşılaştırıcı tutarlı olmalı ve taşmamalıdır. Kararlılık güvencesi yoktur.
• Birleştirme sıralaması. Her durumda Θ(n lg n); 2n − 1 çağrı, n − 1 birleştirme, O(n) ek bellek. Bağlı sürüm tutanakları taşımaz, yalnız bag indislerini değiştirir.
• Heap sort. Heap kurma en çok 2^k − k − 1 ≤ 2n kaydırmayla O(n), sıralama O(n lg n); ek bellek O(1), kararsız.
• Basamak sıralaması. Kararlı kovalarla LSD'den MSD'ye O(d(n + r)); pozitif tamsayılar ve küçük aralık için, karşılaştırmasız.

20.14Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• parçala ve yönet divide and conquer
• hızlı sıralama quick sort
• bölümleme partition
• pivot pivot
• değişmez invariant
• bekçi sentinel
• yineleme bağıntısı recurrence relation
• alt sınır lower bound
• çerçeve stack frame
• yığın taşması stack overflow
• üçün ortancası median-of-three
• eklemeli sıralama insertion sort
• hibrit sıralama hybrid sort
• introsort introsort
• void işaretçi void pointer
• fonksiyon işaretçisi function pointer
• tutanak record
• kararlı stable (sort)
• yerinde sıralama in-place sort
• birleştirme sıralaması merge sort
• heap sort heap sort
• max-heap max-heap
• aşağıdan yukarıya heap oluşturma bottom-up heap construction
• tam ikili ağaç complete binary tree
• basamak sıralaması radix sort
• kova bucket
• sayarak sıralama counting sort
• anahtar key

20.15Kendini Dene

1. [2, 8, 7, 1, 3, 5, 6, 4] dizisinde bol(a, 0, 7) çağrılıyor. Dizi ne olur, hangi değer döner?

   Cevap

   Pivot 4. i 8'de, j 3'te durur: takas, [2, 3, 7, 1, 8, 5, 6, 4]. Sonra i 7'de, j 1'de durur: takas, [2, 3, 1, 7, 8, 5, 6, 4]. Ardından i 7'de (konum 3), j 1'de (konum 2) durur ve çaprazlanır. Pivot 3. konuma gelir: [2, 3, 1, 4, 8, 5, 6, 7], dönüş 3.

2. quicksort1 ters sıralı [6, 5, 4, 3, 2, 1] dizisinde kaç bol çağrısı yapar? Bu girdi neden de kötüdür?

   Cevap

   5 çağrı. Her pivot aralığın bir ucuna düşer ve her bölme yalnız bir öğe ayırır; derinlik n − 1, iş n² mertebesindedir.

3. Ortalama durum bağıntısından C₂ ve C₃'ü hesaplayın.

   Cevap

   C₂ = 3 + (2/2)(C₀ + C₁) = 3. C₃ = 4 + (2/3)(C₀ + C₁ + C₂) = 4 + 2 = 6. Kapalı biçim de n = 3 için 2 · 4 · H₄ − 32/3 = 50/3 − 32/3 = 6 verir.

4. quicksort2 1000 öğelik bir diziyi sıralarken yığında aynı anda en çok kaç (L, R) ikilisi bulunabilir? YMAX = 64 neden yeterlidir?

   Cevap

   ⌊lg 1000⌋ + 1 = 10 ikili, yani 20 int. Sınır n < 2³¹ için bile 2 · 31 = 62 int'tir ve 64'ü aşmaz. Bunun koşulu büyük parçanın önce itilmesidir.

5. a = [2, 9, 4, 5] iken merge(a, b, 0, 1, 3) çağrılıyor. Kopyalamadan sonra b nedir? Sonuçta a ne olur?

   Cevap

   Sol yarı olduğu gibi, sağ yarı ters kopyalanır: b = [2, 9, 5, 4]. Birleştirme 2, 4, 5, 9 sırasını verir: a = [2, 4, 5, 9].

6. Birleştirme sıralaması 8 öğe için kaç mergesort çağrısı, kaç merge ve kaç karşılaştırma yapar?

   Cevap

   2n − 1 = 15 çağrı, n − 1 = 7 birleştirme ve 8 · lg 8 = 24 karşılaştırma.

7. a[1..8] = [3, 1, 4, 1, 5, 9, 2, 6] dizisine aşağıdan yukarıya heap kurma uygulanıyor. Sonuç nedir?

   Cevap

   [9, 6, 4, 1, 5, 3, 2, 1]. heapify 4, 3, 2 ve 1 için çağrılır ve toplam 5 kaydırma yapılır.

8. Basamak sıralaması 512, 037, 208, 099 listesine uygulanıyor. Onlar geçişinden sonra liste nedir?

   Cevap

   Birler geçişi 512 037 208 099 verir (2, 7, 8, 9). Onlar geçişi 1, 3, 0, 9 basamaklarına göre 208 512 037 099 verir. Yüzler geçişinden sonra liste 037 099 208 512 olur.

9. int dizisini qsort ile büyükten küçüğe sıralayan, taşmayan bir karşılaştırma fonksiyonu nasıl yazılır?

   Cevap

   int azalan(const void *p, const void *q) { int x = *(const int *)p, y = *(const int *)q; return (y > x) - (y < x); }. artan'daki x ile y'nin yeri değiştirilmiştir. return y - x; yazılsaydı büyük farklarda taşma olurdu.

20.16İleri okuma

• R. Sedgewick, Algorithms in C, Kısım 1–4, Bölüm 7–10. Bu nottaki bol, quicksort2, medyan-3 ve bitonik merge kodlarının kaynağıdır; hızlı sıralamanın sürümlerini ölçümlerle karşılaştırır.
• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Bölüm 7. Bağlı birleştirme sıralamasını, adjust ile heap sort'u ve kovalı basamak sıralamasını bu nottaki örneklerle anlatır.
• T. H. Cormen ve diğerleri, Introduction to Algorithms, Bölüm 6–8. Heap sort, hızlı sıralamanın olasılıklı analizi ve doğrusal zamanlı sıralamalar için ayrıntılı kanıtlar verir.
• D. Musser, “Introspective Sorting and Selection Algorithms”, 1997. Introsort'un tanıtıldığı makaledir; medyan-3'ü n²'ye zorlayan girdileri de inceler.

20.17Kaynaklar

1. R. Sedgewick, Algorithms in C, Kısım 1–4, Bölüm 7–10 (quicksort, mergesort, priority queues ve heapsort, radix sorting).
2. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Bölüm 7.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, Bölüm 6–8.
4. D. Musser, “Introspective Sorting and Selection Algorithms”, 1997.
5. ISO/IEC 9899 (C standardı), qsort tanımı (§7.22.5.2).

İlgili sayfalar: Bölüm 20 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.