Bölüm 2: Sıralama Algoritmaları

2.1Sıralama problemi ve değerlendirme ölçütleri

Bir algoritmanın iyi olup olmadığını konuşabilmek için önce problemi kesin biçimde tanımlamak, sonra da “iyi” sözcüğünün neyi ölçtüğünü belirlemek gerekir. Bu kesim önce sıralama problemini tanımlar. Ardından bölümdeki algoritmaları kısaca tanıtır ve onları karşılaştırırken kullanılacak ölçütleri açıklar. Ölçütlerden biri, kararlılık, bölüm boyunca birkaç kez karşımıza çıkacağı için ayrıca ele alınır.

2.1.1Sıralama nedir?

Günlük hayatta sürekli veriyle karşılaşırız: alışveriş listeleri, banka hareketleri, sosyal medya gönderileri, sınav sonuçları. Bu verinin işe yaraması için çoğu zaman belirli bir düzende tutulması gerekir. Bir e-posta kutusu tarihe göre, bir sözlük alfabeye göre, bir sınav listesi puana göre dizilir. Sıralama (sorting), bir listedeki öğeleri belirli bir ölçüte göre düzene koymaktır. Ölçüt sayısal değer, alfabetik sıra ya da tarih olabilir; düzen de artan (küçükten büyüğe) ya da azalan olabilir. Bu notta aksi söylenmedikçe tam sayılar artan sırada sıralanır. Azalan sıralama, karşılaştırmanın yönünü çevirmekten ibarettir.

Tanımdaki iki koşulun ikisi de önemlidir. Çıktı sıralı olmalıdır, ama yalnız bu yetmez: çıktı girdinin bir permütasyonu olmalıdır. Yani hiçbir öğe kaybolmamalı, hiçbir öğe çoğalmamalı, yeni bir değer eklenmemelidir. Her öğeyi 0 yapan bir “algoritma” sıralı bir dizi üretir, ama permütasyon koşulunu çiğnediği için doğru değildir.

Gerçek uygulamalarda sıralanan şey çoğu zaman tek bir sayı değil, bir kayıttır: öğrenci numarası, adı ve bölümü olan bir satır gibi. Kaydın sıralamada kullanılan alanına anahtar (key) denir. Kaydın geri kalan alanları anahtarla birlikte taşınır. Bu bölümdeki örneklerde kayıt yalnız anahtardan oluşur; kararlılık konusunda ise anahtarın yanına bir etiket eklenir.

Sıralama neden bu kadar önemli? Çünkü sıralı veri üzerinde pek çok işlem çok kolaylaşır. Sıralı dizide bir değeri ikili arama ile O(log n) adımda bulmak mümkündür; sırasız dizide ise en kötü durumda bütün öğelere bakmak gerekir. Tekrar eden öğeler sıralı dizide yan yana durur; onları bulmak tek bir geçiş ister. İki sıralı liste tek geçişte birleştirilebilir. Ortanca, en küçük ya da en büyük k öğe doğrudan indisle okunur. Bu yüzden sıralama çoğu zaman tek başına bir amaç değil, başka bir algoritmanın ilk adımıdır.

2.1.2Algoritma çeşitleri

Sıralama problemini çözen çok sayıda algoritma vardır ve her biri farklı bir çalışma ilkesine dayanır. Tablo 2.1 bu bölümde incelenen algoritmaları temel fikirleriyle birlikte listeler. Tablodaki ilk dört algoritma basit ve karesel sürelidir. Sonraki üçü n log n düzeyinde çalışır. Saymalı ve basamak sıralaması öğeleri karşılaştırmaz. Timsort ise iki algoritmanın karmasıdır ve bugün Java ile Python kütüphanelerinde nesne sıralamasında kullanılır.

2.1.3Değerlendirme ölçütleri

Aynı problemi çözen iki algoritmadan hangisinin daha iyi olduğu, neye önem verildiğine bağlıdır. Sıralama algoritmaları için altı ölçüt öne çıkar.

Zaman. Bir sıralama algoritmasının süresi büyük ölçüde iki temel işlemin sayısıyla belirlenir: iki öğenin karşılaştırılması ve öğelerin taşınması. Taşıma, iki öğenin yerini değiştiren bir takas (swap) ya da bir öğeyi bir hücreden diğerine kopyalayan bir kaydırma olabilir. Bu sayılar girdi boyutu n'nin yanında girdinin kendisine de bağlıdır. Bu yüzden üç durum ayrı ayrı incelenir: en iyi durum, ortalama durum ve en kötü durum. Sonuçlar asimptotik gösterimle verilir: Θ(n²), Θ(n log n), Θ(n + k) gibi.

Ek bellek. Algoritmanın girdi dizisi dışında kullandığı bellek de önemlidir. Yalnız birkaç değişkenle, yani O(1) ek bellekle çalışan algoritmaya yerinde (in-place) sıralama denir. Yerinde algoritma, öğeleri girdi dizisinin içinde yer değiştirerek düzenler. Birleştirme sıralaması gibi bazı algoritmalar ise yardımcı diziler ister.

Kararlılık. Eşit anahtarlı öğelerin girdideki göreli sırası çıktıda da korunuyorsa algoritma kararlıdır (stable). Bu ölçüt bir sonraki alt kesimde örnekle açıklanır.

Karşılaştırmalı olup olmama. Bölümdeki algoritmaların çoğu öğeler hakkında yalnız “a ≤ b mi?” sorusunu sorar. Bu tür algoritmalara karşılaştırmalı sıralama denir. Böyle bir algoritma, en kötü durumda Ω(n log n) karşılaştırma yapmak zorundadır. Saymalı ve basamak sıralaması anahtarların değerini doğrudan dizi indisi olarak kullanır; bu yüzden bu sınırın dışında kalır.

Uyarlanabilirlik. Neredeyse sıralı bir girdiyi rastgele bir girdiden daha hızlı sıralayan algoritmaya uyarlanabilir (adaptive) denir. Eklemeli sıralama, bayraklı kabarcık sıralaması ve Timsort uyarlanabilirdir. Seçimli sıralama ise girdi ne olursa olsun aynı sayıda karşılaştırma yapar.

Çevrimiçi çalışma. Verinin tamamını baştan görmeden, öğeler geldikçe sıralayabilen algoritmaya çevrimiçi (online) denir. Eklemeli sıralama çevrimiçidir: o ana kadar gelen öğeler her an sıralıdır ve yeni gelen öğe doğru yere eklenir. Seçimli sıralama çevrimiçi değildir, çünkü en küçüğü bulmak için bütün öğeleri görmesi gerekir.

Bu ölçütler birbirinden bağımsızdır ve çoğu zaman biri için diğerinden ödün verilir. Birleştirme sıralaması hem hızlı hem kararlıdır ama ek bellek ister. Heap sort hızlı ve yerindedir ama kararsızdır. Hiçbir algoritma her ölçütte en iyi değildir; uygun algoritma uygulamanın neye ihtiyaç duyduğuna göre seçilir.

2.1.4Kararlılık

Kararlılık ancak kayıtların anahtar dışında da bir kimliği olduğunda anlam taşır. Yalnız tam sayılardan oluşan bir dizide iki 3'ü birbirinden ayırt etmek mümkün değildir; hangisinin önce geldiğinin bir önemi yoktur. Şekil 2.2 bu yüzden kayıtları (anahtar, etiket) çiftleri olarak gösterir. Sıralama yalnız sayıya göre yapılır; harf, kaydın kimliğidir.

Kararlılık en çok çok anahtarlı sıralamada işe yarar. Bir öğrenci listesi önce ada göre, sonra kararlı bir algoritmayla bölüme göre sıralanırsa, her bölümün içi alfabetik kalır. İkinci sıralama eşit bölümlü öğrencilerin sırasına dokunmadığı için, birinci sıralamanın kurduğu alfabetik düzen korunur. Kararsız bir algoritma ise bölüm içindeki alfabetik sırayı dağıtabilir. Aynı fikir basamak sıralamasının da temelidir: sayılar basamak basamak sıralanırken her ara adımın kararlı olması gerekir (2.9.6).

2.2Kabarcık sıralaması

Kabarcık sıralaması, bir diziyi sıralamanın akla gelen ilk yollarından biridir. Yalnız komşu iki öğeye bakar ve yanlış sıradaysa yerlerini değiştirir. Pratikte yavaştır, ama iki önemli kavramı açıkça gösterir: turdan tura büyüyen sıralı bölge ve ters çift. Bu iki kavram eklemeli sıralamanın analizinde de kullanılır.

2.2.1Fikir

Kabarcık sıralaması (bubble sort) diziyi soldan sağa tarar ve her adımda komşu iki öğeyi karşılaştırır. Soldaki öğe sağdakinden büyükse ikisinin yeri değiştirilir. Böylece büyük bir öğe, karşılaştırmalar boyunca sağa doğru taşınır; suyun içinde yükselen bir kabarcık gibi. Algoritma adını bu benzetmeden alır.

Dizinin baştan sona bir kez taranmasına tur denir. Bir turun sonunda o ana kadar sıralanmamış kısmın en büyük öğesi, dizinin sonundaki doğru yerine ulaşır. Nedeni basittir: en büyük öğeye gelindiğinde ondan büyük bir komşu yoktur, bu yüzden her karşılaştırmada takas edilip bir sağa geçer ve turun sonuna kadar taşınır. Birinci turdan sonra en büyük öğe, ikinci turdan sonra en büyük iki öğe yerindedir. Genel olarak i. tur bittiğinde en büyük i öğe son yerlerindedir. Bu yüzden her tur bir öncekinden bir öğe kısa olabilir.

Algoritmaya küçük bir iyileştirme eklemek mümkündür. Bir turda hiç takas yapılmadıysa bütün komşu çiftler doğru sıradadır; bu da dizinin sıralı olduğu anlamına gelir. Bu durumda kalan turlara gerek yoktur ve algoritma erken durabilir. Bu bilgi bir bayrak değişkeniyle tutulur. Bayraklı sürüm sıralı bir girdiyi tek turda tanır.

2.2.2Adım adım: [3, 1, 5, 2, 6, 4]

Algoritmayı altı öğeli [3, 1, 5, 2, 6, 4] dizisi üzerinde izleyelim. Tablo 2.2 her karşılaştırmayı, sonucunu ve takastan sonraki diziyi gösterir. Karşılaştırılan çift dizi[j] ile dizi[j+1]'dir.

Birinci turda beş karşılaştırma ve üç takas yapılır; tur sonunda 6 son yerine (indis 5) oturur. İkinci tur bir öğe kısadır: dört karşılaştırma, iki takas; 5 indis 4'e yerleşir. Üçüncü turda üç karşılaştırma yapılır ve hiçbirinde takas gerekmez. Bayrak false kaldığı için algoritma burada durur. Dördüncü ve beşinci turlara geçilmez. Toplam 12 karşılaştırma ve 5 takas yapılmıştır.

2.2.3Java kodu

Aşağıdaki kod, n uzunluklu dizi dizisini bayraklı kabarcık sıralamasıyla sıralar.

boolean yerDegistiMi;
for(int i = 0; i < n - 1; i++) {
  yerDegistiMi = false;
  for(int j = 0; j < n - 1 - i; j++) {
    if(dizi[j] > dizi[j+1]) {
      int gecici = dizi[j];
      dizi[j] = dizi[j+1];
      dizi[j+1] = gecici;
      yerDegistiMi = true;
    }
  }
  if(yerDegistiMi == false) break;
}

Kod satır satır şöyle çalışır:

• Dış döngü (i) turları sayar. En fazla n − 1 tur gerekir: n − 1 öğe yerine oturunca kalan tek öğe de kendiliğinden yerindedir.
• Her turun başında yerDegistiMi bayrağı false yapılır. Tur boyunca bir takas olursa true olur.
• İç döngü (j) sıralanmamış kısımdaki komşu çiftleri gezer. Sondaki i öğe önceki turlarda yerine oturduğu için koşul j < n - 1 - i'dir. j'nin son değeri n - 2 - i olur; bu durumda dizi[j+1] hâlâ sıralanmamış kısmın son hücresidir.
• dizi[j] > dizi[j+1] ise takas yapılır. Takas üç atamayla olur: soldaki değer gecici değişkeninde saklanır, sağdaki sola yazılır, saklanan değer sağa yazılır. gecici olmasaydı ilk atama soldaki değeri yok ederdi.
• Tur bittiğinde bayrak hâlâ false ise o turda hiç takas olmamıştır; break dış döngüden çıkar.

Koşulda > kullanıldığına, >= kullanılmadığına dikkat etmek gerekir. Eşit iki öğe hiçbir zaman yer değiştirmez; bu yüzden eşit anahtarlı öğelerin sırası korunur ve kabarcık sıralaması kararlıdır. Algoritma yalnız gecici, i, j ve bayrak için yer kullanır: ek bellek O(1)'dir, sıralama yerindedir.

2.2.4Kod izleme: [5, 1, 9, 2, 10]

Kodu bu kez beş öğeli [5, 1, 9, 2, 10] dizisiyle çalıştıralım. n = 5 olduğu için dış döngü en çok dört tur döner. Tablo 2.3 değişkenlerin her adımdaki değerini verir.

İlk turda (i = 0) iç döngü j = 0'dan 3'e kadar döner; dört karşılaştırmadan ikisinde takas yapılır ve tur sonunda 10 yerine oturur. İkinci turda (i = 1) iç döngü j < 3 koşuluyla üç kez döner; 5 ile 2 yer değiştirir ve 9 yerine oturur. Üçüncü turda (i = 2) iki karşılaştırmanın ikisi de “hayır” çıkar. Bayrak false kaldığı için break çalışır ve dördüncü tur hiç başlamaz. Sonuç [1, 2, 5, 9, 10]'dur; toplam 9 karşılaştırma ve 3 takas yapılmıştır.

İzlemede ilginç bir ayrıntı vardır: ikinci turun sonunda dizi aslında sıralıdır, ama algoritma bunu bilemez. Sıralı olduğunu ancak takassız bir tur tamamlandığında anlar. Bu yüzden bayraklı kabarcık sıralaması, dizi sıralandıktan sonra her zaman bir tur daha yapar.

2.2.5Analiz ve ters çiftler

Kabarcık sıralamasının maliyetini anlamak için önce dizinin ne kadar “sırasız” olduğunu ölçen bir kavram tanımlayalım.

Sıralı bir dizide hiç ters çift yoktur. Ters sıralı n öğeli dizide ise her çift ters çifttir; çift sayısı n(n − 1)/2 olduğu için ters çift sayısı da budur. Diğer diziler bu iki uç arasında yer alır.

Teoremden en kötü durum doğrudan çıkar. Ters sıralı dizide n(n − 1)/2 ters çift vardır; bu kadar takas gerekir. Karşılaştırma sayısı da aynıdır. Hiçbir tur erken bitmez ve turlar (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 karşılaştırma yapar. En iyi durumda girdi sıralıdır: bayraklı sürüm ilk turda n − 1 karşılaştırma yapar, hiç takas yapmaz ve durur. Rastgele bir permütasyonda her çiftin ters olma olasılığı 1/2'dir; beklenen ters çift sayısı, dolayısıyla beklenen takas sayısı n(n − 1)/4 ≈ n²/4'tür. Karşılaştırma sayısı ise ortalamada n²/2'ye yakındır, çünkü dizi çoğu zaman son turlara kadar sıralanmaz.

Kabarcık sıralamasının artıları azdır ama gerçektir: anlaşılması ve yazılması çok kolaydır, yerinde ve kararlıdır, bayrakla sıralı girdiyi Θ(n)'de tanır. Eksileri ise ağır basar. Karesel süre büyük dizilerde kabul edilemez. Her ters çift için ayrı bir takas yapar ve her takas üç atama ister. Aynı karşılaştırma ve ters çift sayısıyla çalışan eklemeli sıralama ise takas yerine kaydırma kullanır. Bu yüzden kabarcık sıralaması pratikte eklemeli sıralamadan hep yavaştır ve daha çok öğretim amacıyla kullanılır.

2.3Eklemeli sıralama

Eklemeli sıralama, küçük dizilerde ve neredeyse sıralı dizilerde bilinen en hızlı algoritmalardan biridir. Bu yüzden yalnız bir öğretim örneği değildir; Timsort gibi gerçek kütüphane algoritmalarının da bir parçasıdır.

2.3.1Fikir ve değişmez

Eklemeli sıralama (insertion sort), eldeki oyun kartlarını sıralamaya benzer. Kartlar tek tek alınır ve her yeni kart, eldeki sıralı kartların arasında doğru yere yerleştirilir. Eldeki kartlar her an sıralıdır; sıralı kısım her adımda bir kart büyür.

Dizide bu fikir şöyle uygulanır. Dizi iki parçaya ayrılır: solda sıralı kısım, sağda sırasız kısım. Başta sıralı kısım yalnız ilk öğeden oluşur; tek öğeli bir dizi zaten sıralıdır. Her adımda sırasız kısmın ilk öğesi alınır ve sıralı kısımdaki doğru konumuna yerleştirilir. Yer açmak için ondan büyük olan öğeler birer hücre sağa kaydırılır.

Algoritmanın doğruluğu bir döngü değişmezi (loop invariant) ile gösterilir. Değişmez, döngünün her turunun başında doğru olan bir önermedir. Eklemeli sıralamanın değişmezi şudur: dış döngünün her adımının başında dizi[0..i−1], başlangıçta bu indislerde bulunan öğelerin sıralı hâlidir. Başlangıçta i = 1'dir ve tek öğeli dizi[0..0] sıralıdır. Her adım dizi[i]'yi sıralı kısmın doğru yerine ekler; böylece dizi[0..i] sıralı olur ve değişmez bir sonraki adım için de doğru kalır. Döngü i = n olunca biter; değişmez bu anda dizi[0..n−1]'in, yani bütün dizinin sıralı olduğunu söyler.

2.3.2Adım adım: [3, 1, 5, 2, 6, 4]

Kabarcık sıralamasında kullanılan [3, 1, 5, 2, 6, 4] dizisini bu kez eklemeli sıralamayla sıralayalım. Yerleştirilecek öğe gecici adlı bir değişkende tutulur.

İlk adımda gecici = 1 alınır. Solundaki 3, 1'den büyüktür; 3 bir sağa kayar ve dizinin başına gelinir. 1, indis 0'a yazılır. İkinci adımda gecici = 5'tir; solundaki 3 ondan küçük olduğu için hiçbir öğe kaymaz ve 5 yerinde kalır. Üçüncü adım daha uzundur: gecici = 2 için önce 5, sonra 3 sağa kayar; 1 ≤ 2 olduğunda durulur ve 2, indis 1'e yazılır. Dördüncü adımda 6 yerinde kalır. Son adımda 4 için 6 ile 5 kayar ve 4, indis 3'e yerleşir. Toplam 5 kaydırma yapılmıştır; bu sayı dizinin ters çift sayısına eşittir.

Şekil 2.7'deki (a) anı önemli bir noktayı gösterir. Kaydırma bir kopyalamadır: dizi[j+1] = dizi[j] atamasından sonra aynı değer iki hücrede birden bulunur. Bu bir hata değildir; soldaki kopyanın üzerine bir sonraki adımda ya başka bir kaydırma ya da gecici yazılır. Yerleştirilecek öğenin asıl hücresi ise ilk kaydırmada ezilir. Bu yüzden değer, döngü başlamadan gecici'ye alınmalıdır.

2.3.3Java kodu

for(int i = 1; i < n; i++) {
  int gecici = dizi[i];
  int j = i - 1;
  while(j >= 0 && dizi[j] > gecici) {
    dizi[j+1] = dizi[j];
    j = j - 1;
  }
  dizi[j+1] = gecici;
}

• Dış döngü i = 1'den başlar, çünkü tek öğeli dizi[0..0] zaten sıralıdır.
• gecici, yerleştirilecek öğedir; bu değere anahtar da denir. Kaydırmalar onun hücresinin üzerine yazacağı için önce saklanır.
• j, sıralı kısmın son indisinden (i - 1) başlar ve sola doğru ilerler.
• while döngüsü, soldaki öğe gecici'den büyük olduğu sürece o öğeyi bir sağa kaydırır ve j'yi bir azaltır. Koşuldaki j >= 0 denetimi dizinin başını aşmayı önler. Java'da && kısa devre yapar: j = -1 olunca ikinci koşul hiç değerlendirilmez ve dizi[-1] okunmaz.
• Döngü bittiğinde ya j = -1'dir ya da dizi[j] <= gecici'dir. Her iki durumda da boşalan yer j + 1'dir ve gecici oraya yazılır.

Eklemeli sıralama takas değil kaydırma yapar. Bir takas üç atamadır; bir kaydırma ise tek atamadır. Bir öğeyi k hücre sola taşımak kabarcık sıralamasında k takas, yani 3k atama ister. Eklemeli sıralamada ise k kaydırma ve iki atama (gecici'ye alma ve yerine yazma), toplam k + 2 atama yeter. Eklemeli sıralamanın kabarcıktan belirgin biçimde hızlı olmasının nedeni budur.

Koşulda dizi[j] > gecici kullanılır, >= kullanılmaz. Eşit bir öğeye gelindiğinde durulur ve yeni öğe eşitin sağına yerleşir. Böylece eşit öğelerin girdideki sırası korunur ve eklemeli sıralama kararlıdır. Ek bellek yalnız gecici, i ve j'dir; algoritma yerindedir.

2.3.4Kod izleme: [5, 1, 9, 2, 10]

Kodu [5, 1, 9, 2, 10] dizisiyle çalıştıralım (n = 5). Tablo 2.6 her while denetimini ayrı bir satırda gösterir.

i = 1'de 5 sağa kayar ve j −1'e iner. Bu noktada j >= 0 yanlıştır ve döngü biter; 1, dizi[0]'a yazılır. i = 2'de solundaki 5 ≤ 9 olduğundan hiç kaydırma olmaz; 9 kendi hücresine yeniden yazılır. i = 3'te 9 ve 5 kayar, 1 ≤ 2'de durulur ve 2, dizi[1]'e girer. i = 4'te 10 yerinde kalır. i = 5 olunca dış döngü koşulu (5 < 5) yanlıştır ve algoritma biter. Toplam 6 karşılaştırma ve 3 kaydırma yapılmıştır. Dizideki ters çiftler (5,1), (5,2), (9,2)'dir; sayıları kaydırma sayısına eşittir.

2.3.5Analiz

Eklemeli sıralamada her kaydırma, yerleştirilen öğe ile ondan büyük bir öğenin oluşturduğu tek bir ters çifti düzeltir. Bu yüzden toplam kaydırma sayısı, kabarcık sıralamasındaki takas sayısı gibi, ters çift sayısı I'ya eşittir. Karşılaştırma sayısı ise en çok I + (n − 1)'dir. Her başarılı karşılaştırma bir kaydırma yaptırır. Ayrıca her öğe için döngüyü bitiren en fazla bir başarısız karşılaştırma vardır. Öğe dizinin başına kadar kayarsa bu son karşılaştırma yapılmaz, çünkü j >= 0 denetimi önce yanlış olur.

Bu teorem eklemeli sıralamanın uyarlanabilir olduğunu açıkça gösterir. Sıralı dizide I = 0'dır: her öğe için tek bir karşılaştırma yapılır, toplam n − 1, süre Θ(n)'dir. Ters sıralı dizide I = n(n − 1)/2'dir: her öğe dizinin başına kadar kayar ve süre Θ(n²) olur. Rastgele dizide beklenen I değeri n(n − 1)/4'tür; karşılaştırma ve kaydırma sayısı yaklaşık n²/4'tür. Bu, kabarcık sıralamasının ortalama karşılaştırma sayısının yaklaşık yarısıdır.

En iyi ve en kötü durumun büyüme hızları farklı olduğu için eklemeli sıralamanın süresi bütün girdiler için tek bir Θ ile yazılamaz. Doğru ifade şudur: süre bütün girdiler için O(n²) ve Ω(n)'dir; en kötü durum Θ(n²), en iyi durum Θ(n)'dir. “Üst sınır n², alt sınır n, o hâlde süre Θ(n log n)” gibi bir ara değer çıkarımı yanlıştır; sınırlar ayrı girdi aileleri için sıkıdır.

Eklemeli sıralamanın artıları uzun bir listedir: kararlıdır, yerindedir, çevrimiçidir, uyarlanabilirdir ve döngüsü çok sadedir. Küçük dizilerde (kabaca n ≲ 20–50) ek yükü az olduğu için n log n'lik algoritmalardan bile hızlıdır. Bu yüzden Timsort ve birçok kütüphane, hızlı sıralamada ve birleştirme sıralamasında küçük alt dizileri eklemeli sıralamaya bırakır. Eksiği ise rastgele büyük dizilerdeki karesel süredir. Bunun kökü, bir öğenin tek adımda yalnız bir hücre ilerleyebilmesidir: dizinin sonundaki küçük bir öğe başa ulaşmak için yaklaşık n kaydırma ister. Kabuk sıralaması tam bu sorunu çözmek için geliştirilmiştir (2.5).

2.4Seçimli sıralama

Seçimli sıralama, kabarcık ve eklemeli sıralamadan farklı bir ilkeye dayanır. Öğeleri azar azar kaydırmaz; her turda doğru öğeyi seçer ve onu tek bir takasla kesin yerine koyar. Bu yaklaşım takas sayısını en aza indirir, ama karşılaştırma sayısını girdiden bağımsız olarak hep yüksek tutar.

2.4.1Fikir

Seçimli sıralama (selection sort) da diziyi sıralı ve sırasız iki bölüme ayırır. Başta sıralı bölüm boştur. Her turda üç şey yapılır:

1. Sırasız bölümün en küçük öğesi bulunur.
2. Bu öğe, sırasız bölümün başındaki öğeyle yer değiştirir.
3. Takastan sonra o hücre sıralı bölüme katılır; sıralı bölüm bir öğe büyür.

Sıralı bölüme giren öğe artık kesin yerindedir. Ondan küçük bütün öğeler daha önceki turlarda solundaki hücrelere yerleşmiştir. Sağındakilerin hepsi de ondan büyük ya da ona eşittir. Bu yönüyle seçimli sıralama, eklemeli sıralamadan ayrılır. Eklemeli sıralamada sıralı kısım kendi içinde sıralıdır ama öğeler henüz son yerlerinde değildir; sonra gelen küçük bir öğe hepsini kaydırabilir. n öğeli dizide n − 1 tur yeter, çünkü son kalan öğe kendiliğinden en büyüktür. Her tur en fazla bir takas yapar.

2.4.2Adım adım: [3, 1, 5, 2, 6, 4]

Her turda sırasız bölümün ilk öğesi geçici en küçük kabul edilir; sonra kalan öğeler tek tek onunla karşılaştırılır. Daha küçük bir öğe bulunursa en küçük güncellenir.

Birinci turda geçici en küçük 3'tür. 1 < 3 olduğu için en küçük 1 olur; sonraki 5, 2, 6, 4'ün hiçbiri 1'den küçük değildir. Beş karşılaştırmadan sonra 1, baştaki 3 ile yer değiştirir. İkinci turda tarama 3'ten başlar ve 2'yi bulur; 2, sırasız bölümün başındaki 3 ile yer değiştirir. Dikkat edilirse 3 bu takasla indis 3'e, yani 5'in sağına gönderilmiştir; üçüncü turda yeniden seçilip indis 2'ye getirilir. Dördüncü turda 4, 5 ile; beşinci turda 5, 6 ile yer değiştirir. Beş tur sonunda son öğe 6 kendiliğinden yerindedir. Toplam 5 + 4 + 3 + 2 + 1 = 15 karşılaştırma ve 5 takas yapılmıştır.

2.4.3Java kodu

public void sirala(int[] dizi) {
  int n = dizi.length;
  for(int i = 0; i < n - 1; i++) {
    int enKucuk = i;
    for(int j = i + 1; j < n; j++) {
      if(dizi[j] < dizi[enKucuk]) {
        enKucuk = j;
      }
    }
    int gecici = dizi[enKucuk];
    dizi[enKucuk] = dizi[i];
    dizi[i] = gecici;
  }
}

• Dış döngü i = 0'dan n - 2'ye kadar döner; i, sırasız bölümün başıdır ve bu turda doldurulacak hücredir.
• enKucuk, o ana kadar bulunan en küçük öğenin indisini tutar, değerini değil. Takas için hangi hücreyle yer değiştirileceğini bilmek gerekir; değeri dizi[enKucuk] ile her an okunabilir.
• İç döngü j = i + 1'den dizinin sonuna kadar sırasız bölümün tamamını tarar. Girdi sıralı olsa bile bu tarama kısalmaz; en küçüğün gerçekten en küçük olduğunu doğrulamanın tek yolu bütün öğelere bakmaktır.
• dizi[j] < dizi[enKucuk] kesin küçükte en küçük güncellenir. Eşitlikte ilk bulunan korunur.
• İç döngüden sonra dizi[enKucuk] ile dizi[i] üç atamayla yer değiştirir. enKucuk == i ise öğe zaten yerindedir; kod yine de “kendisiyle takas” yapar, bu zararsızdır ama gereksiz üç atamadır.

Seçimli sıralama tur başına bir takas yapar, toplam en fazla n − 1. Bu sayı diğer basit algoritmaların takas sayısından çok daha azdır. Yazma işleminin pahalı olduğu ortamlarda, örneğin her yazmanın hücreyi yıprattığı flash bellekte, az sayıda takas seçimli sıralamanın tek gerçek avantajıdır.

2.4.4Kod izleme: [5, 1, 10, 2, 9]

Her turun başında enKucuk = i atanır. i = 0'da en küçük hemen j = 1'de bulunur ve sonraki üç karşılaştırma onu değiştirmez. j = 5 olunca iç döngü biter ve 1 ile 5 yer değiştirir. i = 1'de en küçük 2'dir (indis 3); i = 2'de 5'tir (yine indis 3); i = 3'te 9'dur (indis 4). i = 4 için dış döngü koşulu 4 < n − 1 yanlıştır ve algoritma biter. Toplam 4 + 3 + 2 + 1 = 10 karşılaştırma ve 4 takas yapılmıştır.

2.4.5Analiz ve kararsızlık

Seçimli sıralamanın karşılaştırma sayısı girdiye hiç bağlı değildir. i. turda iç döngü n − 1 − i kez döner; toplam

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

karşılaştırmadır. Sıralı, ters sıralı ya da rastgele, her girdide bu kadar karşılaştırma yapılır. Bu yüzden en iyi, ortalama ve en kötü durum aynıdır: Θ(n²). Seçimli sıralama uyarlanabilir değildir; sıralı bir diziye de n(n − 1)/2 karşılaştırma harcar.

Seçimli sıralama kararlı değildir. Nedeni, takasın yalnız iki öğeyi değil, aradaki bütün öğelerin üzerinden bir atlamayı içermesidir. Sırasız bölümün başındaki öğe, en küçüğün bulunduğu uzak bir hücreye gönderilir ve bu sırada kendisine eşit bir öğenin üzerinden atlayabilir. En küçük örnek üç öğelidir.

İkinci turda sırasız bölüm [2_b, 2_a]'dır; kod kesin küçükte güncelleme yaptığı için 2_b yerinde kalır ve takas olmaz. Sonuç sayısal olarak doğrudur, ama 2_a ile 2_b'nin göreli sırası tersine dönmüştür. Seçimli sıralamayı kararlı yapmak mümkündür: en küçük öğe takasla değil, aradaki öğeleri bir sağa kaydırarak başa getirilir. Ancak bu, takas sayısının az olması avantajını ortadan kaldırır ve maliyeti eklemeli sıralamaya yaklaştırır.

2.4.6Üç basit algoritma aynı girdide

Kabarcık, eklemeli ve seçimli sıralama aynı karesel sınıftadır, ama sabit çarpanları ve girdiye tepkileri farklıdır. Tablo 2.11 üç algoritmanın üç girdide yaptığı karşılaştırma ve taşıma (takas ya da kaydırma) sayılarını verir. Değerler bu bölümdeki kodlar çalıştırılarak sayılmıştır; n = 6'dır.

Tablodan üç gözlem çıkar. Birincisi, kabarcık ve eklemeli sıralamada taşıma sayısı ters çift sayısına eşittir: [3, 1, 5, 2, 6, 4] için 5, ters sıralı dizi için 6 · 5/2 = 15. Ama bir takas üç atama, bir kaydırma tek atamadır; aynı sayıdaki taşıma eklemelide çok daha ucuzdur. İkincisi, seçimli sıralama girdiden bağımsız olarak hep n(n − 1)/2 = 15 karşılaştırma yapar; buna karşılık en az takası o yapar. Ters sıralı dizide yalnız 3 takas yeter: 6 ↔ 1, 5 ↔ 2 ve 4 ↔ 3. İkişer öğe birbirinin yerine geçer ve ortadaki takaslar gereksiz kalır. Üçüncüsü, sıralı girdide bayraklı kabarcık ve eklemeli sıralama yalnız n − 1 = 5 karşılaştırma yapar; ikisi de uyarlanabilirdir.

Seçimli sıralamada sıralı girdi için takas sütununda 0 görünmesinin nedeni, sayımın yalnız enKucuk ≠ i olan gerçek takasları içermesidir. Kod yazıldığı biçimiyle her turda kendisiyle takas yapar; bunlar atama olarak sayılırsa sıralı girdide de n − 1 “takas” vardır.

2.5Kabuk sıralaması

Eklemeli sıralamanın zayıf noktası, bir öğenin her adımda yalnız bir hücre ilerleyebilmesidir. Kabuk sıralaması bu kısıtı kaldırır: öğeleri önce büyük adımlarla, sonra giderek küçülen adımlarla hareket ettirir. Son adımda yine sıradan eklemeli sıralama çalışır, ama bu kez dizi neredeyse sıralıdır.

2.5.1Fikir ve kod

Kabuk sıralaması (shell sort), 1959'da D. L. Shell'in önerdiği, eklemeli sıralamanın bir genellemesidir. Algoritma bir aralık (gap) değeriyle çalışır. Birbirinden aralık kadar uzaktaki öğeler aynı grubu oluşturur: aralık 4 ise indis 0, 4, 8, … bir grup; 1, 5, 9, … başka bir grup olur. Her grup kendi içinde eklemeli sıralamayla sıralanır. Bu sırada küçük bir öğe tek hamlede aralık kadar hücre atlar. Ardından aralık küçültülür ve aynı işlem tekrarlanır. Son turda aralık 1'dir; bu tur sıradan eklemeli sıralamadır.

Son tur zaten eklemeli sıralama olduğuna göre önceki turlar neden işe yarar? Çünkü önceki turlar, uzaktaki ters çiftlerin çoğunu ucuza giderir. Aralık 4 olan turda bir kaydırma bir öğeyi dört hücre taşır; aynı taşıma eklemeli sıralamada dört kaydırma isterdi. Aralık 1'e gelindiğinde dizide çok az ters çift kalır ve 2.3.5'teki teoreme göre eklemeli sıralama böyle bir diziyi hızla bitirir.

void kabukSirala(int[] dizi) {
  int n = dizi.length;
  for (int aralik = n / 2; aralik > 0; aralik /= 2)
    for (int i = aralik; i < n; i++) {
      int gecici = dizi[i], j;
      for (j = i; j >= aralik && dizi[j - aralik] > gecici; j -= aralik)
        dizi[j] = dizi[j - aralik];
      dizi[j] = gecici;
    }
}

• Dış döngü aralığı n / 2'den başlatır ve her turda yarıya indirir (aralik /= 2); aralık 0 olunca durur. Tam sayı bölmesi olduğu için aralık dizisi n = 8 için 4, 2, 1; n = 6 için 3, 1'dir.
• Orta döngü i = aralik'tan dizinin sonuna kadar gider. Her i, kendi grubunda eklenecek öğedir. Gruplar ayrı ayrı değil, iç içe işlenir: i bir artınca sıradaki öğe başka bir gruba aittir.
• İç döngü eklemeli sıralamanın while döngüsünün aynısıdır, yalnız adım 1 yerine aralik'tır. j, aralik'tan küçük olunca ya da soldaki grup öğesi gecici'den büyük olmayınca durur. Boşalan dizi[j] hücresine gecici yazılır.

Kabuk sıralaması yerindedir: yalnız birkaç değişken kullanır, ek bellek O(1)'dir. Ama kararlı değildir. Eşit iki öğe farklı gruplarda bulunabilir; büyük aralıklı bir turda biri diğerinin üzerinden atlayarak önüne geçebilir.

2.5.2Adım adım: [6, 5, 3, 1, 8, 7, 2, 4]

Sekiz öğeli dizide aralık dizisi 4, 2, 1'dir. Tablo 2.12 her aralıktan sonraki durumu verir.

Aralık 4'te dört grup vardır ve her biri iki öğelidir. Yalnız [3, 2] grubu sırasızdır; tek kaydırmayla [2, 3] olur. Aralık 2'de iki grup vardır: çift indisler [6, 2, 8, 3] ve tek indisler [5, 1, 7, 4]. Birinci grup eklemeli sıralamayla [2, 3, 6, 8] olur (2 için 6 kayar; 3 için 8 ve 6 kayar: 3 kaydırma). İkinci grup da 3 kaydırmayla [1, 4, 5, 7] olur. Gruplar dizideki yerlerine geri yazıldığında [2, 1, 3, 4, 6, 5, 8, 7] çıkar. Bu dizide yalnız üç ters çift kalmıştır: (2, 1), (6, 5), (8, 7). Aralık 1 turu, yani sıradan eklemeli sıralama, bu yüzden yalnız 3 kaydırma yapar. Toplam 10 kaydırma gerekmiştir; aynı dizi doğrudan eklemeli sıralamayla sıralansaydı ters çift sayısı kadar, yani 16 kaydırma gerekirdi.

2.5.3Kod izleme: [5, 2, 6, 1, 4, 3]

Kodun altı öğeli bir dizideki çalışması Tablo 2.13'te görülür. n = 6 olduğu için ilk aralık 3'tür; gruplar (0, 3), (1, 4) ve (2, 5) indis çiftleridir. Sonraki aralık 3/2 = 1'dir.

Aralık 3 turunda 1, tek hamlede indis 3'ten indis 0'a atlar; eklemeli sıralama bunun için üç kaydırma yapardı. Aynı biçimde 3, indis 5'ten indis 2'ye geçer. Bu turdan sonra dizi [1, 2, 3, 5, 4, 6] olur ve yalnız bir ters çift, (5, 4), kalır. Aralık 1 turu bunu tek kaydırmayla düzeltir. Aralık 1/2 = 0 olunca dış döngü biter. Toplam yalnız 3 kaydırma yapılmıştır. Aynı dizinin ters çift sayısı 9'dur; doğrudan eklemeli sıralama 9 kaydırma yapardı.

2.5.4Aralık dizisi ve karmaşıklık

Kabuk sıralamasının süresi, kullanılan aralık dizisine bağlıdır ve tam analizi zordur. Shell'in özgün dizisi n/2, n/4, …, 1'dir; bu notun kodu da onu kullanır. Bu dizinin en kötü durumu Θ(n²)'dir. Kötü durumun nedeni, n ikinin kuvveti olduğunda son tura kadar bütün aralıkların çift olmasıdır. Çift indisler ile tek indisler son tura kadar hiç karşılaştırılmaz. Örneğin büyük öğelerin hepsi çift, küçüklerin hepsi tek indislerdeyse ilk turlar onları karıştıramaz ve son tur karesel iş yapar.

Daha iyi aralık dizileri de vardır. T. N. Hibbard'ın 2^k − 1 dizisi (1, 3, 7, 15, …) ardışık aralıkları ortak çarpansız tutar ve en kötü durumu O(n^1,5)'e indirir. Başka diziler bunu daha da iyileştirir; pratikte orta büyüklükteki dizilerde kabuk sıralaması oldukça hızlıdır. En iyi durumda, yani sıralı girdide, her tur yaklaşık n karşılaştırma yapar ve log n tur vardır: süre Θ(n log n)'dir. Kabuk sıralamasının ortalama süresi için genel bir kapalı formül bilinmez; bu nedenle karşılaştırma tablolarında “aralığa bağlı” diye yazılır.

2.6Birleştirme sıralaması

Buraya kadar incelenen algoritmaların hepsi en kötü durumda karesel süreliydi. Birleştirme sıralaması bu sınırı aşan ilk algoritmadır: her girdide Θ(n log n) sürede çalışır. Bunu, problemi küçük parçalara bölen ve parçaların çözümlerini birleştiren bir tasarım yöntemiyle başarır.

2.6.1Böl ve fethet

Böl ve fethet (divide and conquer), bir problemi aynı türden daha küçük alt problemlere bölen, alt problemleri özyinelemeli olarak çözen ve sonuçları birleştiren bir algoritma tasarım yöntemidir. Her böl ve fethet algoritmasında üç adım vardır.

1. Böl (divide): Problem daha küçük alt problemlere ayrılır.
2. Fethet (conquer): Alt problemler aynı yöntemle, özyinelemeli olarak çözülür. Alt problem yeterince küçükse doğrudan çözülür; bu, özyinelemenin taban durumudur.
3. Birleştir (combine): Alt problemlerin çözümleri, asıl problemin çözümüne dönüştürülür.

Birleştirme sıralaması (merge sort) bu yöntemi sıralamaya uygular. Dizi ortadan iki yarıya bölünür. Her yarı aynı yöntemle sıralanır. Sonra sıralı iki yarı, sıralı tek bir dizide birleştirilir. Taban durumu tek öğeli dizidir; tek öğeli bir dizi tanım gereği sıralıdır. Algoritma 1945'te John von Neumann'a atfedilir.

Birleştirme sıralamasında bölme adımı neredeyse bedavadır: yalnız orta indis hesaplanır. Asıl iş birleştirme adımında yapılır. İki sıralı diziyi birleştirmenin fikri basittir. İki dizinin de en küçük öğesi kendi başındadır. Bu iki baş karşılaştırılır, küçük olan çıktıya yazılır ve o dizide bir sonraki öğeye geçilir. Dizilerden biri bitince öbüründe kalanlar sırayla çıktıya kopyalanır. Her karşılaştırma çıktıya bir öğe yazdırdığı için toplam m öğenin birleştirilmesi en fazla m − 1 karşılaştırma ve m yazma ister: süre Θ(m)'dir.

2.6.2Örnek: [38, 27, 43, 3, 9, 82, 10]

Yedi öğeli bir diziyi ele alalım. Orta indis ⌊(sol + sağ)/2⌋ ile hesaplandığı için tek sayılı parçalarda sol yarı bir öğe fazla alır: [38, 27, 43, 3] ve [9, 82, 10]. Şekil 2.13 bölmeleri ve birleştirmeleri birlikte gösterir.

Kod derinlik öncelikli çalıştığı için birleştirmeler şekildeki düzey sırasıyla değil, aşağıdaki sırayla yapılır. Sol yarı tamamen sıralanmadan sağ yarıya geçilmez.

birlestir toplam 6 kez çağrılır. Bu sayı her zaman n − 1'dir. Her birleştirme iki parçayı bire indirir; bu yüzden n tek öğeli parçadan tek bir diziye ulaşmak için n − 1 birleştirme gerekir. Karşılaştırma toplamı 1 + 1 + 3 + 1 + 2 + 6 = 14'tür.

2.6.3Özyinelemenin sırası

Özyinelemeli çağrıların hangi sırayla yürüdüğünü görmek için sekiz öğeli [6, 5, 3, 1, 8, 7, 2, 4] dizisini izleyelim. Dizi önce [6, 5, 3, 1] ve [8, 7, 2, 4] olarak bölünür. Sol yarı [6, 5] ve [3, 1]'e, [6, 5] de [6] ve [5]'e bölünür. İlk birleştirme burada olur: [6] + [5] → [5, 6]. Sonra [3, 1] bölünür ve [1, 3] olarak birleştirilir. [5, 6] ile [1, 3] birleşince sol yarı [1, 3, 5, 6] olarak sıralanmış olur. Ancak bundan sonra sağ yarıya geçilir: [8, 7] → [7, 8], [2, 4] → [2, 4], ikisi birleşince [2, 4, 7, 8]. Son birleştirme [1, 3, 5, 6] + [2, 4, 7, 8] → [1, 2, 3, 4, 5, 6, 7, 8]'dir.

Bu sıra, özyinelemeli çağrıların bir yığında (çağrı yığınında) tutulmasının doğal sonucudur. Herhangi bir anda yığında en çok ⌈log₂ n⌉ + 1 çağrı bulunur, çünkü her çağrı parça boyunu yarıya indirir. Sekiz öğe için yığın derinliği en çok 4'tür: boyu 8, 4, 2 ve 1 olan dört parça.

2.6.4Java kodu

Kod iki metottan oluşur. birlestirmeliSirala, dizi[sol..sag] aralığını sıralar; bütün dizi için ilk çağrı birlestirmeliSirala(dizi, 0, n - 1)'dir.

void birlestirmeliSirala(int[] dizi, int sol, int sag) {
  if (sol < sag) {
    int orta = sol + (sag - sol) / 2;
    birlestirmeliSirala(dizi, sol, orta);
    birlestirmeliSirala(dizi, orta + 1, sag);
    birlestir(dizi, sol, orta, sag);
  }
}

• sol < sag değilse aralıkta en çok bir öğe vardır ve metot hiçbir şey yapmadan döner; bu taban durumudur.
• Orta indis sol + (sag - sol) / 2 ile hesaplanır. Matematikte bu (sol + sag) / 2 ile aynıdır. Ama Java'da sol + sag toplamı çok büyük dizilerde int sınırını (2³¹ − 1) aşıp negatif bir sayıya dönüşebilir. İlk yazım bu taşmayı önler.
• Sol yarı [sol..orta], sağ yarı [orta+1..sag] özyinelemeli olarak sıralanır; sonra birlestir çağrılır.

birlestir, sıralı A[p..q] ve A[q+1..r] parçalarını A[p..r]'de birleştirir.

void birlestir(int[] A, int p, int q, int r) {
  int[] L = Arrays.copyOfRange(A, p, q + 1);
  int[] R = Arrays.copyOfRange(A, q + 1, r + 1);
  int i = 0, j = 0, k = p;
  while (i < L.length && j < R.length) {
    if (L[i] <= R[j]) A[k++] = L[i++];
    else              A[k++] = R[j++];
  }
  while (i < L.length) A[k++] = L[i++];
  while (j < R.length) A[k++] = R[j++];
}

• İki yarı önce Arrays.copyOfRange ile L ve R yardımcı dizilerine kopyalanır. Kopyalama gereklidir, çünkü sonuç doğrudan A'nın aynı hücrelerine yazılacaktır ve kopya olmasa henüz okunmamış öğelerin üzerine yazılırdı. copyOfRange'in üst sınırı dışlayıcıdır; bu yüzden q + 1 ve r + 1 yazılır.
• i ve j sırasıyla L ile R'nin sıradaki öğesini, k ise A'da yazılacak hücreyi gösterir.
• Birinci while, iki dizide de öğe kaldıkça başları karşılaştırır; küçük ya da eşit olanı A[k]'ya yazar ve ilgili indisi ilerletir. A[k++] = L[i++] ifadesi önce yazar, sonra iki indisi birer artırır.
• Dizilerden biri bitince kalan iki while'dan yalnız biri çalışır ve öbür dizide kalanları sırayla kopyalar. Kalan öğeler zaten sıralıdır ve yazılanların hepsinden büyük ya da onlara eşittir; karşılaştırmaya gerek yoktur.

Koşul L[i] <= R[j]'dir. Eşitlikte soldaki öğe önce alınır. Sol yarıdaki öğeler girdide sağ yarıdakilerden önce geldiği için eşit anahtarların göreli sırası korunur: birleştirme sıralaması kararlıdır.

2.6.5Kod izleme: birlestir()

[6, 5, 3, 1, 8, 7, 2, 4] örneğinin son adımında birlestir(A, 0, 3, 7) çağrılır. Bu anda A[0..3] = [1, 3, 5, 6] ve A[4..7] = [2, 4, 7, 8]'dir.

İlk altı adımda birer karşılaştırma yapılır ve sonuç dönüşümlü olarak iki diziden gelir. Altıncı adımdan sonra i = 4'tür; L bitmiştir ve birinci while sona erer. Kalan 7 ve 8 karşılaştırma yapılmadan kopyalanır. Toplam 6 karşılaştırma ve 8 yazma yapılmıştır. Sekiz öğeli bir birleştirme en fazla 7 karşılaştırma ister; bu sınır, iki dizi son öğelerine kadar birlikte tükendiğinde dolar. Örneğin L = [1, 3, 5, 7], R = [2, 4, 6, 8] için 7 karşılaştırma gerekir.

2.6.6Analiz

Birleştirme sıralamasının süresi bir özyineleme bağıntısıyla (recurrence) ifade edilir. n öğeli diziyi sıralamanın süresi T(n) olsun. Algoritma boyu n/2 olan iki alt problemi çözer ve sonuçları Θ(n) sürede birleştirir. Bölme sabit süredir. Buna göre

T(n) = 2 T(n/2) + Θ(n), T(1) = Θ(1)

bağıntısı yazılır.

Bu bağıntıyı çözmenin en sezgisel yolu özyineleme ağacıdır. Kökte boyu n olan bir problem vardır ve birleştirme işi n'dir. Bir alt düzeyde boyu n/2 olan iki problem vardır; her biri n/2 iş yapar, düzeyin toplamı yine n'dir. Bir alt düzeyde dört tane n/4 vardır; toplam yine n. Her düzeyde parça sayısı ikiye katlanır, parça boyu yarıya iner, toplam iş değişmez. Parça boyu 1'e inene kadar log₂ n düzey vardır. Toplam iş düzey başına n çarpı düzey sayısı, yani n log₂ n'dir.

Aynı sonuç ana teoremle (master theorem) de bulunur. Bağıntı T(n) = aT(n/b) + f(n) biçimindedir; burada a = 2, b = 2, f(n) = Θ(n)'dir. n^{log_b a} = n^{log₂ 2} = n olur ve f(n) = Θ(n^{log_b a}) eşitliği teoremin ikinci durumudur. Bu durumda T(n) = Θ(n^{log_b a} log n) = Θ(n log n)'dir.

Birleştirme sıralaması girdinin düzenine bakmaz; her durumda diziyi aynı biçimde böler ve aynı birleştirmeleri yapar. Bu yüzden en iyi, ortalama ve en kötü durum aynıdır: Θ(n log n). Karşılaştırma sayısı girdiye göre biraz değişir, çünkü bir dizi erken biterse kalanlar karşılaştırmasız kopyalanır; ama bu değişim büyüme hızını etkilemez.

Ek bellek açısından birleştirme sıralaması yerinde değildir. Birleştirme anında L ve R toplam n öğe tutar; ek bellek Θ(n)'dir. Buna özyineleme yığınının Θ(log n) çerçevesi eklenir. Büyük veri setlerinde bu ek bellek önemli bir maliyettir ve hızlı sıralamanın pratikte tercih edilmesinin nedenlerinden biridir.

Birleştirme sıralamasının bir yan ürünü de ters çift sayımıdır. Birleştirme sırasında R'den bir öğe alındığında, L'de kalan bütün öğeler ondan büyüktür ve her biri onunla bir ters çift oluşturur. Sayaca L.length − i eklenir. Sol ve sağ yarının kendi içindeki ters çiftler özyinelemeyle sayılır. Toplam iş birleştirme sıralamasıyla aynıdır: Θ(n log n). Bütün çiftleri tek tek denetleyen kaba kuvvet yöntemi ise Θ(n²) sürer. Örneğin [3, 1, 2, 5, 4] dizisinde ters çiftler (3, 1), (3, 2) ve (5, 4)'tür; sayıları 3'tür.

2.7Hızlı sıralama

Hızlı sıralama da böl ve fethet yöntemini kullanır, ama işin yerini değiştirir. Birleştirme sıralamasında bölme kolay, birleştirme zordur. Hızlı sıralamada ise bölme zordur ve birleştirmeye hiç gerek kalmaz. Ortalama durumda Θ(n log n)'dir, yerinde çalışır ve önbellek dostudur; bu yüzden pratikte en hızlı karşılaştırmalı sıralama genellikle odur.

2.7.1Fikir

Hızlı sıralama (quick sort) C. A. R. Hoare'un 1959'da geliştirdiği ve 1961–1962'de yayımladığı bir algoritmadır. Algoritma üç adımdan oluşur:

1. Diziden bir pivot öğe seçilir. Pivot x olsun.
2. Dizi pivot etrafında iki parçaya ayrılır: solda x'ten küçük ya da eşit öğeler, sağda x'ten büyük ya da eşit öğeler. Pivot ikisinin arasına yerleşir. Bu işleme parçalama (partitioning) denir.
3. İki parça özyinelemeli olarak sıralanır.

Parçalamanın önemli bir sonucu vardır: parçalamadan sonra pivot kesin yerindedir. Solundaki bütün öğeler ondan küçük ya da eşit, sağındakiler büyük ya da eşittir; sıralı dizide de tam o indiste duracaktır. İki parça sıralandığında öğeler parçaların sınırını hiç geçmez. Bu yüzden iki sıralı parçayı birleştirmek için ek bir iş gerekmez: dizi yerinde sıralanmış olur.

2.7.2Parçalama prosedürü

Parçalamanın birkaç yolu vardır. Bu notta N. Lomuto'nun adıyla anılan yöntem kullanılır. Pivot olarak aralığın son öğesi seçilir ve dizi tek geçişte taranır.

parcala(A, p, q):
  pivot = A[q]        // pivot seç
  i = p - 1           // ≤ pivot bölgesinin sonu
  for j = p to q - 1:
    if A[j] <= pivot:
      i = i + 1
      takas(A[i], A[j])
  takas(A[i + 1], A[q])  // pivotu yerleştir
  return i + 1          // pivotun indisi

Prosedür iki indisle çalışır. i, “pivottan küçük ya da eşit” bölgenin son hücresidir; başta bu bölge boş olduğu için i = p − 1'dir. j ise sıradaki incelenecek öğedir. Her adımda A[j] pivotla karşılaştırılır. Büyükse yalnız j ilerler; öğe “büyükler” bölgesine katılmış olur. Küçük ya da eşitse i bir artırılır ve A[i] ile A[j] takas edilir. Böylece öğe küçükler bölgesinin sonuna alınır; büyükler bölgesinin ilk öğesi de j'nin yerine geçer. Tarama bitince pivot, büyükler bölgesinin ilk hücresi olan A[i + 1] ile takas edilir ve onun indisi döndürülür.

Prosedürün doğruluğu şu döngü değişmezine dayanır: her adımın başında

• A[p..i]'deki öğeler pivottan küçük ya da eşittir,
• A[i+1..j−1]'deki öğeler pivottan büyüktür,
• A[j..q−1] henüz incelenmemiştir ve A[q] pivottur.

Başlangıçta ilk iki bölge boştur ve değişmez kendiliğinden doğrudur. Her adım, incelenen öğeyi doğru bölgeye ekleyerek değişmezi korur. Döngü bittiğinde incelenmemiş bölge boştur ve pivotun A[i+1]'e alınması diziyi istenen biçime getirir. Tarama tek geçiştir: n öğelik aralık için n − 1 karşılaştırma yapılır, süre Θ(n), ek bellek O(1)'dir.

Aynı fikir pivot ilk öğe seçilerek de uygulanabilir. Bu sürümde pivot A[p]'de kalır, tarama p + 1'den başlar ve sonda pivot küçükler bölgesinin son öğesiyle yer değiştirir.

PARCALA(A, p, q):
  x = A[p]            // pivot
  i = p
  for j = p + 1 to q:
    if A[j] <= x:
      i = i + 1
      takas(A[i], A[j])
  takas(A[p], A[i])
  return i

2.7.3Parçalama örneği: pivot ilk öğe

İlk öğeyi pivot alan sürümü [6, 10, 13, 5, 8, 3, 2, 11] dizisinde izleyelim. Pivot x = 6'dır; i = p = 0'dır ve j 1'den başlar.

Tarama boyunca dizinin başı üç bölgeye ayrılır: pivot, küçükler bölgesi ve büyükler bölgesi. İlk iki öğe (10 ve 13) büyüktür ve büyükler bölgesine katılır. 5 geldiğinde küçükler bölgesi bir büyür ve 5, büyükler bölgesinin ilk öğesi olan 10 ile yer değiştirir. 3 ve 2 için aynı şey olur. Tarama bittiğinde i = 3'tür. Pivot, küçükler bölgesinin son öğesi olan 2 ile yer değiştirir. Sonuçta pivot 6 indis 3'e oturur; solundaki 2, 5, 3 ondan küçük, sağındaki 8, 13, 10, 11 ondan büyüktür. Parçaların kendi içinde sıralı olmadığına dikkat edilmelidir; parçalama yalnız pivotu yerine koyar.

2.7.4Kod izleme: parcala()

Lomuto parçalamasının Java karşılığı aşağıdadır. takas(dizi, a, b), iki hücrenin değerini üç atamayla değiştiren yardımcı metottur.

int parcala(int[] dizi, int alt, int ust) {
  int pivot = dizi[ust];
  int i = alt - 1;
  for (int j = alt; j < ust; j++) {
    if (dizi[j] <= pivot) {
      i++;
      takas(dizi, i, j);
    }
  }
  takas(dizi, i + 1, ust);
  return i + 1;
}

Metodu parcala(dizi, 0, 7) çağrısıyla [2, 8, 7, 1, 3, 5, 6, 4] dizisinde izleyelim. Pivot dizi[7] = 4, başlangıçta i = −1'dir.

İlk öğe 2, pivottan küçüktür; i 0 olur ve öğe kendisiyle takas edilir. Bu işlem zararsızdır ama gereksiz bir takastır. 8 ve 7 büyüktür ve yalnız j ilerler. 1 geldiğinde i = 1 olur ve 1, büyükler bölgesinin ilk öğesi 8 ile yer değiştirir. 3 için de aynısı olur: 3 ile 7 yer değiştirir. 5 ve 6 büyüktür. Döngü j = ust'ta biter; pivot i + 1 = 3 indisine alınır ve 3 döndürülür. Sol parça [0..2]'deki öğeler 4'ten küçük, sağ parça [4..7]'deki öğeler 4'ten büyüktür. Toplam 7 karşılaştırma yapılmıştır; 8 öğelik aralık için n − 1 = 7.

2.7.5Özyinelemeli yapı

Parçalama hazır olduğunda hızlı sıralamanın kendisi birkaç satırdır. Sözde kod 1 tabanlı indislerle yazılmıştır:

HIZLI-SIRALA(A, p, r)
  if p < r
    q = PARCALA(A, p, r)
    HIZLI-SIRALA(A, p, q − 1)
    HIZLI-SIRALA(A, q + 1, r)

İlk çağrı: HIZLI-SIRALA(A, 1, n)

Java sürümü 0 tabanlıdır ve bütün dizi için ilk çağrı hizliSirala(dizi, 0, n - 1)'dir.

void hizliSirala(int[] dizi, int alt, int ust) {
  if (alt < ust) {
    int p = parcala(dizi, alt, ust);
    hizliSirala(dizi, alt, p - 1);
    hizliSirala(dizi, p + 1, ust);
  }
}

Kodda iki noktaya dikkat etmek gerekir. Birincisi, pivot iki özyinelemeli çağrının hiçbirine dahil edilmez; çağrılar p − 1'de biter ve p + 1'den başlar. Pivot yerine oturmuştur ve ona bir daha dokunulmaz. İkincisi, taban durumu alt < ust koşulunun yanlış olmasıdır: aralıkta sıfır ya da bir öğe vardır ve böyle bir aralık zaten sıralıdır. Pivot parçanın en küçüğü ya da en büyüğü olduğunda boş bir parça oluşur; örneğin hizliSirala(dizi, 0, -1). Bu çağrı hemen döner.

2.7.6Tüm çalışma: [6, 10, 13, 5, 8, 3, 2, 11]

Tablo 2.16 yalnız ilk parçalamayı gösteriyordu. Bütün sıralamayı, yine pivot ilk öğe olacak biçimde, özyinelemenin derinliğiyle birlikte izleyelim.

Tabloda boş aralıklar ([0..−1], [3..2] gibi) ayrı satır olarak yazılmamıştır; bu çağrılar hemen döner. Bütün çağrılar bittiğinde dizi [2, 3, 5, 6, 8, 10, 11, 13] olur. Birleştirme adımı yoktur: her pivot kendi parçalamasında yerine oturmuş, parçalar da yerinde sıralanmıştır. Sağ tarafta özyineleme dört düzey derinliğe iner, çünkü 8 ve 13 pivotları kendi parçalarının en küçüğü ve en büyüğüdür; her biri parçadan yalnız kendisini ayırır.

2.7.7Çağrı izleme: [5, 2, 8, 1, 9, 3]

Java kodunun (pivot son öğe) altı öğeli bir dizideki çağrıları aşağıdaki tabloda sırayla verilmiştir. Her satır bir hizliSirala çağrısıdır.

İlk çağrıda pivot 3'tür; 3'ten küçük 2 ve 1 sola toplanır, 5, 9, 8 sağda kalır ve pivot indis 2'ye oturur. Sonra sol parça (0, 1) sıralanır: pivot 1, solu boş, sağı [2]. Boş ve tek öğeli parçalar hemen döner. Sol taraf bitince ilk çağrının ikinci özyinelemeli satırı çalışır ve (3, 5) çağrılır: pivot 8, solunda [5], sağında [9]. Toplam 3 parcala çağrısı ve 4 taban çağrısı yapılmıştır; sonuç [1, 2, 3, 5, 8, 9]'dur.

2.7.8Analiz ve pivot seçimi

Hızlı sıralamanın süresi, pivotun diziyi ne kadar dengeli böldüğüne bağlıdır. Her parçalama, aralık boyuna göre doğrusal iş yapar. Bölmelerin dengesi ise özyineleme ağacının derinliğini belirler.

En iyi durum. Pivot her seferinde parçanın ortancasıysa dizi iki eşit yarıya bölünür. Bağıntı birleştirme sıralamasınınkiyle aynıdır: T(n) = 2T(n/2) + Θ(n), çözümü Θ(n log n).

En kötü durum. Pivot her seferinde parçanın en küçüğü ya da en büyüğüyse bir parça boş, öbürü n − 1 öğelidir. Bağıntı T(n) = T(n − 1) + Θ(n) olur. Açılınca n + (n − 1) + … + 1, yani Θ(n²) çıkar. Bu durum şaşırtıcı biçimde en “kolay” girdide ortaya çıkar: zaten sıralı bir dizide son öğeyi pivot alan sürüm her seferinde en büyüğü seçer. 1000 öğeli sıralı dizide karşılaştırma sayısı 999 + 998 + … + 1 = 499.500'dür ve özyineleme 1000 düzey derinliğe iner. Çok büyük dizilerde bu derinlik çağrı yığınını taşırır ve StackOverflowError verir.

Ortalama durum. Rastgele bir girdide pivot çoğu zaman “yeterince ortada” düşer. Pivotun hep 1'e 9 oranında böldüğü kötü görünen bir durumda bile özyineleme ağacının derinliği log_10/9 n'dir, yani yine logaritmiktir; toplam iş O(n log n) kalır. Ayrıntılı analiz, beklenen karşılaştırma sayısının büyük n için yaklaşık 2n ln n ≈ 1,39 n log₂ n olduğunu gösterir. Küçük n'de alt dereceli terimler de etkilidir. Lomuto parçalamasının kesin beklenen değeri 2(n + 1)H_n − 4n'dir (H_n, harmonik sayı) ve n = 1000 için yaklaşık 10.986 eder. Bu sayı birleştirme sıralamasının karşılaştırma sayısından yaklaşık %39 fazladır. Buna rağmen hızlı sıralama pratikte genellikle daha hızlıdır: iç döngüsü çok sadedir, yardımcı dizi kopyalamaz ve diziyi sırayla taradığı için işlemcinin önbelleğini iyi kullanır.

En kötü durumdan kaçınmak için pivot seçimi iyileştirilir.

• Rastgele pivot. Pivot aralıktan rastgele seçilir ve parçalamadan önce son hücreyle takas edilir. Böylece hiçbir sabit girdi algoritmayı kötü duruma düşüremez. Beklenen süre her girdide Θ(n log n)'dir. Kötü durum hâlâ mümkündür, ama yalnız şanssız rastgele seçimlerle ve olasılığı çok küçüktür.
• Üçün ortancası (median-of-three). İlk, orta ve son öğenin ortancası pivot olur. Sıralı ve ters sıralı girdide bu seçim tam ortayı verir ve en kötü durumu önler.
• Küçük parçalar. Parça boyu küçülünce (kabaca n ≲ 16) eklemeli sıralamaya geçmek pratikte hızlandırır. Ayrıca önce küçük parçaya inilip büyük parça döngüyle işlenirse özyineleme derinliği en kötü durumda bile O(log n)'de kalır.

Hızlı sıralama yerindedir: yalnız özyineleme yığını için ek bellek kullanır, ortalamada O(log n). Kararlı değildir; parçalamadaki uzun mesafeli takaslar eşit öğelerin sırasını bozabilir. Java'nın Arrays.sort(int[]) metodu ilkel tür dizilerinde hızlı sıralamanın iki pivot kullanan bir sürümünü (dual-pivot quicksort) kullanır. İlkel türlerde kararlılığın önemi yoktur, çünkü eşit iki int ayırt edilemez.

2.8Heap sort

Birleştirme sıralaması en kötü durumda da Θ(n log n)'dir ama ek bellek ister. Hızlı sıralama yerindedir ama en kötü durumu karesedir. Heap sort ikisinin iyi yanını birleştirir: en kötü durumda O(n log n) sürer ve O(1) ek bellekle yerinde çalışır. Bunu, dizinin kendisini bir veri yapısı olarak kullanarak başarır.

2.8.1Heap ve dizi gösterimi

Heap, her düzeyi soldan sağa dolu olan bir tam ikili ağaçtır ve bir sıralama koşulunu sağlar. Max-heap'te her düğüm çocuklarından büyük ya da onlara eşittir. Bu koşul ağacın her yerinde sağlandığı için en büyük öğe köktedir. Heap yapısı veri yapıları konusunda öncelik kuyruğu olarak tanınır; burada yalnız sıralamada nasıl kullanıldığı ele alınır.

Heap'in en kullanışlı özelliği, ağacın ayrı bir yapı olarak tutulmasına gerek olmamasıdır. Tam ikili ağaç bir dizide düzey düzey, soldan sağa saklanır. 0 tabanlı indislerle dizi[i]'nin sol çocuğu 2i + 1, sağ çocuğu 2i + 2, ebeveyni (i − 1) / 2 (tam sayı bölmesi) indisindedir. Böylece işaretçi kullanmadan, yalnız indis aritmetiğiyle ağaçta gezinmek mümkündür. Heap sort tam bu yüzden yerindedir: sıralanacak dizi aynı zamanda heap'in kendisidir.

Heap sort iki aşamada çalışır:

1. Dizi bir max-heap'e dönüştürülür.
2. Kök, yani en büyük öğe, heap'in son öğesiyle yer değiştirir. Bu öğe artık dizinin sonundaki sıralı bölgeye geçmiştir ve heap bir öğe küçülür. Köke gelen öğe heap koşulunu bozabileceği için aşağı doğru süzülür ve heap yeniden kurulur. Bu adım heap'te tek öğe kalana kadar tekrarlanır.

Her iki aşamanın temeli aynı işlemdir: bir düğümü aşağı süzmek. Düğüm çocuklarından küçükse büyük çocuğuyla yer değiştirir ve aynı denetim yeni konumunda tekrarlanır. Düğüm her iki çocuğundan büyük ya da eşit olduğunda ya da bir yaprağa ulaştığında süzme biter. Bu işlemin ön koşulu, düğümün iki alt ağacının zaten birer heap olmasıdır.

2.8.2Örnek: [4, 10, 3, 5, 1]

Algoritmanın bütününü küçük bir dizide görelim. Tablo 2.21 her adımda dizinin heap kısmını ve sıralı kısmını ayrı ayrı gösterir.

Heap kurma adımında yaprak olmayan düğümler aşağıdan yukarıya işlenir. İndis 1'deki 10 çocuklarından (5 ve 1) büyüktür; değişiklik olmaz. Kökteki 4, büyük çocuğu 10 ile yer değiştirir. Yeni konumunda (indis 1) çocukları 5 ve 1'dir; 4, 5 ile yer değiştirir ve yaprağa iner. Sonuç [10, 5, 3, 4, 1]'dir. Bundan sonraki her turda heap'in en büyüğü sona taşınır; sıralı bölge sağdan sola, büyükten küçüğe dolar.

2.8.3Birinci aşama: max-heap kurma

Sekiz öğeli [6, 5, 3, 1, 8, 7, 2, 4] dizisini ele alalım. Dizi tam ikili ağaç olarak düşünüldüğünde henüz heap değildir: örneğin kök 6, çocuğu 8'den küçüktür.

Heap'i kurmanın verimli yolu, aşağıdan yukarı çalışmaktır. Yapraklar (indis ⌊n/2⌋ ve sonrası, burada 4–7) tek öğeli birer heap'tir; onlarla bir şey yapmak gerekmez. İşleme son iç düğümden, yani indis n/2 − 1 = 3'ten başlanır ve köke doğru ilerlenir. Her düğüm aşağı süzülür. Bir düğüm işlendiğinde onun iki alt ağacı daha önce işlenmiş, yani zaten heap'tir; süzmenin ön koşulu bu yüzden her zaman sağlanır.

Kökteki 6, büyük çocuğu 8 ile yer değiştirdikten sonra indis 1'e iner. Orada çocukları 4 ve 5'tir; 6 ikisinden de büyük olduğu için süzme durur. Bütün iç düğümler işlendiğinde dizi [8, 6, 7, 4, 5, 3, 2, 1] olur. Bu bir max-heap'tir ve en büyük öğe 8 köktedir. Dikkat edilirse heap sıralı bir dizi değildir; yalnız her ebeveynin çocuklarından büyük olduğunu garanti eder.

2.8.4İkinci aşama: kökü sona taşıma

Max-heap [8, 6, 7, 4, 5, 3, 2, 1] hazırdır. Her turda kök, heap'in son öğesiyle yer değiştirir; heap bir küçülür ve köke gelen öğe aşağı süzülür.

Birinci turda 8 son hücreye (indis 7) geçer ve köke 1 gelir. 1'in çocukları 6 ve 7'dir; büyük olan 7 ile yer değiştirir ve indis 2'ye iner. Orada çocukları 3 ve 2'dir; 3 ile yer değiştirir ve yaprağa ulaşır. Heap [7, 6, 3, 4, 5, 1, 2] olur. Sonraki turlar aynı biçimde ilerler. Yedi tur sonunda heap'te tek öğe kalır; o da en küçük öğedir ve indis 0'da yerindedir. Sıralı dizi [1, 2, 3, 4, 5, 6, 7, 8]'dir.

2.8.5Java kodu ve analiz

void yiginSirala(int[] dizi) {
  int n = dizi.length;
  for (int i = n / 2 - 1; i >= 0; i--)   // 1) yığın kur
    yiginlastir(dizi, n, i);
  for (int i = n - 1; i > 0; i--) {      // 2) sırala
    takas(dizi, 0, i);                   // en büyüğü sona
    yiginlastir(dizi, i, 0);             // kökü süz
  }
}
void yiginlastir(int[] dizi, int n, int i) {
  int enBuyuk = i, sol = 2 * i + 1, sag = 2 * i + 2;
  if (sol < n && dizi[sol] > dizi[enBuyuk]) enBuyuk = sol;
  if (sag < n && dizi[sag] > dizi[enBuyuk]) enBuyuk = sag;
  if (enBuyuk != i) {
    takas(dizi, i, enBuyuk);
    yiginlastir(dizi, n, enBuyuk);
  }
}

• yiginSirala iki döngüden oluşur. Birinci döngü heap'i kurar: i, son iç düğüm n / 2 - 1'den köke kadar azalır ve her düğüm için yiginlastir(dizi, n, i) çağrılır.
• İkinci döngü sıralar: i, son indisten 1'e kadar azalır. Her turda kök dizi[i] ile takas edilir. Ardından yiginlastir(dizi, i, 0) çağrılır; ikinci argüman i, heap'in artık yalnız ilk i öğeden oluştuğunu söyler. Böylece sona taşınan öğeler süzmede yeniden kullanılmaz.
• yiginlastir, i düğümünü n boyutlu heap'te aşağı süzer. Önce i, sol ve sağ çocuk arasında en büyüğün indisi enBuyuk'ta bulunur. sol < n ve sag < n denetimleri çocuğun heap içinde olup olmadığını sorar.
• enBuyuk != i ise düğüm çocuklarından birinden küçüktür; ikisi takas edilir ve süzme çocuğun konumunda özyinelemeli olarak sürer. Eşitse düğüm yerindedir ve özyineleme biter.

Heap kurmanın maliyeti. Kurma döngüsü yaklaşık n/2 düğüm için süzme yapar ve tek bir süzme O(log n) sürer. Bu, kaba bir O(n log n) sınırı verir. Ama sınır gevşektir, çünkü düğümlerin çoğu alçaktadır. Yüksekliği h olan bir düğümün süzmesi en çok h adımdır. Yüksekliği h olan düğüm sayısı en çok ⌈n/2^h+1⌉'dir: yaprakların sayısı yaklaşık n/2, bir üst düzeyinki n/4'tür ve böyle devam eder. Toplam iş

Σ_{h ≥ 0} (n/2^h+1) · h = (n/2) · Σ_{h ≥ 0} h/2^h = (n/2) · 2 = n

mertebesindedir. Yani aşağıdan yukarı heap kurma O(n)'dir. Bu yönteme R. W. Floyd'un adıyla Floyd yöntemi de denir. Heap, öğeleri tek tek ekleyip her birini yukarı süzerek de kurulabilir; bu da geçerli bir max-heap verir, ama en kötü durumda O(n log n) sürer.

Sıralama aşamasının maliyeti. İkinci döngü n − 1 kez döner ve her turda kökü en çok heap yüksekliği kadar, yani O(log n) adım süzer. Bu aşama O(n log n)'dir ve toplam süreyi belirler. En kötü durumda bile süre O(n log n)'dir.

Bellek ve kararlılık. Heap sort yalnız birkaç değişken kullanır; O(1) ek bellekle yerinde çalışır. yiginlastir burada özyinelemeli yazılmıştır, ama özyineleme son satırdadır ve kolayca döngüye çevrilir; döngülü sürümde yığın da gerekmez. Heap sort kararlı değildir: kök ile son öğenin takası, eşit anahtarlı bir öğeyi diğerlerinin üzerinden atlatabilir. Uyarlanabilir de değildir; sıralı bir girdi bile önce heap'e dönüştürülür ve yine Θ(n log n) sürer.

2.8.6Kod izleme: heap kurma

Heap kurma döngüsünün [3, 9, 2, 1, 4, 5] dizisindeki çalışması satır satır şöyledir. n = 6'dır; yapraklar indis 3, 4 ve 5'tir. Döngü i = n/2 − 1 = 2'den başlar.

for (int i = n / 2 - 1; i >= 0; i--)
  yiginlastir(dizi, n, i);

void yiginlastir(int[] dizi, int n, int i) {
  int enBuyuk = i, sol = 2 * i + 1, sag = 2 * i + 2;
  if (sol < n && dizi[sol] > dizi[enBuyuk]) enBuyuk = sol;
  if (sag < n && dizi[sag] > dizi[enBuyuk]) enBuyuk = sag;
  if (enBuyuk != i) {
    takas(dizi, i, enBuyuk);
    yiginlastir(dizi, n, enBuyuk);
  }
}

i = 2'de 2'nin tek çocuğu 5'tir (indis 5); 5 daha büyük olduğu için yer değiştirirler ve süzme indis 5'te sürer. İndis 5 yapraktır; süzme biter. i = 1'de 9 çocuklarından (1 ve 4) büyüktür; değişiklik olmaz. i = 0'da 3, büyük çocuğu 9 ile yer değiştirir ve indis 1'e iner. Orada çocukları 1 ve 4'tür; 4 ile yer değiştirir ve yaprağa iner. Döngü i = −1'de biter. Sonuç [9, 4, 5, 1, 3, 2]'dir: her ebeveyn çocuklarından büyüktür ve en büyük öğe 9 köktedir.

sag denetiminin dizi[enBuyuk] ile yapıldığına dikkat etmek gerekir; dizi[i] ile değil. i = 0 adımında sağ çocuk 5, düğümün kendi değeri 3'ten büyüktür ama sol çocuk 9'dan küçüktür. Doğru seçim büyük çocuk 9'dur. Sağ çocuk dizi[i] ile karşılaştırılsaydı 5 seçilirdi; 5 köke çıkar, 9 onun altında kalırdı ve heap koşulu bozulurdu.

2.9Doğrusal zamanlı sıralama

Birleştirme sıralaması ve heap sort en kötü durumda Θ(n log n)'dir. Daha hızlı bir karşılaştırmalı algoritma bulmak mümkün müdür? Bu kesim cevabın “hayır” olduğunu kanıtlar. Ardından, öğeleri karşılaştırmak yerine anahtar değerlerini doğrudan kullanarak doğrusal sürede sıralayan üç algoritmayı anlatır.

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

Karşılaştırmalı bir algoritma, girdi hakkında bilgiyi yalnız “a_i ≤ a_j mi?” sorularının cevaplarından edinir. Böyle bir algoritmanın davranışı bir karar ağacı (decision tree) ile gösterilebilir. Ağacın her iç düğümü bir karşılaştırmadır; i:j etiketi a_i ile a_j'nin karşılaştırıldığını söyler. Sol dal “≤”, sağ dal “>” cevabını izler. Her yaprak, algoritmanın o cevap dizisi sonunda ürettiği sıralamadır. Girdi verildiğinde algoritma kökten bir yaprağa giden tek bir yolu izler. Yolun uzunluğu, o girdide yapılan karşılaştırma sayısıdır.

Teoremin iki önemli sonucu vardır. Birincisi, birleştirme sıralaması ve heap sort asimptotik olarak en iyi karşılaştırmalı algoritmalardır; en kötü durumları alt sınıra eşittir. İkincisi, daha hızlı sıralamak için karşılaştırma dışında bir bilgiye ihtiyaç vardır. Anahtarlar küçük tam sayılarsa değerlerin kendisi dizi indisi olarak kullanılabilir; saymalı ve basamak sıralaması bunu yapar.

2.9.2Saymalı sıralama

Saymalı sıralama (counting sort), anahtarları küçük bir aralıktaki tam sayılar olan öğeleri hiç karşılaştırmadan sıralar. Girdi A[1..n], her anahtar {1, 2, …, k} kümesindedir. Çıktı B[1..n] dizisine yazılır. Geçici olarak C[1..k] sayaç dizisi kullanılır.

Algoritmanın fikri şudur: anahtarı i'den küçük ya da eşit olan öğelerin sayısı biliniyorsa, anahtarı i olan son öğenin çıktıdaki konumu da bilinir. Örneğin anahtarı 3'ten küçük ya da eşit beş öğe varsa, son 3 çıktının beşinci hücresine yazılır. Algoritma dört döngüden oluşur:

for i = 1 to k
  C[i] = 0
for j = 1 to n
  C[A[j]] = C[A[j]] + 1   // C[i] = |{anahtar = i}|
for i = 2 to k
  C[i] = C[i] + C[i−1]    // C[i] = |{anahtar ≤ i}|
for j = n downto 1
  B[C[A[j]]] = A[j]
  C[A[j]] = C[A[j]] − 1

1. Birinci döngü bütün sayaçları sıfırlar.
2. İkinci döngü girdiyi tarar ve her anahtarın kaç kez geçtiğini sayar. Döngü sonunda C[i], anahtarı i olan öğe sayısıdır.
3. Üçüncü döngü önek toplamını hesaplar: her sayaca solundakini ekler. Döngü sonunda C[i], anahtarı i'den küçük ya da eşit olan öğe sayısıdır.
4. Dördüncü döngü girdiyi sondan başa tarar. Her öğe B[C[A[j]]] hücresine yazılır ve sayaç bir azaltılır; aynı anahtarlı bir sonraki öğe bir sol hücreye düşer.

2.9.3Adım adım: A = [4, 1, 3, 4, 3]

Girdi A = [4, 1, 3, 4, 3], n = 5, anahtarlar {1, …, 4}'tür (k = 4). Diziler 1 tabanlıdır.

Sayma döngüsünden sonra C = [1, 0, 2, 2]'dir: bir tane 1, hiç 2, iki tane 3, iki tane 4 vardır. Önek toplamından sonra C = [1, 1, 3, 5] olur. Bu değerler, her anahtarın çıktıdaki son konumudur: 1'in son konumu 1, 3'ün son konumu 3, 4'ün son konumu 5'tir. Son döngü girdiyi sağdan sola gezer. A[5] = 3, B[3]'e yazılır ve C[3] 2'ye iner; bir sonraki 3 (A[3]) bu yüzden B[2]'ye düşer. Sonuç B = [1, 3, 3, 4, 4]'tür. Hiç karşılaştırma yapılmamıştır.

Son döngünün sondan başa gezmesi kararlılığı sağlar. Eşit anahtarlı iki öğeden girdide sonra gelen önce işlenir ve daha sağdaki hücreye yazılır; önce gelen ise onun soluna düşer. Böylece eşitlerin girdideki sırası çıktıda korunur. Döngü baştan sona gezseydi eşitlerin sırası tersine dönerdi; sonuç yine sıralı olurdu ama algoritma kararsız olurdu.

2.9.4Karmaşıklık ve Java kodu

Toplam süre Θ(n + k)'dir. Anahtar aralığı k = O(n) ise süre Θ(n)'dir. Bu, karşılaştırma alt sınırıyla çelişmez; saymalı sıralama karşılaştırma yapmadığı için teoremin varsayımı ona uymaz. Ek bellek Θ(n + k)'dir: çıktı dizisi ve sayaç dizisi. k çok büyükse algoritma pratik değildir. Örneğin 32 bitlik tam sayılar için yaklaşık 4,3 milyar sayaç gerekir.

Java sürümü 0 tabanlıdır ve 0 … maks aralığını kullanır; maks, dizinin en büyük öğesidir.

int[] saymaliSirala(int[] dizi) {
  int maks = enBuyuk(dizi);
  int[] sayac = new int[maks + 1];
  for (int x : dizi) sayac[x]++;
  for (int i = 1; i <= maks; i++) sayac[i] += sayac[i - 1];
  int[] cikti = new int[dizi.length];
  for (int i = dizi.length - 1; i >= 0; i--) {
    cikti[sayac[dizi[i]] - 1] = dizi[i];
    sayac[dizi[i]]--;
  }
  return cikti;
}

Sözde koddan farklı olarak sayaçlar new int[maks + 1] ile otomatik olarak sıfırlanır. Önek toplamından sonra sayac[x], anahtarı x'ten küçük ya da eşit öğe sayısıdır; çıktı 0 tabanlı olduğu için x'in son konumu sayac[x] − 1'dir. Örneğin A = [2, 5, 3, 0, 2, 3, 0, 3] için adetler [2, 0, 2, 3, 0, 1], önek toplamları [2, 2, 4, 7, 7, 8]'dir; çıktı [0, 0, 2, 2, 3, 3, 3, 5] olur.

2.9.5Basamak sıralaması

Saymalı sıralama anahtar aralığı küçükken çok hızlıdır, ama aralık büyüyünce bellek ihtiyacı patlar. Basamak sıralaması (radix sort) bu sorunu, büyük sayıları basamak basamak sıralayarak çözer. Her basamak yalnız 0–9 değerini alır; bu yüzden her geçişte k = 10 olan bir saymalı sıralama yeter.

Burada anlatılan sürüm LSD (least significant digit) basamak sıralamasıdır: sıralama en anlamsız basamaktan, yani birler basamağından başlar; onlar, yüzler diye devam eder. Her geçişte o basamağa göre kararlı bir sıralama yapılır. Basamak sayısı d, taban b olsun. Her geçiş Θ(n + b) sürer ve d geçiş vardır; toplam süre Θ(d · (n + b))'dir. d ve b sabitse süre Θ(n)'dir. Ek bellek Θ(n + b)'dir; algoritma yerinde değildir.

int[] basamakSirala(int[] dizi) {
  int maks = enBuyuk(dizi);
  for (int us = 1; maks / us > 0; us *= 10)
    dizi = basamagaGoreSay(dizi, us);
  return dizi;
}
int[] basamagaGoreSay(int[] dizi, int us) {
  int n = dizi.length;
  int[] cikti = new int[n], sayac = new int[10];
  for (int x : dizi) sayac[(x / us) % 10]++;
  for (int i = 1; i < 10; i++) sayac[i] += sayac[i - 1];
  for (int i = n - 1; i >= 0; i--) {
    int b = (dizi[i] / us) % 10;
    cikti[--sayac[b]] = dizi[i];
  }
  return cikti;
}

• basamakSirala, us değişkenini 1, 10, 100, … diye büyütür. maks / us > 0 koşulu, en büyük sayının hâlâ işlenmemiş bir basamağı olduğu sürece doğrudur. 802 için us 1, 10 ve 100 değerlerini alır; 1000'de 802/1000 = 0 olur ve döngü biter.
• basamagaGoreSay, saymalı sıralamanın bir basamağa uyarlanmış hâlidir. Bir sayının o basamağı (x / us) % 10 ile bulunur: 802 için us = 10'da 802/10 = 80, 80 % 10 = 0.
• Son döngü yine sondan başa gezer ve kararlılığı sağlar. cikti[--sayac[b]] ifadesi önce sayacı bir azaltır, sonra azalmış değeri indis olarak kullanır; Java sürümündeki sayac[x] − 1 ile aynı işi tek ifadede yapar.

2.9.6Kararlılık neden gerekli?

LSD basamak sıralamasının doğruluğu şu değişmeze dayanır: k. geçişten sonra dizi, sayıların son k basamağına göre sıralıdır. Bir sonraki geçiş (k + 1). basamağa göre sıralar. Bu basamağı farklı olan iki sayı doğru sıraya girer. Bu basamağı aynı olan iki sayının sırasını ise önceki geçişler belirlemiştir ve o sıra son k basamağa göre doğrudur. Bu sıranın korunması, yani alt sıralamanın kararlı olması şarttır.

Şekildeki örnekte birinci geçişten sonra dizi [273, 123, 456, 276, 167, 467]'dir. İkinci geçişte 167 ile 467'nin onlar basamağı eşittir (6). Kararlı sıralama birinci geçişten gelen sırayı korur: 167 önce gelir. Bu sıra doğrudur, çünkü iki sayının birler basamağı da eşittir (7) ve girdideki sıra korunmuştur. Son geçişte 273 ile 276'nın yüzler basamağı eşittir (2). Alt sıralama kararsız olsaydı bu ikisi yer değiştirebilirdi ve sonuç [123, 167, 276, 273, …] gibi yanlış bir dizi olurdu. Sonuç [123, 167, 273, 276, 456, 467]'dir.

Basamak sıralaması en anlamlı basamaktan da başlayabilir; bu sürüme MSD (most significant digit) denir. MSD sürümü sayıları önce ilk basamağa göre kovalara ayırır ve her kovayı ayrı ayrı, özyinelemeli olarak sıralar. Dizgi sıralamasında yaygın kullanılır. LSD sürümü ise daha sadedir ama bütün anahtarların aynı uzunlukta olmasını ister.

2.9.7Kod izleme: basamagaGoreSay()

int[] basamagaGoreSay(int[] dizi, int us) {
  int n = dizi.length;
  int[] cikti = new int[n], sayac = new int[10];
  for (int x : dizi) sayac[(x / us) % 10]++;
  for (int i = 1; i < 10; i++) sayac[i] += sayac[i - 1];
  for (int i = n - 1; i >= 0; i--) {
    int b = (dizi[i] / us) % 10;
    cikti[--sayac[b]] = dizi[i];
  }
  return cikti;
}

basamagaGoreSay(dizi, 1) çağrısını [32, 15, 41, 23, 11] dizisinde izleyelim. Birler basamakları sırasıyla 2, 5, 1, 3, 1'dir.

Önek toplamından sonra sayac[b], basamağı b'den küçük ya da eşit olan öğe sayısıdır; örneğin sayac[3] = 4'tür. Bu sayı, o basamaklı son öğenin cikti'daki konumunun bir fazlasıdır. Sağdan sola gezerken 11 önce işlenir ve cikti[1]'e yazılır. 41 ile 11'in birler basamağı aynıdır; 41 sonra işlenir ve cikti[0]'a, yani 11'in soluna düşer. Girdide de 41, 11'den önceydi: sıra korunmuştur. Sonuç [41, 11, 32, 23, 15]'tir ve birler basamağına göre sıralıdır. Sonraki geçiş (us = 10) onlar basamağına bakar ve [11, 15, 23, 32, 41] dizisini üretir. 11 ile 15'in onlar basamağı eşittir; birinci geçişin kurduğu sıra (11 önce) korunur.

2.9.8Kova sıralaması

Kova sıralaması (bucket sort), girdinin dağılımı hakkında bir varsayım yaparak doğrusal beklenen süreye ulaşır. Girdinin [0, 1) aralığına düzgün dağılmış gerçel sayılardan oluştuğunu varsayalım. Algoritma n kova açar ve x değerini ⌊n · x⌋ numaralı kovaya atar. Her kova, örneğin eklemeli sıralamayla, kendi içinde sıralanır. Sonra kovalar sırayla birleştirilir.

Şekildeki örnekte 2 numaralı kovaya üç sayı (.21, .23, .26), 1 ve 7 numaralı kovalara ikişer sayı düşer; 0, 4, 5 ve 8 numaralı kovalar boştur. Dağılım düzgünse her kovaya ortalama bir öğe düşer ve kovaları sıralamak toplamda Θ(n) beklenen sürer. Dağıtma ve birleştirme de doğrusaldır; beklenen toplam süre Θ(n)'dir. Ancak varsayım bozulursa, örneğin bütün öğeler tek bir kovaya düşerse, o kova eklemeli sıralamayla Θ(n²)'de sıralanır. Kova sıralaması, kovalar kararlı bir algoritmayla sıralanırsa kararlıdır ve Θ(n) ek bellek ister. Sıralama Algoritmaları simülatöründeki onuncu algoritma kova sıralamasıdır.

2.10Timsort

Kütüphanelerin kullandığı sıralama algoritmaları ders kitaplarındaki saf algoritmalardan biraz farklıdır. Gerçek veride sık görülen düzenlerden yararlanır ve birkaç algoritmayı bir arada kullanırlar. Timsort bunun en bilinen örneğidir.

2.10.1Karma bir algoritma

Timsort, Tim Peters'ın 2002'de Python için tasarladığı karma (hybrid) bir sıralama algoritmasıdır. Bugün Java'da nesne dizileri (Arrays.sort(Object[]), List.sort) ve Python'da sorted Timsort kullanır. Algoritmanın çıkış noktası şu gözlemdir: gerçek veri çoğu zaman tamamen rastgele değildir. İçinde zaten sıralı uzun parçalar bulunur. Bir tabloya sonradan eklenen birkaç kayıt, kısmen sıralı bir günlük dosyası ya da iki sıralı listenin art arda eklenmesi buna örnektir.

Timsort bu sıralı parçaları, yani run'ları kullanır. Önce dizi soldan sağa taranır ve doğal run'lar bulunur; azalan bir run ters çevrilip artana dönüştürülür. Çok kısa run'lar, belirli bir en küçük uzunluğa (minrun, pratikte 32 ile 64 arası) kadar eklemeli sıralamayla uzatılır. Eklemeli sıralama küçük ve neredeyse sıralı parçalarda çok hızlı olduğu için bu seçim yerindedir. Ardından run'lar birleştirme sıralamasının birleştirme adımıyla ikişer ikişer birleştirilir. Birleştirme sırasında bir run'dan art arda çok öğe alınıyorsa algoritma “dörtnala” (galloping) kipine geçer. Bu kipte sıradaki öğenin yeri üstel aramayla bulunur ve bir öbek öğe tek seferde kopyalanır.

Timsort kararlıdır, çünkü hem eklemeli sıralama hem birleştirme kararlıdır. En kötü durumda O(n log n)'dir. Girdi zaten sıralıysa tek bir run bulunur ve algoritma n − 1 karşılaştırmayla, yani Θ(n)'de biter. Birleştirme için en çok O(n) ek bellek kullanır. Nesne sıralamasında kararlılık önemli olduğu için Java ilkel türlerde hızlı sıralamayı, nesnelerde Timsort'u kullanır.

Aşağıdaki kod Timsort'un basitleştirilmiş bir sürümüdür: doğal run'ları aramaz, diziyi sabit uzunluklu parçalara böler. Parçaları eklemeliSirala(dizi, sol, sag) ile sıralar, sonra 2.6.4'teki birlestir metoduyla birleştirir.

static final int MIN_PARCA = 4;
void timSirala(int[] dizi) {
  int n = dizi.length;
  for (int i = 0; i < n; i += MIN_PARCA)            // 1) run'lar
    eklemeliSirala(dizi, i, Math.min(i + MIN_PARCA - 1, n - 1));
  for (int boyut = MIN_PARCA; boyut < n; boyut *= 2)  // 2) birleştir
    for (int sol = 0; sol < n; sol += 2 * boyut) {
      int orta = sol + boyut - 1;
      int sag = Math.min(sol + 2 * boyut - 1, n - 1);
      if (orta < sag) birlestir(dizi, sol, orta, sag);
    }
}

• Birinci döngü diziyi MIN_PARCA uzunluklu parçalara ayırır ve her birini eklemeli sıralamayla sıralar. Son parça daha kısa olabilir; Math.min(i + MIN_PARCA - 1, n - 1) dizinin dışına çıkılmasını önler.
• İkinci döngü birleştirmeleri aşağıdan yukarı yapar. boyut, birleştirilecek sıralı parçaların uzunluğudur ve her turda iki katına çıkar. Her turda yan yana iki parça [sol..orta] ve [orta+1..sag] birleştirilir.
• orta < sag değilse sağda birleşecek bir parça yoktur; tek kalan parça bu turda aynen bırakılır.

Bu döngülü yapı, birleştirme sıralamasının özyinelemesiz, “aşağıdan yukarı” (bottom-up) bir sürümüdür. Özyineleme yığını kullanmaz.

2.10.2Adım adım

Basitleştirilmiş Timsort'u MIN_PARCA = 4 ile [5, 21, 7, 23, 19, 10, 3, 12, 8, 1] dizisinde izleyelim (n = 10).

Dizi önce üç run'a ayrılır; son run iki öğelidir. Her run eklemeli sıralamayla sıralanır. boyut = 4 turunda ilk iki run birleşir. Üçüncü run'ın birleşeceği bir eşi yoktur, çünkü orta = 8 + 4 − 1 = 11 dizinin sonunu (sag = 9) aşar. boyut = 8 turunda sekiz öğeli parça ile iki öğeli parça birleşir ve dizi sıralanır. boyut = 16 ≥ n olduğunda döngü biter.

2.11Algoritmaların karşılaştırılması

Bölümdeki algoritmaları artık yan yana koymak mümkündür. Bu kesim önce asimptotik özellikleri bir tabloda toplar, sonra gerçek karşılaştırma sayılarını verir ve hangi durumda hangi algoritmanın seçileceğini tartışır.

2.11.1Karmaşıklık tablosu

Tablodaki iki ayrıntı açıklama ister. Heap sort'un en iyi durumu Θ değil O ile yazılmıştır: bütün anahtarlar eşitse hiçbir süzme ilerlemez ve algoritma doğrusal sürede biter. Farklı anahtarlarda ise en iyi durum da Θ(n log n)'dir. Hızlı sıralamanın ek belleği yalnız özyineleme yığınıdır; büyük parça döngüyle, küçük parça özyinelemeyle işlenirse yığın derinliği O(log n)'i aşmaz.

2.11.2Ölçüm: n = 1000

Asimptotik gösterim sabit çarpanları gizler. Gerçek davranışı görmek için bu bölümdeki kodlar n = 1000 öğeli üç tür girdiyle çalıştırılmış ve yapılan öğe karşılaştırmaları sayılmıştır. Rastgele dizi sabit bir tohumla üretilmiştir.

Tablo kuramın söylediklerini sayılarla doğrular. Seçimli sıralama üç girdide de tam n(n − 1)/2 = 499.500 karşılaştırma yapar. Kabarcık ve eklemeli sıralama sıralı girdide yalnız n − 1 = 999 karşılaştırmayla biter. Rastgele girdide eklemeli sıralamanın sayısı yaklaşık n²/4 = 250.000, kabarcığınki yaklaşık n²/2'dir. Birleştirme sıralaması her girdide n log₂ n'in altında kalır. Sıralı ve ters sıralı girdilerde birleştirilen dizilerden biri hep erken bittiği için yaklaşık yarısı kadar karşılaştırma yapar. Hızlı sıralama rastgele girdide birleştirmenin biraz üstündedir ve 2.7.8'deki kesin beklenen değere (yaklaşık 10.986) yakındır. Ama sıralı ve ters sıralı girdilerde son öğeyi pivot alan sürüm en kötü durumuna düşer ve seçimli sıralama kadar karşılaştırma yapar. Heap sort girdiden neredeyse bağımsızdır; uyarlanabilir olmadığı için sıralı girdide bile 17.583 karşılaştırma harcar.

Karşılaştırma sayısı tek ölçüt değildir. Hızlı sıralama, karşılaştırma sayısı birleştirmeden fazla olmasına rağmen pratikte genellikle daha hızlıdır. Nedeni, yardımcı dizilere kopyalama yapmaması ve belleği sırayla gezmesidir. Heap sort ise karşılaştırma sayısının yanında belleği atlayarak gezdiği için (indis i'den 2i + 1'e) önbelleği kötü kullanır ve çoğu zaman hızlı sıralamadan yavaştır.

2.11.3Hangi durumda hangi algoritma?

Küçük ya da neredeyse sıralı dizi

Eklemeli sıralama: ek yükü azdır, uyarlanabilir ve kararlıdır. Süresi Θ(n + I) olduğu için ters çift sayısı az olan büyük dizilerde de hızlıdır.

Genel amaçlı, hız öncelikli

Hızlı sıralama, rastgele pivot ya da üçün ortancasıyla. Önbellek dostudur ve yerindedir.

Kararlılık gerekli

Birleştirme sıralaması ya da Timsort. Kütüphanelerin nesne sıralaması bu yüzden Timsort'tur.

En kötü durum garantisi ve az bellek

Heap sort: O(n log n) ve O(1) ek bellek. Introsort adlı karma algoritma hızlı sıralamayla başlar; özyineleme çok derinleşirse heap sort'a geçer ve böylece en kötü durumu O(n log n)'de tutar.

Küçük tam sayı anahtarlar

Saymalı ya da basamak sıralaması: Θ(n + k) ve Θ(d(n + b)).

Bağlı liste ya da dış bellek

Birleştirme sıralaması. Rastgele erişim gerektirmez; öğeleri sırayla okuyup sırayla yazar. Belleğe sığmayan büyük bir dosya parça parça sıralanır ve parçalar birleştirilir. Bağlı liste de ek dizi olmadan, yalnız bağlar değiştirilerek birleştirilebilir.

Kabarcık ve seçimli sıralama çoğunlukla öğretim amaçlıdır. Seçimli sıralama yalnız yazmanın çok pahalı olduğu durumlarda anlam taşır, çünkü en fazla n − 1 takas yapar.

2.12Sık yapılan hatalar

Sıralama kodlarındaki hataların çoğu sınır indisleri, geçici değişkenler ve eşitlik koşulları çevresinde toplanır. Aşağıdaki liste bölüm boyunca anlatılan hataları bir arada verir.

Bu hataların ortak noktası, çoğunun küçük bir örnekle elle izlenince hemen görülmesidir. İyi deneme girdileri şunlardır: sınır hatası için en kısa diziler (bir ve iki öğeli), kararlılık hatası için eşit anahtarlı kayıtlar, hızlı sıralamanın kötü durumu için sıralı bir dizi.

2.13Özet

• Sıralama, bir dizinin öğelerini anahtara göre artan (ya da azalan) düzene koyan bir permütasyon bulmaktır. Algoritmalar zaman (en iyi, ortalama, en kötü), ek bellek, kararlılık, yerinde çalışma, uyarlanabilirlik ve çevrimiçi olma ölçütleriyle karşılaştırılır.
• Kararlı algoritma eşit anahtarlı kayıtların göreli sırasını korur; çok anahtarlı sıralama ve basamak sıralaması buna dayanır. Kabarcık, eklemeli, birleştirme, saymalı, basamak ve Timsort kararlıdır; seçimli, kabuk, hızlı ve heap sort kararsızdır.
• Ters çift, birbirine göre yanlış sıradaki iki öğedir. Bir komşu takas tam bir ters çifti düzeltir; kabarcıkta takas sayısı ve eklemelide kaydırma sayısı ters çift sayısına eşittir. Ters sıralı dizide n(n − 1)/2 ters çift vardır.
• Kabarcık sıralaması komşuları takas eder; her turda kalanların en büyüğü sona gider. Bayraklı sürüm en iyi durumda Θ(n), aksi hâlde Θ(n²)'dir.
• Eklemeli sıralama anahtarı saklar, büyükleri kaydırır ve anahtarı yerleştirir. Süresi Θ(n + I)'dır; küçük ve neredeyse sıralı dizilerde en iyi seçenektir.
• Seçimli sıralama her turda en küçüğü başa alır: her girdide n(n − 1)/2 karşılaştırma, en çok n − 1 takas.
• Kabuk sıralaması azalan aralıklarla eklemeli sıralama yapar; süresi aralık dizisine bağlıdır (n/2 aralıkla en kötü Θ(n²), Hibbard dizisiyle O(n^1,5)).
• Birleştirme sıralaması böl, sırala, birleştir adımlarını izler: T(n) = 2T(n/2) + Θ(n) = Θ(n log n), her girdide. Θ(n) ek bellek ister ve kararlıdır.
• Hızlı sıralama pivot etrafında parçalar; pivot kesin yerine oturur ve birleştirme gerekmez. Ortalama Θ(n log n), en kötü Θ(n²); rastgele pivot ya da üçün ortancası kötü durumu önler.
• Heap sort diziyi O(n)'de max-heap'e çevirir, sonra n − 1 kez kökü sona alıp süzer: en kötü durumda O(n log n), O(1) ek bellek.
• Karşılaştırmalı her sıralama en kötü durumda Ω(n log n) karşılaştırma yapar (karar ağacının n! yaprağı). Saymalı sıralama Θ(n + k), basamak sıralaması Θ(d(n + b)), kova sıralaması düzgün dağılımda beklenen Θ(n) sürer; karşılaştırma yapmadıkları için bu sınıra bağlı değildirler.
• Timsort, sıralı run'ları eklemeli sıralamayla uzatıp birleştirme ile birleştiren kararlı bir karma algoritmadır; Java ve Python'un nesne sıralamasıdır.

2.14Kavram listesi

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

• sıralama sorting
• takas swap
• yerinde in-place
• kararlı stable (sort)
• uyarlanabilir adaptive (sort)
• ters çift inversion
• kabarcık sıralaması bubble sort
• eklemeli sıralama insertion sort
• seçimli sıralama selection sort
• kabuk sıralaması shell sort
• böl ve fethet divide and conquer
• birleştirme merge
• birleştirme sıralaması merge sort
• özyineleme bağıntısı recurrence (relation)
• özyineleme ağacı recursion tree
• ana teorem master theorem
• hızlı sıralama quick sort
• pivot pivot
• parçalama partition
• üçün ortancası median-of-three
• heap heap
• heap sort heap sort
• karşılaştırma alt sınırı comparison sort lower bound
• alt sınır lower bound
• saymalı sıralama counting sort
• basamak sıralaması radix sort
• LSD / MSD basamak sıralaması LSD / MSD radix sort
• kova sıralaması bucket sort
• Timsort Timsort
• karesel quadratic
• log-doğrusal linearithmic
• en iyi / ortalama / en kötü durum best / average / worst case

2.15Kendini Dene

1. Eklemeli sıralama [2, 4, 1, 3] dizisini sıralarken kaç karşılaştırma ve kaç kaydırma yapar?

   Cevap

   i = 1: 4 > 2 değil; 1 karşılaştırma, kaydırma yok. i = 2 (1): 4 ve 2 kayar, j = −1'de durulur; 2 karşılaştırma, 2 kaydırma. i = 3 (3): 4 kayar, 2 > 3 yanlış; 2 karşılaştırma, 1 kaydırma. Toplam 5 karşılaştırma ve 3 kaydırma. Ters çiftler (2, 1), (4, 1), (4, 3)'tür; sayıları kaydırma sayısına eşittir.

2. Bayraklı kabarcık sıralaması [2, 3, 4, 5, 1] dizisinde kaç tur, kaç karşılaştırma ve kaç takas yapar? Dizi neredeyse sıralı olmasına rağmen sonuç neden kötüdür?

   Cevap

   Her turda 1 yalnız bir hücre sola ilerler: [2, 3, 4, 1, 5], [2, 3, 1, 4, 5], [2, 1, 3, 4, 5], [1, 2, 3, 4, 5]. Dört turun hepsinde takas olduğu için bayrak hiç erken çıkış sağlamaz. 4 + 3 + 2 + 1 = 10 karşılaştırma ve 4 takas yapılır. Sondaki küçük öğe komşu takaslarla tur başına bir hücre ilerleyebildiği için kabarcık sıralaması bu girdide en kötü karşılaştırma sayısına ulaşır. Eklemeli sıralama aynı diziyi 3 + 4 = 7 karşılaştırmayla sıralar.

3. Kayıtlar (4, a), (2, b), (4, c), (1, d) olsun ve sıralama yalnız sayıya göre yapılsın. Seçimli sıralama bu girdide kararlılığı bozar mı?

   Cevap

   Bozar. Birinci turda en küçük (1, d), baştaki (4, a) ile takas edilir: (1, d), (2, b), (4, c), (4, a). İkinci turda (2, b) yerindedir. Üçüncü turda (4, a) kesin küçük olmadığı için takas olmaz. Sonuçta (4, c), (4, a)'nın önündedir; girdide ise a önceydi.

4. parcala(dizi, 0, 4) (Lomuto, pivot son öğe) [3, 7, 1, 6, 4] dizisinde çalışıyor. Metot ne döndürür ve dizi ne olur?

   Cevap

   Pivot 4, i = −1. j = 0: 3 ≤ 4, i = 0, kendisiyle takas. j = 1: 7 büyük. j = 2: 1 ≤ 4, i = 1, 7 ile 1 yer değiştirir: [3, 1, 7, 6, 4]. j = 3: 6 büyük. Son takas dizi[2] ↔ dizi[4]: [3, 1, 4, 6, 7]. Metot 2 döndürür; pivot 4 indis 2'de kesin yerindedir.

5. [1, 2, 3, 4, 5, 6, 7] dizisinden aşağıdan yukarı kurulan max-heap nedir?

   Cevap

   i = 2: 3, büyük çocuğu 7 ile yer değiştirir: [1, 2, 7, 4, 5, 6, 3]. i = 1: 2, büyük çocuğu 5 ile: [1, 5, 7, 4, 2, 6, 3]. i = 0: 1, büyük çocuğu 7 ile yer değiştirir ve indis 2'ye iner; orada çocukları 6 ve 3'tür, 6 ile yer değiştirir. Sonuç [7, 5, 6, 4, 2, 1, 3]'tür. Sıralı dizi bile heap kurmada epey takas ister; heap sort uyarlanabilir değildir.

6. Birleştirme sıralaması 16 öğeli bir diziyi en kötü durumda en fazla kaç karşılaştırmayla sıralar? Karşılaştırma alt sınırı kaçtır?

   Cevap

   Dört birleştirme düzeyi vardır: sekiz tane 2 öğeli, dört tane 4 öğeli, iki tane 8 öğeli ve bir tane 16 öğeli birleştirme. 8 · 1 + 4 · 3 + 2 · 7 + 1 · 15 = 49. Alt sınır ⌈log₂ 16!⌉ = ⌈44,25⌉ = 45'tir; birleştirme sıralaması bu sınıra yakındır.

7. Java'daki saymaliSirala metodu [1, 0, 2, 1, 0] dizisiyle çağrılıyor. Sayma döngüsünden ve önek toplamından sonra sayac dizisi nedir?

   Cevap

   maks = 2, sayaç üç hücrelidir. Adetler [2, 2, 1]'dir; önek toplamları [2, 4, 5] olur. Son döngü sağdan sola gezer ve çıktı [0, 0, 1, 1, 2] olur. Karşılaştırma yapılmaz; süre Θ(n + k)'dir.

8. [53, 21, 33, 12] dizisi LSD basamak sıralamasıyla sıralanıyor. Birinci geçişten sonra dizi nedir? 53 ile 33'ün sırası neden korunur?

   Cevap

   Birler basamakları 3, 1, 3, 2'dir; kararlı sıralama [21, 12, 53, 33] verir. 53 ile 33'ün birler basamağı eşittir ve girdide 53 önce geldiği için önce kalır. İkinci geçiş onlar basamağına göre [12, 21, 33, 53] dizisini üretir.

9. Bir milyon öğeli bir dizide yalnız on öğe yanlış yerdedir; her biri doğru yerinden en çok birkaç hücre uzaktadır. Kararlı ve hızlı bir sıralama için hangi algoritma seçilmelidir?

   Cevap

   Eklemeli sıralama ya da Timsort. Ters çift sayısı I çok küçüktür; eklemeli sıralamanın süresi Θ(n + I), yani doğrusal olur. Timsort da uzun sıralı run'ları bulup neredeyse doğrusal sürede biter. Birleştirme sıralaması yine Θ(n log n) harcar; seçimli sıralama Θ(n²)'dir.

2.16İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 2, 6, 7 ve 8: eklemeli ve birleştirme sıralamasını döngü değişmeziyle, heap sort'u, hızlı sıralamanın olasılıksal analizini ve doğrusal zamanlı sıralamayı kanıtlarıyla anlatır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Bölüm 2: aynı algoritmaları Java koduyla verir; karşılaştırma sayılarını deneylerle ölçen bölümleri bu nottaki ölçüm tablosunun genişletilmiş bir hâlidir.
• D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2. baskı, 1998), Bölüm 5.2: kabuk sıralamasının aralık dizilerini ve sıralama algoritmalarının tam karşılaştırma sayılarını en ayrıntılı biçimde inceler.
• T. Peters, “listsort.txt” (CPython kaynak kodu): Timsort'un run tespiti, minrun seçimi ve galloping kipini tasarımcısının kendi anlatımıyla açıklar.

2.17Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. E. D. Demaine, C. E. Leiserson, MIT 6.046J Introduction to Algorithms ders notları, 2005.
3. C. A. R. Hoare, “Quicksort”, The Computer Journal 5(1), 1962.
4. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2. baskı, Addison-Wesley, 1998.
5. T. Peters, “listsort.txt” (Timsort tasarım notu), CPython, 2002.
6. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.
7. D. L. Shell, “A High-Speed Sorting Procedure”, Communications of the ACM 2(7), 1959.

İlgili sayfalar: Bölüm 2 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.