Bölüm 19: Temel Sıralama Algoritmaları

19.1Sıralama kavramları

Telefon rehberindeki adlar, bir sınavın sonuç listesi, bir arama motorunun döndürdüğü sayfalar, bir mağazanın fiyata göre dizilmiş ürünleri: hepsi sıralanmış verilerdir. Sıralı veri iki büyük kolaylık sağlar. Birincisi arama hızlanır. Sıralı bir dizide ikili arama O(lg n) adımda sonuca ulaşır, sırasız dizide ise bütün öğelere bakmak gerekir. İkincisi pek çok soru sıralı veride kendiliğinden cevaplanır. En küçük ve en büyük değer dizinin iki ucundadır. Aynı değerler yan yana düşer, bu yüzden tekrarları bulmak tek bir geçiş ister. İki listenin ortak öğeleri, iki sıralı liste aynı anda gezilerek bulunur.

Sıralama algoritmaları algoritma analizinin de en iyi çalışma alanıdır. Problem kolay anlaşılır, çözümler kısadır, ama çözümlerin maliyetleri birbirinden çok farklıdır. Aynı bin sayıyı bir algoritma yarım milyon karşılaştırmayla, bir başkası on beş bin karşılaştırmayla sıralar. Bu notta önce ortak dil kurulur. Sonra üç temel algoritma ayrıntısıyla incelenir, ardından karşılaştırma yapmayan iki algoritma ve Shell sıralaması gelir. Not, karşılaştırmalı her sıralamanın uyması gereken alt sınırla biter.

19.1.1Tutanak, alan ve anahtar

Sıralanan şey çoğu zaman tek tek sayılar değildir. Bir öğrenci işleri programı öğrencinin numarasını, adını, soyadını ve not ortalamasını birlikte tutar. Bu bilgilerin her birine alan (field), bir öğrenciye ait alanların bütününe tutanak (record) denir. C'de bir tutanak doğal olarak bir struct ile gösterilir:

typedef struct {
    int    no;          /* anahtar */
    char   ad[20];
    char   soyad[20];
    double ort;
} ogrenci;

Tutanaklar bellekte tutuluyorsa topluluğa liste, bellek dışında, örneğin diskte tutuluyorsa kütük (file) denir. Sıralama her zaman alanlardan birine ya da birkaçına göre yapılır.

Şekil 19.1 üç öğrenci tutanağını gösterir. Öğrenci numarası anahtardır: iki öğrencinin adı ve soyadı aynı olabilir, numarası aynı olamaz. Ad, soyad ve ortalama veri alanlarıdır. Sıralama yalnız anahtarları karşılaştırır, ama tutanağın bütün alanları anahtarla birlikte yer değiştirir. Bu ayrım iki maliyet doğurur: anahtarları karşılaştırmanın maliyeti ve tutanakları taşımanın maliyeti. Tutanak büyükse ikincisi baskın çıkabilir.

Gerçek programlarda anahtar her zaman biricik olmak zorunda değildir. Öğrenciler not ortalamasına göre de sıralanabilir ve iki öğrencinin ortalaması aynı çıkabilir. Bu durumda “anahtar” sözcüğü sıralamanın dayandığı alan anlamında kullanılır. Eşit anahtarlı tutanakların sıralamadan sonra hangi sırada kalacağı ise kararlılık konusudur.

Sıralamalar verinin nerede durduğuna göre de ikiye ayrılır. İç sıralamada (internal sorting) verinin tamamı ana bellektedir ve herhangi bir öğeye sabit sürede erişilir. Dış sıralamada (external sorting) veri belleğe sığmaz; disk ya da teyp gibi yardımcı bellek kullanılır. Diskten bir blok okumak, bellekte binlerce karşılaştırma yapmaktan uzun sürer. Bu yüzden dış sıralamada maliyeti belirleyen, karşılaştırma sayısı değil disk erişim sayısıdır. Bu notun konusu iç sıralamadır. Yine de buradaki fikirler dış sıralamanın da temelidir: dış sıralama algoritmaları belleğe sığan parçaları iç sıralamayla sıralar, sonra sıralı parçaları birleştirir.

19.1.2Maliyeti neyle ölçeriz?

Bir sıralama algoritmasının süresini doğrudan saniyeyle ölçmek yanıltıcıdır, çünkü süre makineye, derleyiciye ve girdiye göre değişir. Bunun yerine algoritmanın yaptığı temel işlemler sayılır. Sıralamada iki temel işlem vardır:

• Karşılaştırma. İki anahtarın sırası sorulur: a[j] < a[min] gibi. Karşılaştırmaya dayanan algoritmalar girdi hakkında bilgiyi yalnız bu sorulardan edinir.
• Taşıma. Bir öğe dizide başka bir yere yazılır. Takas (swap) üç atamadan oluşur; eklemeli sıralamanın kaydırması ise tek bir atamadır. Notta “taşıma” sözcüğü ikisini birden anlatır; gerektiğinde hangisinin sayıldığı ayrıca belirtilir.

Bir algoritmanın çalışma süresi bu iki sayının toplamıyla orantılıdır. Hangisinin daha önemli olduğu veriye bağlıdır. Anahtarlar uzun karakter dizileriyse karşılaştırma pahalıdır. Tutanaklar büyükse taşıma pahalıdır. Flash bellekte her yazma hücreyi biraz yıprattığı için yazma sayısını azaltmak ayrıca değerlidir. Sayılar üç durum için verilir. En iyi durum algoritmanın en az iş yaptığı girdidir, en kötü durum en çok iş yaptığı girdidir. Ortalama durum, bütün olası girdilerin eşit olasılıkla geldiği varsayımıyla beklenen iştir. Ortalama durumun bu tanımı önemlidir ve eklemeli sıralamada ayrıntısıyla hesaplanır.

19.1.3Kararlılık

Şekil 19.2 tanımı küçük bir örnekle gösterir. Girdide beş tutanak vardır; sayı anahtardır, harf yalnız tutanakları birbirinden ayırmak için eklenmiştir. 3a ile 3c'nin anahtarı aynıdır ve girdide 3a önce gelir. Kararlı bir algoritma çıktıda da 3a'yı 3c'nin önüne koyar: 1b 1e 2d 3a 3c. Seçimli sıralama ise 1b 1e 2d 3c 3a üretir. Çıktı anahtarlara göre doğru sıralanmıştır, ama 3c öne geçmiştir. Seçimli sıralamanın bu sonucu nasıl ürettiği, algoritma tanıtılınca adım adım gösterilir.

Sayılar tek başına sıralanıyorsa kararlılığın bir önemi yoktur: iki 3'ü birbirinden ayırmanın yolu yoktur. Kararlılık, tutanakların anahtar dışında başka alanları olduğunda önem kazanır. En bilinen kullanım, birden çok alana göre sıralamadır.

Örnekteki sıra dikkat ister: önce ikincil alana (ad), sonra birincil alana (soyad) göre sıralanır. Son yapılan sıralama baskın gelir, öncekiler ise eşitlikleri bozmak için kalır. Basamak sıralaması (radix sort) aynı fikri sayıların basamaklarına uygular. Sayılar önce birler basamağına, sonra onlar basamağına, en son da en yüksek basamağa göre sıralanır; her geçişte kararlı bir algoritma kullanılır. Her geçişte kullanılan algoritmanın kararlı olması bu yüzden şarttır.

19.1.4Yerinde sıralama

Seçimli, eklemeli ve kabarcık sıralaması yerindedir: birkaç döngü değişkeni ve takas için tek bir geçici değişken dışında bellek istemezler. Sayarak sıralama yerinde değildir; çıktıyı ayrı bir b dizisine yazar ve sayaçlar için c dizisi kullanır. Kova sıralaması da kovalar ve düğümler için O(n) ek bellek ister. Bellek kıt olduğunda, örneğin gömülü bir denetleyicide, yerinde bir algoritma bu yüzden tek seçenek olabilir.

19.1.5Ortak altyapı: kucuk ve SWAP makroları

Bu nottaki karşılaştırmalı algoritmalar aynı iki yapı taşını kullanır: iki öğeyi karşılaştıran kucuk ve iki öğeyi takas eden SWAP. İkisi de C önişlemcisinin makrolarıdır. Makro (macro), derlemeden önce metin olarak yerine konan bir kısaltmadır; fonksiyon çağrısının maliyeti yoktur.

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

• Satır 1. N, deneme programının sıralayacağı öğe sayısıdır.
• Satır 2. kucuk(A, B), A < B ise 1, değilse 0 üretir. Parametrelerin ve bütün ifadenin parantez içine alınması bilinçlidir. Makro metin olarak açılır. Parantezsiz bir tanımda kucuk(x & 1, y) çağrısı x & 1 < y metnine dönüşürdü. C'de < işleci &'den önce uygulandığı için bu ifade x & (1 < y) olarak hesaplanırdı. Algoritmalar karşılaştırmayı bu makro üzerinden yaptığında, karşılaştırma ölçütünü değiştirmek tek satırlık bir iştir. Örneğin büyükten küçüğe sıralamak için tanımda < yerine > yazmak yeter.
• Satır 3. SWAP(A, B), A'nın değerini geçici t_ değişkenine alır, A'ya B'yi, B'ye eski A'yı yazar. Üç atama yapılır. Bu sürüm iki argümanlıdır ve öğe türü olarak int kullanır; başka türden öğeler için tanımdaki int değiştirilir.

Makronun gövdesinin do { … } while (0) içine alınması ilk bakışta tuhaf görünür. Döngü bir kez çalışır ve hiçbir şey yinelenmez. Amacı, makroyu sözdizimi bakımından tek bir deyim yapmaktır. Gövde yalnız süslü parantezlerle yazılsaydı ne olacağına bakalım:

#define SWAP(A, B) { int t = A; A = B; B = t; }

if (a[0] > a[1])
    SWAP(a[0], a[1]);
else
    puts("sirali");

Önişlemci SWAP(a[0], a[1]); satırını { int t = a[0]; a[0] = a[1]; a[1] = t; }; metnine çevirir. Bloktan sonraki noktalı virgül, boş bir deyimdir ve if deyimini sonlandırır. Ardından gelen else sahipsiz kalır ve derleyici hata verir. do { … } while (0) biçiminde ise sondaki noktalı virgül while (0)'ı kapatır; if–else yapısı bozulmaz. Bu kalıp, birden çok deyimden oluşan makrolar için C'de yerleşik bir alışkanlıktır.

Algoritmalarda iki makro çoğu zaman birlikte görünür: if (kucuk(A, B)) SWAP(A, B);. Bu satır A < B ise iki öğeyi takas eder. Kalıba karşılaştır-takas (compare-exchange) denir. Yönüne dikkat etmek gerekir: A dizide B'nin sağındaysa bu satır küçük öğeyi sola taşır. Kabarcık sıralamasındaki if (kucuk(a[j], a[j - 1])) SWAP(a[j], a[j - 1]); satırı tam böyledir: sağdaki a[j] soldakinden küçükse yer değiştirirler.

Algoritmaları sınamak için kullanılan ana program da kısadır:

int main(void) {
    int *a = malloc(N * sizeof *a);
    if (a == NULL) return 1;
    for (int i = 0; i < N; i++)
        a[i] = rand() % 50;
    selection(a, 0, N - 1);   /* sıralama yordamına çağrı */
    for (int i = 0; i < N; i++) printf("%d ", a[i]);
    free(a);
    return 0;
}

• Satır 2–3. N tamsayılık bir dizi heap bellekten alınır. sizeof *a, a'nın gösterdiği öğenin boyudur, yani sizeof(int). Bu yazım, dizinin türü değişirse kendiliğinden doğru kalır. malloc bellek bulamazsa NULL döndürür; program bu durumda 1 koduyla biter. Denetim yapılmasaydı a[i] yazımı NULL adresine yazmaya çalışırdı ve program çökerdi.
• Satır 4–5. Dizi 0 ile 49 arasında rastgele sayılarla doldurulur. rand() her çalıştırmada aynı diziyi üretir, çünkü tohum (srand) verilmemiştir. Bu durum sınamada bir kolaylıktır: hata bulunduğunda aynı girdi yeniden elde edilir.
• Satır 6. Sıralama yordamı çağrılır. Bütün yordamlar dizinin a[L..R] parçasını sıralar; bütün diziyi sıralamak için L = 0, R = N − 1 verilir. Bu arayüz, bir dizinin yalnız bir parçasını sıralamayı da mümkün kılar. Hızlı sıralama gibi algoritmalar küçük parçaları eklemeli sıralamaya bu arayüzle devreder.
• Satır 7–8. Sonuç yazılır ve bellek geri verilir. free unutulursa küçük bir programda bir şey olmaz. Aynı kod uzun çalışan bir programda tekrar tekrar çağrılırsa ise bellek sızıntısı birikir.

Program stdio.h ve stdlib.h başlıklarıyla derlenir. rand()'ın ürettiği sayılar C kütüphanesine göre değişir; bu notun denemesinde (zig cc, Windows) çıktı 0 5 8 11 12 14 17 19 24 27 28 31 34 41 45 oldu.

19.2Seçimli sıralama

19.2.1Fikir ve kod

Seçimli sıralama (selection sort), sıralamanın belki de en doğal yoludur. Masadaki bir deste sınav kâğıdını numara sırasına koyan biri önce en küçük numaralı kâğıdı arar ve en üste koyar. Sonra kalanlar arasında en küçüğü arar ve ikinci sıraya koyar. Bu iş kâğıt bitene kadar sürer. Algoritma üç cümleyle anlatılır:

1. Listedeki en küçük değerli öğe bulunur.
2. Bu öğe ilk konumdaki öğeyle yer değiştirir.
3. Aynı adımlar ikinci öğeden başlayarak kalan alt liste için yinelenir.

C ile gerçeklemesi:

void selection(int a[], int L, int R) {
    for (int i = L; i < R; i++) {
        int min = i;
        for (int j = i + 1; j <= R; j++)
            if (kucuk(a[j], a[min]))
                min = j;
        SWAP(a[i], a[min]);
    }
}

• Satır 2. Dış döngü, sıradaki en küçük öğenin yerleşeceği konumu i ile gezer. i, R'ye kadar değil R − 1'e kadar gider. n − 1 öğe yerine oturunca sonuncusu ister istemez doğru yerdedir: kalan tek öğe en büyük öğedir.
• Satır 3. min, şimdiye kadar görülen en küçük öğenin indisini tutar. Başlangıçta aday, kalan alt listenin ilk öğesi a[i]'dir.
• Satır 4–6. İç döngü kalan alt listenin geri kalanını, a[i+1..R]'yi tarar. Daha küçük bir öğe görülünce min onun indisine güncellenir. Karşılaştırma kucuk makrosuyla, yani katı “küçüktür” ile yapılır: eşit bir öğe min'i değiştirmez.
• Satır 7. En küçük öğe a[i] ile takas edilir. min == i ise takas öğeyi kendisiyle değiştirir; dizi değişmez, ama üç atama yine yapılır.

Algoritmanın doğruluğu bir döngü değişmeziyle (invariant) gösterilir. Değişmez, döngünün her turunun sonunda doğru kalan bir özelliktir.

Her dış tur sonunda a[L..i] sıralıdır ve dizinin en küçük i − L + 1 öğesini içerir.

İlk tur sonunda a[L]'de bütün dizinin en küçüğü vardır; tek öğeli bir parça sıralıdır. Bir tur başlarken değişmez i − 1 için doğruysa, tur kalan öğelerin en küçüğünü bulur ve a[i]'ye koyar. Bu öğe a[L..i−1]'deki her öğeden küçük değildir (onlar daha önce seçildi) ve kalanların hepsinden büyük değildir. Değişmez i için de doğru olur. Döngü i = R − 1 ile bittiğinde a[L..R−1] sıralıdır ve en küçük n − 1 öğeyi taşır; kalan a[R] en büyüktür. Dizi sıralanmıştır.

Seçimli sıralamanın belirgin bir özelliği, girdinin durumuna hiç bakmamasıdır. En küçüğü seçmek için kalan alt liste her turda sonuna kadar taranmalıdır. Dizi baştan sıralı olsa bile algoritma bunu fark etmez, çünkü “daha küçük bir öğe kalmadı” bilgisini ancak taramayı bitirince edinir.

19.2.2Adım adım izleme

selection(a, 0, 4) çağrısı a = [29, 10, 14, 37, 13] dizisi üzerinde izlenir. Tablo 19.1 her karşılaştırmayı ayrı bir satırda verir; Şekil 19.3 her turun sonundaki takası gösterir.

İzlemede üç ayrıntı göze çarpar. Birincisi, tur 0'da 13 de 10'dan büyük olduğu için min yalnız bir kez değişti. Tur 1'de ise iki kez değişti: önce 14'e, sonra 13'e. Kaç güncelleme yapılacağı girdiye bağlıdır, ama karşılaştırma sayısı bağlı değildir. İkincisi, tur 2'de 14 zaten yerindeydi ve takas kendisiyle yapıldı. Üçüncüsü, dizi tur 3'ten önce henüz sıralı değildi; son takas iki öğeyi birden yerine oturttu. Toplam 4 + 3 + 2 + 1 = 10 karşılaştırma ve 4 takas çağrısı yapıldı.

19.2.3Analiz

Tur i'de iç döngü j = i + 1, …, R için çalışır. n öğeli bir dizide (L = 0, R = n − 1) ilk turda n − 1, ikinci turda n − 2, son turda 1 karşılaştırma yapılır:

C(n) = (n − 1) + (n − 2) + … + 2 + 1 = n(n − 1)/2 ≈ n²/2

Bu toplam, ilk n − 1 doğal sayının toplamıdır. Toplamı bulmanın bilinen yolu, terimleri bir de ters sırayla yazıp alt alta toplamaktır. Her sütunun toplamı n'dir ve n − 1 sütun vardır. İki kat toplam n(n − 1) eder, toplamın kendisi yarısıdır.

Karşılaştırma sayısı girdiden bağımsızdır: dizi sıralı da olsa, ters sıralı da olsa, rastgele de olsa iç döngü aynı sayıda döner. Seçimli sıralama için en iyi, ortalama ve en kötü durum aynıdır ve Θ(n²)'dir. Takas sayısı ise tam olarak n − 1'dir: her dış turda bir takas yapılır ve son öğe için tur yoktur. Bunların bazıları öğenin kendisiyle takasıdır; kodu if (min != i) ile korumak gereksiz takasları önler, ama her tura bir karşılaştırma ekler. Ek bellek yalnız i, j, min ve takasın geçici değişkenidir: O(1). Algoritma yerindedir.

Tablo 19.2 iki sayının ne kadar farklı büyüdüğünü gösterir. n on katına çıktığında karşılaştırma sayısı yaklaşık yüz katına, takas sayısı ise yalnız on katına çıkar. Takas pahalıysa bu fark seçimli sıralamayı değerli kılar. Tutanaklar büyükse, örneğin her biri birkaç yüz bayt ise, her takas üç büyük kopyalama demektir. Flash bellekte her yazma hücreyi yıpratır. Bu tür durumlarda seçimli sıralamanın yaptığı n − 1 takas, öteki temel algoritmaların n² mertebesindeki taşımasından çok daha ucuzdur.

Seçimli sıralama kararlı değildir. Bunun nedeni uzak takastır. a[i] ile a[min] arasında birçok öğe olabilir. a[i] bu öğelerin üzerinden atlar ve eşit anahtarlı bir öğenin arkasına düşebilir. Şekil 19.2'deki girdide (3a, 1b, 3c, 2d, 1e) bu adım adım görülür:

• Tur 0. En küçük 1b'dir (min = 1). 3a ile 1b takaslanır: (1b, 3a, 3c, 2d, 1e).
• Tur 1. Kalanların en küçüğü 1e'dir (min = 4). 3a ile 1e takaslanır: (1b, 1e, 3c, 2d, 3a). 3a, 3c'nin ve 2d'nin üzerinden atlayarak en sona gitti. Kararlılık bu adımda bozuldu.
• Tur 2. En küçük 2d'dir. 3c ile 2d takaslanır: (1b, 1e, 2d, 3c, 3a).
• Tur 3. kucuk(3a, 3c) yanlıştır; min değişmez ve takas kendisiyledir. Sonuç (1b, 1e, 2d, 3c, 3a).

Bu girdide 1b ile 1e'nin sırası korunmuştur, ama bu bir rastlantıdır. Kararlılık bütün girdiler için geçerli olması gereken bir özelliktir; tek bir karşı örnek algoritmayı kararsız yapar. En küçük karşı örnek üç öğelidir ve alıştırmalarda ele alınır.

19.3Eklemeli sıralama

19.3.1Fikir ve kod

Eklemeli sıralama (insertion sort), iskambil oynayan birinin elindeki kâğıtları dizme biçimidir. Kâğıtlar masadan tek tek alınır. Eldeki kâğıtlar her an sıralıdır; yeni kâğıt bunların arasında uygun yere sokulur. Bunun için yeni kâğıttan büyük olanlar bir sağa itilir ve açılan boşluğa yeni kâğıt konur.

Dizide de aynısı yapılır. Dizinin solunda sıralı bir ön ek büyür. Başlangıçta ön ek yalnız ilk öğedir ve tek öğe her zaman sıralıdır. Her turda ön ekin hemen sağındaki öğe alınır ve ön ek içinde yerine eklenir. Tur sonunda ön ek bir öğe uzar. İki sürümden ilki şudur:

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;
    }
}

• Satır 2. i, yerleştirilecek öğenin indisidir ve L + 1'den başlar. Bu anda a[L..i−1] sıralıdır.
• Satır 3. Yerleştirilecek değer v'ye alınır. Bu adım zorunludur: ilk kaydırma a[i]'nin üzerine yazar ve değer kaybolur.
• Satır 4. j, ön ekin sağ ucundan başlar ve sola doğru ilerler.
• Satır 5. Döngü iki koşul birlikte doğru olduğu sürece döner: j alt dizinin içindedir (j >= L) ve a[j], v'den büyüktür. C'nin && işleci kısa devreyle çalışır: ilk koşul yanlışsa ikincisi hiç hesaplanmaz. j L − 1'e indiğinde a[j] okunmaz; okunsaydı dizinin dışına çıkılırdı.
• Satır 6–7. v'den büyük öğe bir sağa kaydırılır ve j bir azalır. Kaydırma tek bir atamadır, takas değildir.
• Satır 9. Döngü bittiğinde a[j] ya v'den küçük ya da ona eşittir ya da j alt dizinin solundadır. Her iki durumda da v'nin yeri j + 1'dir.

Döngü değişmezi bu kez şöyledir: dış döngünün her turu başlarken a[L..i−1], girdide bu konumlarda bulunan öğelerin sıralı hâlidir. Seçimli sıralamanın değişmeziyle aradaki fark önemlidir. Eklemeli sıralamada ön ek sıralıdır ama dizinin en küçük öğelerini içermek zorunda değildir: sonradan gelen küçük bir öğe ön ekin en başına girebilir. Algoritma son tura kadar hiçbir öğenin son yerini kesin bilmez.

19.3.2Adım adım izleme

insertion(a, 0, 4) çağrısı a = [7, 2, 9, 5, 1] üzerinde izlenir. Tablo 19.3 her turun karşılaştırmalarını, kaydırmalarını ve tur sonundaki diziyi verir.

En öğretici tur i = 3'tür. Şekil 19.4 bu turun ara durumlarını gösterir. v = 5 bir kenara alınmıştır. 9, 5'ten büyüktür ve bir sağa kayar; dizide geçici olarak iki 9 görünür. Sonra 7 kayar ve iki 7 görünür. 2 ise 5'ten küçüktür; döngü durur ve 5, a[1]'e yazılır. Ara durumlarda dizide bir değerin iki kopyası olması normaldir. Kaydırma bir öğeyi sağa kopyalar; eski yer bir sonraki adımda ya başka bir öğeyle ya da v ile doldurulur.

İzlemede 7 kaydırma ve 9 karşılaştırma sayıldı. Kaydırma sayısı rastlantı değildir: 7, dizideki ters sıralı çiftlerin sayısıdır. Bu bağlantı evrik kavramıyla birlikte ayrıca kanıtlanır. Karşılaştırma sayısı kaydırma sayısından biraz fazladır. Bir tur ya a[j] > v yanlış çıkınca biter ve bu son sınama kaydırmasız bir karşılaştırmadır. Ya da j dizinin başından çıkınca biter; o zaman fazladan karşılaştırma yoktur. Burada i = 2 ve i = 3 turları ilk yolla bitti, i = 1 ve i = 4 turları ikinci yolla. Karşılaştırma sayısı 7 + 2 = 9 oldu.

19.3.3Bekçili sürüm: insertion1

İç döngünün her adımı iki sınama yapar: j >= L ve a[j] > v. Birincisi yalnız v dizinin başına kadar gidecekse işe yarar. Bu yalnız v o ana kadar görülen öğelerin en küçüğü olduğunda olur. Dizinin en küçük öğesi baştan a[L]'ye yerleştirilirse hiçbir v onun soluna geçemez; a[L] her döngüyü kendiliğinden durdurur. Böyle bir öğeye bekçi (sentinel) denir. İkinci sürüm bu fikri kullanır:

void insertion1(int a[], int L, int R) {
    for (int i = R; i > L; i--) // bekçi
        if (a[i] < a[i-1]) SWAP(a[i], a[i-1]);
    for (int i = L + 2; i <= R; i++) {
        int v = a[i], j = i;
        while (kucuk(v, a[j - 1])) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = v;
    }
}

• Satır 2–3. Hazırlık geçişi: dizinin sağından soluna komşular karşılaştırılır ve sağdaki küçükse takaslanır. Bu tek geçiş en küçük öğeyi kabarcık gibi a[L]'ye taşır. n − 1 karşılaştırma ve en çok n − 1 takas yapılır.
• Satır 4. Asıl döngü L + 2'den başlar. Hazırlık geçişinden sonra a[L] en küçüktür, bu yüzden a[L..L+1] zaten sıralıdır.
• Satır 5–10. İç döngüde yalnız kucuk(v, a[j − 1]) sınanır. j, L + 1'e indiğinde a[L], v'den büyük olamayacağı için koşul yanlış olur ve döngü durur. j'nin L'nin soluna geçmesi imkânsızdır.

Bu sürüm iki küçük farkla daha hızlıdır. İç döngü adım başına bir sınama eksik yapar; döngü binlerce kez döndüğünde bu fark ölçülebilir. Ayrıca koşul tek bir karşılaştırma olduğu için derleyici döngüyü daha sıkı derler. Bedeli, hazırlık geçişinin fazladan n − 1 karşılaştırmasıdır. Tablo 19.4, insertion1(a, 0, 3) çağrısını a = [4, 3, 1, 2] üzerinde izler.

Son turda v = 2, iki öğeyi kaydırdıktan sonra a[0] = 1 ile karşılaştı ve durdu. Sınır denetimi olmadan güvenle durabildi, çünkü bekçi her v'den küçük ya da ona eşittir. Hazırlık geçişinin bir yan etkisi de vardır: yalnız en küçük öğe değil, yol üzerindeki başka küçük öğeler de biraz sola kayar. Burada 1, 3'ün ve 4'ün önüne geçerken 3 de bir sağa itildi. Bu yüzden sonraki turlarda kaydırılacak iş biraz azalabilir.

Bekçi fikri yalnız sıralamaya özgü değildir. Bir dizide doğrusal arama yaparken aranan değer dizinin sonuna geçici olarak yazılırsa döngü her adımda “dizi bitti mi?” diye sormak zorunda kalmaz. Bağlı listelerde başlık düğümü de aynı işi görür: liste boş olsa bile ilk düğümün öncülü vardır ve özel durum ortadan kalkar.

19.3.4En iyi ve en kötü durum

Eklemeli sıralamanın işi, seçimli sıralamanınkinin tersine, girdiye çok bağlıdır. Şekil 19.5 iki uç durumu yan yana koyar.

En iyi durum: sıralı girdi. Her turda v, ön ekin en sağındaki öğeyle karşılaştırılır. O öğe v'den küçük ya da eşittir; döngü hiç dönmez ve v yerinde kalır. n − 1 turun her birinde bir karşılaştırma yapılır, kaydırma yapılmaz. Toplam n − 1 karşılaştırma eder; çalışma süresi Θ(n)'dir. Hiçbir algoritma bundan iyisini yapamaz: dizinin sıralı olduğundan emin olmak için her öğeye en az bir kez bakmak gerekir.

En kötü durum: ters sıralı girdi. Her yeni öğe o ana kadar görülenlerin hepsinden küçüktür. i. turda v, ön ekteki i öğenin hepsiyle karşılaştırılır, hepsi bir sağa kayar ve v en başa yazılır. Toplam

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

karşılaştırma ve aynı sayıda kaydırma eder. Çalışma süresi Θ(n²)'dir. n = 1.000 için bu 499.500 karşılaştırma ve 499.500 kaydırmadır.

Eklemeli sıralama kararlıdır. İç döngünün koşulu katı eşitsizliktir: a[j] > v. Ön ekte v'ye eşit bir öğeyle karşılaşılınca koşul yanlış olur ve v o öğenin sağına yazılır. Girdide sonra gelen öğe, çıktıda da sonra kalır. Koşul a[j] >= v yazılsaydı v eşitlerin üzerinden atlayıp onların soluna geçerdi; dizi yine sıralanırdı ama kararlılık kaybolurdu ve gereksiz kaydırmalar yapılırdı. Algoritma yerindedir: i, j ve v dışında bellek kullanmaz.

Eklemeli sıralamanın asıl gücü “neredeyse sıralı” veridir. Her öğe son yerine birkaç konum uzaksa her tur birkaç adımda biter ve toplam iş n'ye yakın kalır. Sıralı bir listeye arada bir yeni kayıt eklenen uygulamalar, büyük ölçüde sıralanmış bir diziyi son kez düzelten algoritmalar ve küçük parçalar bu durumdadır. Hızlı sıralamanın pratik gerçeklemeleri, parçalar 10–20 öğenin altına inince eklemeli sıralamaya geçer.

19.3.5Ortalama durum: bir örnek

En iyi durum n − 1, en kötü durum n(n − 1)/2 karşılaştırmadır. Rastgele bir girdi için kaç karşılaştırma beklenir? Akla ilk gelen, iki ucun ortalamasını almaktır. Bu yanlıştır. Ortalama durum analizinde örnekler uzayındaki bütün durumlar gözlenmeli ve her biri olasılığıyla tartılmalıdır. Uçların ortalaması ise yalnız iki durumu hesaba katar.

Önce tek bir turun ortalaması bulunur. Tur j'de (bu kesimde tur indisi için j kullanılır) a[0..j−1] sıralıdır ve a[j] yerleştirilecektir. Girdi rastgeleyse a[j]'nin ön ekteki j öğe arasındaki sırası da rastgeledir. Öğe j + 1 konumdan herhangi birine eşit olasılıkla yerleşir: ön ekin en sağına, bir solundakine, … , en başa.

Şekil 19.6, j = 3 için bu dört durumu sıralı ön ek [3, 6, 8] üzerinde gösterir.

• Durum 1, v = 10. 8 > 10 yanlıştır. 1 karşılaştırma.
• Durum 2, v = 7. 8 > 7 doğru, 6 > 7 yanlıştır. 2 karşılaştırma.
• Durum 3, v = 5. 8 > 5 ve 6 > 5 doğru, 3 > 5 yanlıştır. 3 karşılaştırma.
• Durum 4, v = 2. 8 > 2, 6 > 2, 3 > 2 doğrudur. Sonra j = −1 olur, j >= 0 yanlış çıkar ve kısa devre yüzünden a[j] > v hiç sınanmaz. 3 karşılaştırma.

Son iki durum aynı sayıda karşılaştırma ister. Öğe en başa gidecekse son karşılaştırma “dur” cevabı vermez; döngüyü sınır sınaması bitirir. Bu yüzden 4 karşılaştırmalık bir durum yoktur. Dört durum eşit olasılıklıdır ve beklenen karşılaştırma sayısı

(1 + 2 + 3 + 3) / 4 = 9/4 = 2,25

olur. Bu sayı en iyi tur (1) ile en kötü turun (3) ortalaması olan 2'den farklıdır. Burada fark küçüktür, ama yöntem yanlıştır ve başka algoritmalarda büyük hatalara yol açar. Erken duran kabarcık sıralamasında uçların ortalaması ≈ n²/4 karşılaştırma verir; bütün dizilişler sayılınca gerçek ortalamanın ≈ n²/2 olduğu görülür.

19.3.6Ortalama durum: genel hesap

Hesabı genelleştirmek için olasılığın bir kavramı gerekir. Değeri rastlantıya bağlı bir sayıya rastlantı değişkeni denir. C_j, j. öğeyi yerleştirirken yapılan karşılaştırma sayısı olsun. Değeri girdiye bağlıdır, bu yüzden bir rastlantı değişkenidir. Bir rastlantı değişkeninin beklenen değeri E(C_j), alabileceği her değerin olasılığıyla çarpılıp toplanmasıyla bulunur. Bütün durumlar eşit olasılıklıysa beklenen değer basit aritmetik ortalamadır.

Tur j'de j + 1 durum vardır. Öğe sağdan k. konuma yerleşecekse (k = 1, …, j) k karşılaştırma yapılır. En başa yerleşecekse, yani j + 1. durumda, j karşılaştırma yapılır. Böylece

E(C_j) = (1 / (j + 1)) · [1 + 2 + … + j + j] = (1 / (j + 1)) · [2j + Σ_k=1^j−1 k]

Köşeli parantezin içi j(j + 1)/2 + j'dir. j + 1'e bölünce

E(C_j) = j/2 + j/(j + 1) = j/2 + 1 − 1/(j + 1) = (j + 2)/2 − 1/(j + 1)

bulunur. j = 3 için 5/2 − 1/4 = 2,25 eder; bu, örnekte elle bulunan değerdir. j = 4 için 3 − 1/5 = 2,8'dir: beş durumun karşılaştırma sayıları 1, 2, 3, 4 ve 4'tür, ortalamaları 14/5 = 2,8.

Bütün dizinin toplam karşılaştırma sayısı Y = C₁ + C₂ + … + C_N−1'dir. Beklenen değer toplamın üzerine dağılır: toplamın beklenen değeri, beklenen değerlerin toplamıdır. Bu yüzden turlar arasındaki bağıntıyla uğraşmadan

E(Y) = Σ_j=1^N−1 E(C_j) = Σ_j=1^N−1 [(j + 2)/2 − 1/(j + 1)]

yazılır. İlk parça (1/2) · [N(N − 1)/2 + 2(N − 1)] = (N² + 3N)/4 − 1'dir. İkinci parça 1/2 + 1/3 + … + 1/N = H_N − 1'dir; burada H_N = 1 + 1/2 + … + 1/N, harmonik sayıdır. Harmonik sayı yavaş büyür: H_N = ln N + O(1). İki parça birleşince −1'ler birbirini götürür:

Formülün doğruluğu küçük N değerleri için bütün dizilişler tek tek sayılarak denetlendi. Tablo 19.5'da “bütün dizilişler” sütunu, N! permütasyonun her biri sayaçlı bir insertion ile sıralanıp karşılaştırma sayılarının ortalaması alınarak bulundu. Sonuç formülle birebir aynıdır.

Küçük N'lerde formül N²/4'ten belirgin biçimde büyüktür, çünkü 3N/4 terimi henüz önemlidir. N büyüdükçe N²/4 baskın gelir. N = 1.000 için formül 250.750 − 7,49 ≈ 250.743 verir; bu, en kötü durumun (499.500) yaklaşık yarısıdır. Ortalama durum en kötü durumdan iki kat iyidir, ama yine Θ(n²)'dir. Kaydırmalar da ortalamada n²/4 kadardır. Kaydırmaya “yarı değişim” de denir: takasta iki öğe yer değiştirir, kaydırmada yalnız biri.

Ortalama durum analizinin dayandığı varsayıma dikkat etmek gerekir: bütün dizilişler eşit olasılıklıdır. Gerçek veri bu varsayıma uymayabilir. Bir uygulamanın verisi çoğunlukla neredeyse sıralıysa eklemeli sıralamanın gerçek ortalaması n²/4'ten çok küçük olur. Analiz bir model üzerinde yapılır; model veriye uymuyorsa sonuç da uymaz.

19.4Kabarcık sıralaması

19.4.1Fikir ve kod

Kabarcık sıralaması (bubble sort) yalnız komşu öğeleri karşılaştırır ve yanlış sıradaysa takaslar. Dizinin sağ ucundan sola doğru ilerleyen bir geçişte küçük bir öğe, her komşu takasında bir konum sola kayar. Geçiş bitince kalan öğelerin en küçüğü en sola varmış olur, tıpkı suyun dibinden yüzeye çıkan bir hava kabarcığı gibi. Algoritmanın adı bu benzetmeden gelir.

void bubble(int a[], int L, int R) {
    int i, j;
    for (i = L; i < R; i++)
        for (j = R; j > i; j--)
            if (a[j] < a[j-1]) SWAP(a[j], a[j-1]);
}

• Satır 3. Dış döngü n − 1 tur döner. Tur i'nin sonunda a[i]'de kalanların en küçüğü bulunur.
• Satır 4. İç döngü j'yi dizinin sağ ucundan i + 1'e kadar indirir. a[L..i−1] önceki turlarda yerine oturmuştur; o bölgeye girilmez.
• Satır 5. Karşılaştır-takas: sağdaki a[j] soldaki a[j − 1]'den küçükse yer değiştirirler. Karşılaştırma katıdır; eşit komşular takaslanmaz.

Seçimli sıralama da her turda kalanların en küçüğünü a[i]'ye koyar. Aradaki fark yöntemdedir. Seçimli sıralama en küçüğü bulup tek bir uzak takasla taşır. Kabarcık sıralaması ise küçük öğeyi komşu takaslarıyla adım adım sola götürür. Bu yolculuk sırasında başka öğeler de yer değiştirir. Örneğin büyük öğeler her turda biraz sağa kayar. Kabarcık sıralaması bu yüzden seçimli sıralamadan çok daha fazla taşıma yapar, ama karşılığında önemli bir özellik kazanır: yalnız komşular takaslandığı için kararlıdır.

Şekil 19.7, bubble(a, 0, 4) çağrısının a = [7, 2, 9, 5, 1] üzerindeki turlarını gösterir; Tablo 19.6 her karşılaştırmayı ayrı ayrı verir.

Tur 0'da 1, dört takasla en sola çıktı. Tur 1'de iki şey birden oldu: 5 ile 9 yer değiştirdi ve 9 en sağa ulaştı, ardından 2 yerine yükseldi. Tur 2'de tek takas diziyi sıraladı. Tur 3 ise yalnız bir karşılaştırma yaptı ve hiçbir şey değiştirmedi; 7 zaten a[3]'teydi. Toplam 10 karşılaştırma ve 7 takas yapıldı. Takas sayısı yine 7'dir, tıpkı eklemeli sıralamanın aynı dizideki kaydırma sayısı gibi.

19.4.2Erken duran sürüm: bubble2

İzlemedeki son tur boşunaydı: dizi tur 2'den sonra sıralıydı, ama algoritma bunu bilmiyordu. Oysa bilgi elindeydi. Bir tur boyunca hiç takas yapılmadıysa her komşu çifti doğru sıradadır, yani dizi sıralıdır. Sonraki turlara girmeye gerek yoktur. Kod bu gözlemle biraz daha dikkatli yazılabilir:

void bubble2(int a[], int L, int R) {
    for (int i = L; i < R; i++) {
        int takas = 0;      // bu turda takas oldu mu?
        for (int j = R; j > i; j--)
            if (kucuk(a[j], a[j - 1])) {
                SWAP(a[j], a[j - 1]);
                takas = 1;
            }
        if (!takas) return; // sıralı: erken çık
    }
}

• Satır 3. Her turun başında takas bayrağı sıfırlanır.
• Satır 5–8. Takas yapılınca bayrak 1 olur. Karşılaştırma bu kez kucuk makrosuyla yazılmıştır; anlamı bubble'daki satırla aynıdır.
• Satır 9. Tur takassız bittiyse yordam hemen döner.

Tablo 19.7, bubble2(a, 0, 4) çağrısını a = [2, 1, 3, 5, 4] üzerinde izler. Bu dizide yalnız iki çift yanlış sıradadır.

İlk tur iki takasla diziyi sıraladı. İkinci tur hiç takas yapmadı ve yordam döndü. Toplam 4 + 3 = 7 karşılaştırma yapıldı; erken durma olmasaydı iki tur daha (2 + 1 = 3 karşılaştırma) boşuna dönecekti. Sıralı bir girdide bubble2 tek turda, n − 1 karşılaştırmayla biter; en iyi durumu Θ(n)'dir.

Erken durmanın kazancı girdinin biçimine bağlıdır. Sağdan sola ilerleyen bu sürümde küçük bir öğe tek turda en sola gidebilir, ama büyük bir öğe her turda yalnız bir konum sağa ilerler. [2, 3, 4, 5, 1] dizisinde 1 ilk turda başa çıkar ve ikinci turda yordam durur: 2 tur. [5, 1, 2, 3, 4] dizisinde ise 5'in en sağa varması için dört tur gerekir; erken durma hiçbir şey kazandırmaz. İki dizide de yalnız dört çift yanlış sıradadır.

19.4.3Analiz

bubble her durumda (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 karşılaştırma yapar; iç döngünün sınırları girdiye bağlı değildir. Takas sayısı ise girdiye bağlıdır. Sıralı girdide hiç takas yapılmaz. Ters sıralı girdide her karşılaştırma bir takasla sonuçlanır ve n(n − 1)/2 takas yapılır. Rastgele girdide ortalama takas sayısı n(n − 1)/4'tür; bunun nedeni hemen aşağıda evriklerle açıklanır.

Bazı kaynaklar, örneğin Sedgewick'in kitabı, kabarcık sıralamasının ortalamada da yaklaşık n²/2 değiştirme yaptığını söyler. Tablo 19.8'daki sayım ise ortalama takas sayısının n(n − 1)/4, yani en kötü durumun tam yarısı olduğunu gösterir. Karşılaştırma sayısı için iki ifade de uyuşur: n²/2.

Erken duran bubble2 sıralı girdide O(n)'dir, ama ortalamada pek bir şey kazanmaz. Bütün dizilişler üzerinden sayıldığında n = 8 için ortalama tur sayısı 5,79'dur; en çok 7 tur dönebilirdi. Ortalama karşılaştırma sayısı 26,0'dır, erken durmasız sürümün 28 karşılaştırmasına çok yakındır. Bu yüzden karmaşıklık özetinde kabarcık sıralamasının ortalaması ≈ n²/2 karşılaştırma olarak verilir. Eklemeli sıralama aynı ortalama girdide bunun yarısıyla yetinir.

Kabarcık sıralaması kararlıdır: yalnız komşular takaslanır ve eşit komşular takaslanmaz. Eşit iki öğe birbirinin üzerinden hiç atlayamaz, dolayısıyla göreli sıraları değişmez. Algoritma yerindedir; ek bellek O(1)'dir. Toplam karmaşıklık O(n²)'dir.

Uygulamada kabarcık sıralaması nadiren kullanılır. Eklemeli sıralama aynı işi daha az karşılaştırma ve daha ucuz kaydırmalarla yapar. Kabarcık sıralamasının iki değeri vardır: öğretmek kolaydır ve erken duran sürümü bir dizinin sıralı olup olmadığını tek geçişte söyler.

19.5Evrikler: ortak ölçü

Eklemeli sıralama [7, 2, 9, 5, 1]'i 7 kaydırmayla, kabarcık sıralaması 7 takasla sıraladı. İki farklı algoritmanın aynı sayıda taşıma yapması bir rastlantı değildir. İkisi de aynı şeyi sayar: dizideki “ters duran” çiftleri.

[7, 2, 9, 5, 1] dizisinin evrikleri, değerleriyle yazılırsa (7, 2), (7, 5), (7, 1), (2, 1), (9, 5), (9, 1) ve (5, 1)'dir. Şekil 19.8 bu yedi çifti yaylarla gösterir. Sıralı bir dizinin evrik sayısı 0'dır. Ters sıralı bir dizide her çift evriktir ve n öğeden n(n − 1)/2 çift seçilebilir. Evrik sayısı bu yüzden bir dizinin “ne kadar sırasız” olduğunun ölçüsüdür: 0 ile n(n − 1)/2 arasında değişir.

Teoremin ikinci yarısı, rastgele bir dizinin ortalama evrik sayısını bulmakla tamamlanır. Her (i, j) çifti için iki öğeden biri büyüktür; rastgele bir dizilişte büyüğün solda olma olasılığı 1/2'dir. Bunu görmek için her dizilişi, ters çevrilmiş hâliyle eşleştirmek yeter: bir çift bu ikisinden tam birinde evriktir. n(n − 1)/2 çiftin her biri ortalamada 1/2 evrik katkısı yapar. Ortalama evrik sayısı

n(n − 1)/2 · 1/2 = n(n − 1)/4

olur. Kabarcık sıralamasının ortalama takas sayısı ve eklemeli sıralamanın ortalama kaydırma sayısı bu yüzden n(n − 1)/4'tür. Tablolardaki 3, 5, 7,5 ve 10,5 değerleri tam olarak bu formülden gelir.

Bu sonucun güçlü bir yan sonucu vardır. Yalnız komşu öğeleri takaslayan ya da öğeleri teker teker kaydıran her algoritma, her taşımada en çok bir evrik giderir. Ortalama girdide n(n − 1)/4 evrik vardır. Öyleyse bu tür her algoritma ortalamada Ω(n²) iş yapar; daha akıllı bir döngü düzeni bu duvarı aşamaz. Duvarı aşmanın tek yolu, bir taşımada birden çok evrik gidermektir. Bu da birbirinden uzak öğeleri takaslamakla olur. Shell sıralaması ve hızlı sıralama bu yolu seçer.

Seçimli sıralama bu kuralın dışındadır; zaten uzak takas yapar. Tek bir uzak takas birçok evriği birden giderebilir. Örneğin [5, 2, 3, 4, 1] dizisinde 5 ile 1'in takası 7 evriği birden yok eder ve diziyi sıralar. Ancak seçimli sıralamanın sorunu taşıma değil, karşılaştırmadır: girdiden bağımsız olarak n²/2 karşılaştırma yapar.

19.6Sayarak sıralama

19.6.1Karşılaştırmadan sıralamak

Şimdiye kadarki algoritmalar girdi hakkında bilgiyi yalnız iki öğeyi karşılaştırarak edindi. Sayarak sıralama (counting sort) bambaşka bir yol izler: öğeleri birbirleriyle hiç karşılaştırmaz. Bunun yerine değerleri dizi indisi olarak kullanır. Algoritma 1954'te Harold H. Seward'a dayanır. Tek bir koşulu vardır: sıralanacak değerler tamsayıdır ve aralıkları bilinir, örneğin 0 … k.

Fikir şöyledir. Her x değeri için girdide x'ten küçük ya da ona eşit kaç öğe olduğu bilinirse x'in çıktıdaki yeri de bilinir. Girdide 3'ten küçük ya da 3'e eşit üç öğe varsa son 3, çıktının üçüncü konumuna, yani 2 indisine gider. Bu sayıları bulmak için önce her değerin kaç kez geçtiği sayılır, sonra sayılar soldan sağa toplanır.

int counting_sort(const int a[], int b[],
                  int r, int k) {
    int *c = malloc((k + 1) * sizeof *c);
    if (c == NULL) return -1;
    for (int i = 0; i <= k; i++) c[i] = 0;  // L1
    for (int j = 0; j <= r; j++) c[a[j]]++; // L2
    for (int i = 1; i <= k; i++)            // L3
        c[i] += c[i - 1];
    for (int j = r; j >= 0; j--) {          // L4
        b[c[a[j]] - 1] = a[j];
        c[a[j]]--;
    }
    free(c);
    return 0;
}

• Satır 3–4. Sayaç dizisi heap bellekten alınır. Bunun nedeni, k'nın çalışma zamanında belli olmasıdır. Kitaplardaki int c[K] yazımı derleme zamanında sabit bir boyut ister. Değişken uzunluklu dizi (int c[k + 1]) C99'da vardır, ama yığında yer kaplar ve k büyükse yığını taşırır. malloc başarısız olursa yordam −1 döndürür ve çağıran durumu anlar.
• Satır 5 (L1). Sayaçlar sıfırlanır. malloc belleği temizlemez; bu satır olmadan sayaçlar rastgele değerlerle başlar. Aynı işi calloc da yapabilirdi.
• Satır 6 (L2). Her öğe kendi değerinin sayacını bir artırır. c[a[j]]++ ifadesinde değer, indis olarak kullanılır. Karşılaştırma yoktur.
• Satır 7–8 (L3). Sayaçlar soldan sağa toplanır. Döngü bitince c[x], girdide x'ten küçük ya da eşit öğe sayısıdır. Bu tür toplama kümülatif toplam (önek toplamı) denir.
• Satır 9–12 (L4). Girdi sağdan sola gezilir. a[j]'nin yeri c[a[j]] − 1'dir (indisler 0'dan başladığı için 1 çıkarılır). Öğe yazılınca sayaç bir azaltılır. Aynı değerli bir sonraki öğe bir sola yerleşir.
• Satır 13–14. Sayaç dizisi geri verilir ve 0 döndürülür.

19.6.2Sayma ve kümülatif toplam

Yordam a = [3, 0, 6, 9, 4, 3, 10, 5], r = 7, k = 10 ile çağrılsın. L2 her öğeyi sayar: c[3] önce 1, ikinci 3 gelince 2 olur; 0, 4, 5, 6, 9 ve 10'un sayaçları 1'dir; 1, 2, 7 ve 8 girdide yoktur ve sayaçları 0 kalır. L3 sayaçları biriktirir. Tablo 19.10 iki aşamanın sonunu, Şekil 19.9 bellekteki üç diziyi gösterir.

L3 sonundaki satır doğrudan okunabilir. c[9] = 7: girdide 9'dan küçük ya da eşit 7 öğe vardır, bu yüzden 9 çıktının 7. konumuna, yani b[6]'ya gider. c[3] = 3: iki 3'ün sonuncusu b[2]'ye, öncekisi b[1]'e gider. Girdide olmayan değerlerin sayaçları (1, 2, 7, 8) bir öncekini tekrarlar; bu değerler çıktıya hiçbir şey yazmaz.

19.6.3Yerleştirme ve kararlılık

L4, girdiyi sağdan sola gezer. Tablo 19.11 her adımı verir.

Sonuç b = [0, 3, 3, 4, 5, 6, 9, 10]'dur. Şekil 19.10 L4'ün bitişini gösterir. L4 bitince c[x], her değerin çıktıdaki ilk konumunu tutar: c[3] = 1, ilk 3'ün b[1]'de olduğunu söyler.

İki 3'e dikkat edelim. a[5]'teki 3 önce işlendi ve b[2]'ye yazıldı. a[0]'daki 3 sonra işlendi ve sayaç bir azaldığı için b[1]'e, yani bir sola yazıldı. Girdide önce gelen 3 (a[0]) çıktıda da önce gelir. Algoritma kararlıdır ve bunun nedeni L4'ün sağdan sola gezmesidir: aynı değerli öğelerin en sağdaki önce yerleşir ve en sağdaki yeri alır.

L4 soldan sağa yazılsaydı çıktı yine sıralı olurdu, ama eşitlerin sırası tersine dönerdi. Bu durumda a[0]'daki 3 önce işlenir ve b[2]'ye, a[5]'teki 3 ise b[1]'e yazılır. Sayılar tek başına sıralanıyorsa fark görünmez. Sayarak sıralama tutanakları ya da basamak sıralamasının bir geçişini sıralıyorsa fark sonucu bozar.

19.6.4Analiz ve sınırlar

Yordamın dört döngüsü vardır ve hiçbiri iç içe değildir. Maliyetleri Tablo 19.12'da toplanmıştır.

Toplam O(n + k)'dir. k = O(n) ise, yani değer aralığı öğe sayısından çok büyük değilse, sayarak sıralama doğrusal zamanda çalışır. Ek bellek c için k + 1 ve b için n öğedir, toplam O(n + k). Algoritma yerinde değildir.

Doğrusal zaman bir bedelle gelir: veri aralığı bilinmeli ve küçük olmalıdır. Aralık büyürse k terimi baskın çıkar. 10 sayı sıralanacak, ama değerler 0 ile 1.000 arasında olabiliyorsa L1 ve L3 binlik döngülerdir. n = 10 için k = 1.000 = n³'tür; “doğrusal” algoritma bu girdide n³'lük bir algoritmaya dönüşür. Aynı 10 sayıyı eklemeli sıralama en çok 45 karşılaştırmayla sıralar. 32 bitlik rastgele tamsayılar için ise k ≈ 4 · 10⁹'dur ve sayaç dizisi 16 GB tutar. Sayarak sıralama bu yüzden yaş, not, gün, harf kodu gibi dar aralıklı veriler içindir. Geniş aralıklı tamsayılar basamak sıralamasıyla sıralanır: sayı basamaklara bölünür ve her basamak dar aralıklı bir sayarak sıralamayla işlenir.

Algoritmanın iki geçişli yapısı başka yerlerde de karşımıza çıkar: ilk geçişte frekanslar sayılır, ikinci geçişte her öğe hesaplanan yerine doğrudan yazılır. Seyrek matrislerin hızlı devrik alma yöntemi (fast transpose) tam olarak budur. Önce her sütunda kaç sıfırdan farklı terim olduğu sayılır. Sayıların kümülatif toplamı, her sütunun devrik matristeki başlangıç konumunu verir. İkinci geçişte her terim doğrudan yerine yazılır ve bütün iş tek bir çıktı dizisiyle O(sütun sayısı + terim sayısı) zamanda biter.

19.7Shell sıralaması

19.7.1Fikir ve kod

Eklemeli sıralamanın zayıflığı, bir öğeyi her adımda yalnız bir konum ilerletmesidir. Dizinin sonundaki küçük bir öğe başa varmak için n − 1 kaydırma ister. Evrikler açısından bakılınca her kaydırma tek bir evrik giderir ve ters sıralı dizide n(n − 1)/2 evrik vardır. Donald Shell 1959'da basit bir çare önerdi: önce birbirinden uzak öğeleri sırala, sonra aralığı küçült.

Bir h sayısı seçilsin. Dizi, aralarında h konum bulunan öğelerden oluşan h ayrı zincire bölünür: a[0], a[h], a[2h], … birinci zincir, a[1], a[h+1], … ikinci zincirdir. Her zincir eklemeli sıralamayla ayrı ayrı sıralanır. Sonuçta dizi h-sıralı olur: her öğe kendinden h sonraki öğeden büyük değildir. Bu adım büyük bir h ile başlar ve h her adımda küçültülür. Son adımda h = 1'dir; bu, sıradan eklemeli sıralamadır.

void shell_sort(int a[], int n) {
    for (int h = n / 2; h > 0; h /= 2) // aralık
        for (int i = h; i < n; i++) {
            int v = a[i], j = i;
            while (j >= h && a[j - h] > v) {
                a[j] = a[j - h];    // h geri kaydır
                j -= h;
            }
            a[j] = v;
        }
}

• Satır 2. Aralık n/2'den başlar ve her adımda yarıya iner: n = 8 için 4, 2, 1; n = 1.000 için 500, 250, 125, 62, 31, 15, 7, 3, 1. Bu, Shell'in kendi önerdiği aralık dizisidir. Tamsayı bölmesi sayesinde dizi her zaman 1 ile biter.
• Satır 3–9. İç kısım, eklemeli sıralamanın 1 yerine h adımla yazılmış hâlidir. v = a[i] kenara alınır; j, h'şer adımla geri gider; v'den büyük öğeler h konum ileri kaydırılır. Koşuldaki j >= h, a[j − h]'nin dizinin içinde olmasını sağlar.

Kodda zincirler ayrı ayrı sıralanmaz. i döngüsü h'den n − 1'e kadar sırayla gider ve her öğeyi kendi zincirinde yerine ekler. Zincirler böylece iç içe, öğe öğe ilerler. Sonuç, zincirleri tek tek sıralamakla aynıdır, çünkü her zincirin eklemeli sıralaması öğelerini soldan sağa sırayla işler.

Algoritmanın doğruluğu son adımdan gelir: h = 1 turu eksiksiz bir eklemeli sıralamadır ve her diziyi sıralar. Önceki turlar yalnız bu son turun işini azaltır. Hangi aralık dizisi seçilirse seçilsin, 1 ile bittiği sürece sonuç doğrudur. Aralık dizisi yalnız hızı belirler.

19.7.2Adım adım izleme

shell_sort(a, 8) çağrısı a = [35, 33, 42, 10, 14, 19, 27, 44] üzerinde izlenir. Tablo 19.13 her aralığın sonundaki diziyi ve yapılan işi verir.

h = 4 turunda i = 4 için v = 14 alınır. a[0] = 35 > 14 olduğundan 35, a[4]'e kayar ve j = 0 olur. j >= 4 yanlıştır; 14, a[0]'a yazılır. Tek bir kaydırmayla 14 dört konum sola gitti. Aynı kaydırma 35'i de dört konum sağa götürdü. Eklemeli sıralamada bu iş dört komşu adım isterdi. i = 5 ve i = 6'da 19 ve 27 aynı biçimde 33 ve 42'nin önüne geçer. i = 7'de a[3] = 10 ≤ 44'tür ve 44 yerinde kalır.

h = 2 turunda dizi iki zincire ayrılır: çift indisler (14, 27, 35, 42) zaten sıralıdır. Tek indislerde (19, 10, 33, 44) yalnız 10, 19'un önüne geçer. h = 1 turu başladığında dizi [14, 10, 27, 19, 35, 33, 42, 44]'tür. Her öğe son yerinden en çok bir konum uzaktadır; eklemeli sıralama üç kısa kaydırmayla işi bitirir.

Aynı diziyi doğrudan eklemeli sıralama 18 karşılaştırma ve 13 kaydırmayla sıralar; dizide 13 evrik vardır. Shell sıralaması 19 karşılaştırma ve 7 kaydırma yaptı. Bu kadar küçük bir dizide karşılaştırmada kazanç yoktur, ama kaydırma sayısı yarıya inmiştir. 7 kaydırma 13 evriği giderdi: uzak kaydırmalar tek hamlede birden çok evrik yok eder. Örneğin h = 4'teki ilk kaydırma 35'i 33, 42 ve 10'un üzerinden atlattı. Dizi büyüdükçe bu etki belirginleşir.

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

Shell sıralamasının çalışma süresi aralık dizisine bağlıdır ve tam analizi zordur. Bilinen sonuçların bir kısmı şöyledir:

• Shell'in n/2, n/4, …, 1 dizisinde en kötü durum Θ(n²)'dir. Sorun, n 2'nin kuvveti olduğunda bütün aralıkların son tura kadar çift olmasıdır. Tek ve çift konumlar 1'e kadar hiç karşılaşmaz ve kötü bir girdide son tur yine n² mertebesinde iş yapar.
• Knuth'un 1, 4, 13, 40, 121, … dizisinde (h ← 3h + 1) en kötü durum O(n^3/2)'dir. Ardışık aralıklar ortak bölen paylaşmadığı için zincirler birbirine karışır.
• Daha karmaşık dizilerle (örneğin Pratt'ın 2^p3^q biçimindeki aralıkları) en kötü durum O(n lg² n)'ye iner. Ortalama durum için kapalı bir formül bilinmez.

Shell sıralamasının işe yaramasının bir nedeni şu özelliktir: h-sıralı bir dizi k-sıralandığında h-sıralı kalır. Yani sonraki turlar önceki turların kazandırdığı düzeni bozmaz, üzerine ekler. Bu özelliğin kanıtı bu notun kapsamı dışındadır; Knuth'un kitabında verilir.

Tablo 19.14, iki aralık dizisini n = 1.000 öğede karşılaştırır. Değerler sayaçlı bir C programıyla ölçüldü.

Rastgele girdide eklemeli sıralama 240 binden fazla kaydırma yapar; her iki Shell sürümü 10 binin altında kalır. Sıralı girdide ise eklemeli sıralama rakipsizdir, çünkü Shell her aralık için bütün diziyi bir kez gezer: n = 1.000 ve Shell aralıkları için 500 + 750 + 875 + 938 + 969 + 985 + 993 + 997 + 999 = 8.006 karşılaştırma. Bu, aralık sayısı kadar n mertebesinde iştir, yani O(n lg n).

Shell sıralaması yerindedir: eklemeli sıralama kadar bellek kullanır. Kararlı değildir. Uzak kaydırmalar eşit öğeleri birbirinin üzerinden atlatabilir. En küçük örnek dört öğelidir: [2a, 5, 2b, 2c]. h = 2 turunda i = 3 için v = 2c alınır; a[1] = 5 > 2 olduğundan 5 sağa kayar ve 2c, a[1]'e yazılır. Dizi [2a, 2c, 2b, 5] olur. h = 1 turu eşit öğeleri yerinden oynatmaz. 2c, 2b'nin önüne geçmiştir.

Kod kısadır, ek bellek istemez ve orta boy dizilerde n²'li algoritmalardan çok hızlıdır. Bu üç özellik Shell sıralamasını gömülü sistemlerde ve küçük kütüphanelerde sevilen bir seçenek yapar. Verinin özellikleri biliniyorsa Shell sıralaması kova sıralamasıyla birlikte de kullanılabilir. Kovalara dağıtılan öğeler her kovada ayrıca sıralanır; bu iş için kısa ve yerinde bir algoritma uygundur.

19.8Kova sıralaması

19.8.1Fikir

Kova sıralaması (bucket sort), sayarak sıralamanın fikrini gerçel sayılara taşır. Girdinin [0, 1) aralığında n gerçel sayı olduğu ve sayıların bu aralığa düzgün dağıldığı varsayılır. Aralık n eşit parçaya, yani n kovaya bölünür. Her sayı kendi kovasına atılır. Düzgün dağılımda her kovaya ortalama bir sayı düşer. Kovalar küçük olduğu için kendi içlerinde eklemeli sıralamayla ucuza sıralanır. Son olarak kovalar sırayla birleştirilir.

Şekil 19.12, bu yöntemi 10 sayılık bir girdi üzerinde gösterir. 10 kova vardır ve her kova 0,1 genişliğindedir. x değeri ⌊10 · x⌋ numaralı kovaya gider: 0,78 → 7, 0,17 → 1, 0,39 → 3.

19.8.2C ile gerçekleme

Her kova bir bağlı listedir. Kova dizisi bu listelerin baş işaretçilerini tutar. Aşağıdaki gerçekleme dağıtma ile kova içi sıralamayı birleştirir: her sayı kovasına atılırken listede sıralı yerine eklenir. Bu, kova içi eklemeli sıralamanın ta kendisidir.

typedef struct kdugum { double x; struct kdugum *bag; } kdugum;

int bucket_sort(double a[], int n) {        /* 0 <= a[i] < 1 */
    kdugum **kova = calloc(n, sizeof *kova);
    kdugum *havuz = malloc(n * sizeof *havuz);
    if (!kova || !havuz) { free(kova); free(havuz); return -1; }
    for (int i = 0; i < n; i++) {           /* dağıt + sıralı ekle */
        kdugum **p = &kova[(int)(a[i] * n)];
        while (*p && (*p)->x <= a[i]) p = &(*p)->bag;
        havuz[i].x = a[i]; havuz[i].bag = *p; *p = &havuz[i];
    }
    int k = 0;                              /* kovaları birleştir */
    for (int b = 0; b < n; b++)
        for (kdugum *q = kova[b]; q; q = q->bag) a[k++] = q->x;
    free(kova); free(havuz);
    return 0;
}

• Satır 1. Liste düğümü: değer x ve sonraki düğüme bağ bag. Yapı kendine gönderme yapan bir struct'tır.
• Satır 4. kova, n tane kdugum * işaretçisinden oluşan bir dizidir. calloc belleği sıfırlar; bütün kovalar NULL, yani boş liste olarak başlar. malloc kullanılsaydı işaretçiler rastgele adresler taşırdı ve ilk (*p)->x okuması tanımsız davranış olurdu.
• Satır 5. Düğümler tek tek malloc ile değil, tek bir havuz dizisinden alınır. havuz[i], a[i]'nin düğümüdür. n ayrı ayırma yerine iki ayırma yapılır ve bellek tek bir free çiftiyle geri verilir. Ayırma maliyeti düşer, sızıntı riski azalır.
• Satır 6. İki ayırmadan biri başarısızsa ikisi de bırakılır. free(NULL) güvenlidir; hangisinin başarısız olduğunu ayrıca sınamaya gerek yoktur.
• Satır 8. p, bir işaretçinin işaretçisidir (kdugum **). Başlangıçta kova dizisindeki ilgili hücreyi, yani listenin baş işaretçisini gösterir. Kova numarası (int)(a[i] * n)'dir. 0 ≤ a[i] < 1 olduğundan bu sayı 0 ile n − 1 arasındadır.
• Satır 9. p, listede ilerler: gösterdiği işaretçi boş değilse ve o düğümün değeri a[i]'den küçük ya da eşitse p, o düğümün bag alanını göstermeye başlar. Döngü bittiğinde *p, yeni düğümün önüne geçeceği düğümü (ya da NULL'ı) gösterir; p ise değiştirilecek bağın adresidir.
• Satır 10. Yeni düğüm doldurulur, bağı *p'nin gösterdiği düğüme yöneltilir ve *p yeni düğümü gösterir. Ekleme tamamlanır.
• Satır 12–14. Kovalar 0'dan n − 1'e sırayla gezilir; her listenin değerleri sırayla a'ya geri yazılır.
• Satır 15. İki ayırma geri verilir. Düğümler ayrı ayrı ayrılmadığı için ayrı ayrı bırakılmaz.

İşaretçinin işaretçisi bu kodun en ince noktasıdır. Tek yıldızlı bir işaretçiyle listede gezilseydi, listenin başına ekleme özel bir durum olurdu. Başa eklenen düğüm kova dizisindeki baş işaretçiyi değiştirir. Ortaya eklenen düğüm ise önceki düğümün bag alanını değiştirir. p “değiştirilecek işaretçinin adresi”ni tuttuğu için iki durum aynı satırla yapılır. Şekil 19.13 bunu 0,23'ün eklenişinde gösterir.

Yordamın sonunda bellekteki durum Şekil 19.14'dir. Düğümler havuz dizisinde girdi sırasıyla durur: 0,12'nin düğümü havuz[7]'dir, çünkü 0,12 girdinin 7 indisindedir. Bağlar ise her kovanın içini sıralı bir zincire dizer. Bağlı listenin gücü buradadır: öğeler bellekte yer değiştirmez, yalnız bağlar değişir.

Karşılaştırma <= ile yapıldığı için eşit bir değer, listedeki eşitlerinin sonuna eklenir. Girdide önce gelen önce kalır; kova sıralaması bu gerçeklemede kararlıdır. Karşılaştırma < olsaydı yeni öğe eşitlerin önüne girerdi ve kararlılık kaybolurdu.

19.8.3Analiz

Dağıtma ve birleştirme O(n)'dir: her öğe bir kez kovaya atılır ve bir kez geri yazılır. Asıl soru, kovaların içini sıralamanın maliyetidir. Kova i'ye n_i öğe düşerse eklemeli sıralama o kovada O(n_i²) iş yapar. Toplam maliyet O(n + Σ n_i²)'dir.

Girdi düzgün dağılmışsa her öğe her kovaya 1/n olasılıkla düşer. Bu durumda bir kovanın beklenen öğe sayısı 1'dir ve n_i²'nin beklenen değeri 2 − 1/n'dir (Cormen ve arkadaşlarının kitabında kanıtlanır). n kova üzerinden toplam n · (2 − 1/n) = 2n − 1 eder. Ortalama çalışma süresi O(n)'dir.

Düzgün dağılım varsayımı bozulursa sonuç da bozulur. En kötü durumda bütün öğeler aynı kovaya düşer. Örneğin 5 sayı 0,90, 0,91, 0,92, 0,93 ve 0,94 ise ⌊5x⌋ hepsi için 4'tür. Tek kovada 5 öğe eklemeli sıralanır ve maliyet O(n²)'ye çıkar. Ek bellek kova dizisi ve düğümler için O(n)'dir; algoritma yerinde değildir.

Kova sıralaması da karşılaştırma kullanır, ama yalnız kovaların içinde. Öğenin hangi kovaya gideceği bir hesapla, ⌊n · x⌋ ile bulunur. Bu hesap, öğeyi bütün öteki öğelerle tek seferde kıyaslamak gibidir. Algoritmanın karşılaştırmalı sıralamanın alt sınırına takılmamasının nedeni budur.

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

19.9.1Karar ağacı

Seçimli, eklemeli, kabarcık ve Shell sıralaması n² ile n^3/2 arasında karşılaştırma yaptı. Daha iyisi mümkün müdür ve ne kadar iyisi? Bu soruyu bir algoritma için değil, karşılaştırmaya dayanan bütün algoritmalar için cevaplamak gerekir. Bunun aracı karar ağacıdır.

Karşılaştırmalı bir sıralama algoritması girdi hakkında bilgiyi yalnız kucuk çağrılarından edinir. Her çağrının iki sonucu vardır: evet ya da hayır. Algoritmanın bir sonraki adımı bu cevaba bağlıdır. Algoritmanın bütün olası çalışmaları bir ikili ağaç biçiminde çizilebilir. Bu ağaca karar ağacı (decision tree) denir.

• Her iç düğüm bir karşılaştırmadır (çizimde elips): “a < b?”.
• Düğümün iki çocuğu vardır: soldaki “evet” cevabının, sağdaki “hayır” cevabının ardından gelen adımdır.
• Her yaprak bir karardır (çizimde dikdörtgen): girdinin hangi dizilişte olduğu, yani öğelerin hangi sırayla yazılacağı.

Belli bir girdi için algoritma kökten başlar, her karşılaştırmanın cevabına göre sola ya da sağa iner ve bir yaprakta durur. Kökten yaprağa giden yolun uzunluğu, o girdide yapılan karşılaştırma sayısıdır. Şekil 19.15, üç öğeyi (a, b, c) sıralayan bir karar ağacını gösterir. n = 3 için 3! = 6 diziliş ve dolayısıyla 6 yaprak vardır.

Girdi a = 5, b = 8, c = 2 olsun. Kökteki soru “a < b?”'dir: 5 < 8, cevap evet. Sol çocukta “b < c?” sorulur: 8 < 2, cevap hayır, yani c, b'den önce gelmelidir. Bu noktada a < b ve c < b bilinir, ama a ile c'nin sırası bilinmez. Üçüncü soru “a < c?”'dir: 5 < 2, cevap hayır. Yaprak c < a < b'dir ve çıktı 2, 5, 8 olur. Bu girdi için 3 karşılaştırma yapıldı.

Ağacın bazı yolları daha kısadır. a < b ve b < c ise geçişme yoluyla a < c de bilinir; algoritma iki karşılaştırmayla a < b < c kararını verir. En kötü durumdaki karşılaştırma sayısı en uzun yolun uzunluğudur, yani ağacın yüksekliğidir. Bu ağacın yüksekliği 3'tür.

Her karşılaştırmalı sıralama algoritması, her n için böyle bir ağaca karşılık gelir. Eklemeli sıralamanın ağacı bir biçimdedir, seçimli sıralamanınki başka bir biçimde; ama her ağaç aynı koşulu sağlamak zorundadır. Bu koşul, alt sınırın kaynağıdır.

19.9.2Alt sınır teoremi

Daha keskin bir yaklaşım Stirling formülünden gelir:

lg(n!) = n lg n − n lg e + Θ(lg n) ≈ n lg n − 1,4427 n

Burada lg e = 1 / ln 2 ≈ 1,4427'dir. Tablo 19.15 alt sınırı, Stirling yaklaşımını ve temel algoritmaların en kötü durumunu yan yana koyar. Değerler C programında lg(n!) = lg 2 + lg 3 + … + lg n toplamıyla hesaplandı.

Küçük n'lerde Stirling yaklaşımı alt sınırın epey altında kalır, çünkü atılan Θ(lg n) terimi henüz önemlidir. n = 100'de fark 5'e iner. Tablonun son iki sütunu arasındaki uçurum da dikkat çekicidir: 100 öğe için alt sınır 525, seçimli sıralamanın yaptığı ise 4.950 karşılaştırmadır. Aradaki boşluk, daha iyi algoritmalar için yer olduğunu gösterir. Birleştirme sıralaması ve heap sort bu boşluğu kapatır: en kötü durumda O(n lg n) karşılaştırma yaparlar ve alt sınıra sabit bir çarpan kadar yakındırlar.

Teorem bundan sonraki bütün sıralama algoritmalarını karşılaştırmak için bir ölçüt, bir mihenk taşı verir. Karşılaştırmalı bir algoritma O(n lg n)'ye ulaşmışsa, mertebe bakımından daha iyisi yoktur; yalnız sabit çarpanlar ve pratik özellikler (bellek, kararlılık, önbellek dostluğu) iyileştirilebilir. Aynı sınır ortalama durum için de geçerlidir: bir karar ağacında yaprakların ortalama derinliği de en az lg(n!)'dir.

Teoremin bir varsayımı vardır: algoritma girdi hakkında bilgiyi yalnız karşılaştırmayla edinir. Sayarak, kova ve basamak sıralaması bu varsayımı çiğner. c[a[j]]++ satırı a[j]'yi başka bir öğeyle karşılaştırmaz; değerin kendisini indis olarak kullanır ve bu tek işlemle k + 1 yönlü bir karar verir. Karar ağacı ikili olmaktan çıkar ve alt sınır geçerliliğini yitirir. Doğrusal zamanın bedeli de buradan gelir: değerin indis olarak kullanılabilmesi için aralığın bilinmesi gerekir.

19.10Algoritmaları karşılaştırmak

19.10.1Aynı girdide sayım

Formüller algoritmaların büyüme hızını verir, ama sabit çarpanları ve girdinin biçimini gizler. Dört karşılaştırmalı algoritmanın aynı 1.000 öğelik girdilerde yaptığı iş Tablo 19.16'da yan yana durur. Her hücrede önce karşılaştırma, sonra taşıma sayısı yazar. Taşıma seçimli sıralamada takas, eklemeli ve Shell sıralamasında kaydırma, kabarcık sıralamasında takastır.

Sıralı ve ters sıralı sütunlar formüllerden doğrudan çıkar ve bu notun C programıyla da birebir aynı bulundu. Rastgele sütunun kendisi seçilen karıştırmaya bağlıdır. Bu notun C programı başka bir karıştırmayla şu değerleri ölçtü: eklemeli 241.305 / 240.312, erken duran kabarcık 499.247 / 240.312 (977 tur), Shell 15.218 / 7.700. Sayılar biraz farklıdır, ama ilişkiler aynıdır. İki sayımda da eklemeli sıralamanın kaydırma sayısı ile kabarcık sıralamasının takas sayısı eşittir, çünkü ikisi de girdinin evrik sayısıdır. Teoremin öngördüğü n(n − 1)/4 = 249.750 değeri her iki ölçüme de yakındır.

• Seçimli girdiye kördür: her durumda 499.500 karşılaştırma ve 999 takas yapar.
• Eklemeli sıralı girdide 999 karşılaştırmayla biter; rastgele girdide ≈ n²/4, ters girdide n²/2 karşılaştırma yapar.
• Kabarcık erken dursa bile rastgele girdide neredeyse en kötü durum kadar karşılaştırma yapar: 1.000 öğede yalnız son 20–30 tur atlanır.
• Shell rastgele girdide eklemeli sıralamaya göre karşılaştırmaları yaklaşık on altı kat, kaydırmaları otuz kattan fazla azaltır. Uzak kaydırmalar evrikleri hızla yok eder.

Sayımlar bir de süre ölçümüyle desteklenebilir. Tablo 19.17 aynı rastgele girdileri sıralamanın milisaniye cinsinden süresini verir. Süreler makineye, derleyiciye ve derleme seçeneklerine göre değişir; burada önemli olan mutlak değerler değil, n iki katına çıktığında sürenin nasıl değiştiğidir.

n her ikiye katlandığında üç temel algoritmanın süresi yaklaşık dört katına çıkar; bu, n²'li büyümenin işaretidir. Shell sıralaması ise 40.000 öğeyi 13 milisaniyede sıralar. Eklemeli sıralama, karşılaştırma sayısı seçimlininkinin yarısı olduğu için yaklaşık iki kat hızlıdır. Kabarcık sıralaması en yavaşıdır: seçimli kadar karşılaştırma yapar, üstüne eklemeli kadar taşıma yapar ve her taşıması üç atamalı bir takastır.

19.10.2Karmaşıklık özeti

Tablodaki yıldız, kova sıralamasının kararlılığının kova içinde kullanılan sıralamaya bağlı olduğunu anlatır; buradaki gerçekleme <= ile eklediği için kararlıdır. Shell sıralamasının ortalaması aralık dizisine bağlıdır ve kapalı bir formülle bilinmez. Karşılaştırmalı her algoritma için alt sınır ⌈lg n!⌉ ≈ n lg n'dir; tablodaki ilk dört satırın hiçbiri en kötü durumda bu sınıra ulaşmaz.

19.10.3Hangi durumda hangisi?

“En iyi sıralama algoritması” diye bir şey yoktur; her algoritma bir duruma uygundur. Seçim, verinin büyüklüğüne, biçimine ve pahalı olan işleme bağlıdır.

• Takas ya da yazma pahalıysa seçimli sıralama. Tam n − 1 takas yapar. Büyük tutanaklar ve flash bellek gibi yazmanın pahalı olduğu ortamlar için uygundur.
• Veri küçük ya da neredeyse sıralıysa eklemeli sıralama. Kararlıdır, yerindedir ve sıralıya yakın veride O(n)'e iner. Hızlı sıralama ve birleştirme sıralamasının pratik sürümleri küçük parçaları eklemeli sıralamaya bırakır.
• Öğretim ve sıralılık testi için kabarcık sıralaması. Erken duran sürüm bir dizinin sıralı olduğunu tek geçişte anlar. Üretim kodunda nadiren yer alır.
• Değerler küçük bir tamsayı aralığındaysa sayarak sıralama. O(n + k) ve kararlıdır. k, n'den çok büyükse bellek ve zaman boşa gider.
• Orta boy veri ve ek bellek yoksa Shell sıralaması. Birkaç satırlık kodla n²'li algoritmalardan belirgin biçimde hızlıdır.
• Veri [0, 1)'de düzgün dağılmışsa kova sıralaması. Ortalama O(n)'dir, ama dağılım bozuksa n²'ye kadar yavaşlar.

19.11Sık yapılan hatalar

1. Seçimli sıralamada en küçüğün değerini tutmak. int min = a[i]; biçiminde yalnız değer tutulursa tur sonunda en küçük öğenin yeri bilinmez ve takas yapılamaz. Takas için indis (min = j) gerekir.
2. Eklemeli sıralamada v = a[i]'yi kaydırmadan önce saklamamak. İlk kaydırma a[i]'nin üzerine yazar ve yerleştirilecek değer kaybolur.
3. Sınırı j >= 0 yazmak. Alt dizi a[L..R] sıralanıyorsa doğru sınır j >= L'dir. j >= 0, L > 0 olduğunda parçanın dışındaki öğeleri bozar.
4. if (kucuk(A, B)) SWAP(A, B); kalıbında yönü karıştırmak. Bu satır A < B ise takas eder. Küçük öğe sola gidecekse A sağdaki öğe olmalıdır: kucuk(a[j], a[j − 1]).
5. Sayarak sıralamada aralığı unutmak. Negatif ya da k'dan büyük bir değer c[]'nin dışına yazar; C bunu yakalamaz.
6. Sayarak sıralamada L4'ü soldan sağa yazmak. Dizi yine sıralanır, ama eşit öğelerin sırası tersine döner ve kararlılık kaybolur.
7. Çok deyimli makroyu yalnız süslü parantezle yazmak. if (…) SWAP(…); else … yapısında derleme hatası verir; gövde do { … } while (0) içine alınmalıdır.
8. Ortalama durumu en iyi ile en kötünün ortalaması sanmak. Erken duran kabarcık sıralamasında uçlar n − 1 ve n(n − 1)/2 karşılaştırmadır; ortalamaları ≈ n²/4 eder. Gerçek ortalama ise ≈ n²/2'dir: n = 8 için uçların ortalaması 17,5, bütün dizilişlerin ortalaması 26,0'dır. Ortalama, bütün dizilişler üzerinden alınan beklenen değerdir.

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

19.12.1Seçimli sıralamada turlar

Soru. [5, 1, 4, 2, 8] için seçimli sıralamada her tur sonundaki diziyi yazınız. Kaç takas yapıldı?

Çözüm. Tur 0'da en küçük 1'dir (min = 1); 5 ile takaslanır: [1, 5, 4, 2, 8]. Tur 1'de kalanların en küçüğü 2'dir (min = 3); 5 ile takaslanır: [1, 2, 4, 5, 8]. Tur 2'de en küçük 4 zaten a[2]'dedir; takas kendisiyledir. Tur 3'te 5 ile 8 karşılaştırılır; 5 yerindedir. Dizi dört turun sonunda [1, 5, 4, 2, 8] → [1, 2, 4, 5, 8] → [1, 2, 4, 5, 8] → [1, 2, 4, 5, 8] biçiminde ilerler. SWAP dört kez çağrılır, ama yalnız ilk ikisi gerçek takastır. Karşılaştırma sayısı her zamanki gibi 10'dur.

19.12.2Eklemeli sıralamanın iki ucu

Soru. Eklemeli sıralama [1, 2, 3, …, n] ve [n, …, 2, 1] için kaç karşılaştırma yapar?

Çözüm. Sıralı girdide her tur tek karşılaştırmayla biter: n − 1. Ters sıralı girdide i. tur i karşılaştırma yapar: 1 + 2 + … + (n − 1) = n(n − 1)/2. n = 1.000 için 999 ve 499.500.

19.12.3Erken duran kabarcık

Soru. bubble2, [1, 2, 3, 5, 4] girdisinde kaç tur çalışır?

Çözüm. 2 tur. İlk turda j = 4'te 4 < 5 doğrudur ve 5 ile 4 takaslanır; turun geri kalanında takas olmaz. Dizi sıralanmıştır, ama algoritma bunu ancak ikinci turda öğrenir: ikinci turda hiç takas olmaz ve yordam döner. Toplam 4 + 3 = 7 karşılaştırma ve 1 takas yapılır.

19.12.4Sayaç dizisi

Soru. a = [2, 5, 3, 0, 2, 3, 0, 3] ve k = 5 için sayarak sıralamanın L3 sonrası c dizisini yazınız.

Çözüm. L2 sonunda sayaçlar c = [2, 0, 2, 3, 0, 1]'dir: iki 0, hiç 1 yok, iki 2, üç 3, hiç 4 yok, bir 5. L3 bunları biriktirir: c = [2, 2, 4, 7, 7, 8]. Okuma örneği: c[3] = 7, 3'ten küçük ya da eşit yedi öğe vardır; son 3, b[6]'ya yazılır. Sıralı çıktı [0, 0, 2, 2, 3, 3, 3, 5]'tir.

19.12.5Karar ağacının yüksekliği

Soru. 3 öğe için karar ağacının en az yüksekliği nedir? 4 öğe için?

Çözüm. ⌈lg 3!⌉ = ⌈lg 6⌉ = 3 ve ⌈lg 4!⌉ = ⌈lg 24⌉ = 5. 3 öğe için Şekil 19.15'deki ağaç bu sınıra ulaşır. 4 öğe için 4 karşılaştırma yetmez: 4 karşılaştırma en çok 2⁴ = 16 farklı sonuca ayırabilir, oysa 24 diziliş vardır. 5 karşılaştırmayla 4 öğeyi sıralayan algoritmalar vardır.

19.12.6Seçimli sıralamanın kararsızlığı

Soru. Seçimli sıralamanın kararsız olduğunu gösteren en küçük örneği bulunuz.

Çözüm. İki öğe yetmez: iki öğeli bir dizide eşit anahtarlar takaslanmaz, farklı anahtarlar için kararlılık sorusu yoktur. Üç öğeli [2a, 2b, 1] yeter. İlk turda en küçük 1'dir ve a[0]'daki 2a ile takaslanır: [1, 2b, 2a]. İkinci turda kucuk(2a, 2b) yanlıştır ve takas kendisiyledir. Sonuç [1, 2b, 2a]'dır: 2b, 2a'nın önüne geçmiştir. Uzak takas 2a'yı 2b'nin üzerinden atlatmıştır.

19.13Özet

• Sıralama, tutanakları anahtarlarına göre düzenler. İç sıralamada veri bellektedir; dış sıralamada maliyeti disk erişimleri belirler.
• Kararlı bir algoritma eşit anahtarlı tutanakların göreli sırasını korur; birden çok alana göre sıralama ve basamak sıralaması buna dayanır. Yerinde bir algoritma O(1) ek bellek kullanır.
• kucuk ve SWAP makroları algoritmaları tür ve ölçütten bağımsız yazmayı sağlar; çok deyimli makro do { … } while (0) içinde yazılır.
• Seçimli sıralama girdiye kördür: her durumda n(n − 1)/2 karşılaştırma ve n − 1 takas. Uzak takas yüzünden kararsızdır.
• Eklemeli sıralama sıralı girdide n − 1, ters sıralı girdide n(n − 1)/2 karşılaştırma yapar. Ortalaması bütün n! diziliş üzerinden (n² + 3n)/4 − H_n ≈ n²/4'tür; en iyi ile en kötünün ortalaması değildir. Kararlı ve yerindedir. Bekçili sürüm iç döngüdeki sınır sınamasını kaldırır.
• Kabarcık sıralaması komşuları takaslar; kararlıdır. Erken duran sürüm sıralı girdide O(n)'dir, ama ortalamada yine ≈ n²/2 karşılaştırma yapar.
• Evrik, ters duran çifttir. Komşu takası ya da tek konumluk kaydırma tam bir evrik giderir; rastgele dizide ortalama n(n − 1)/4 evrik olduğu için bu tür her algoritma ortalamada Ω(n²)'dir.
• Sayarak sıralama karşılaştırma yapmaz; O(n + k) zamanda ve O(n + k) ek bellekle çalışır. Yerleştirme sağdan sola yapıldığı için kararlıdır. Aralık büyükse yararsızdır.
• Shell sıralaması azalan aralıklarla eklemeli sıralama yapar; son tur h = 1 doğruluğu garanti eder. Uzak kaydırmalar evrikleri hızla giderir. Hız aralık dizisine bağlıdır; yerindedir, kararsızdır.
• Kova sıralaması [0, 1)'de düzgün dağılmış veride ortalama O(n)'dir; bütün öğeler tek kovaya düşerse O(n²)'ye çıkar. C gerçeklemesi işaretçinin işaretçisiyle sıralı ekleme yapar ve düğümleri tek bir havuzdan alır.
• Karşılaştırmalı her sıralama bir karar ağacıdır. Ağacın en az n! yaprağı olduğundan yüksekliği en az ⌈lg n!⌉ = Θ(n lg n)'dir. Bu sınır ileri sıralama algoritmalarının ölçütüdür; karşılaştırma yapmayan algoritmalar ona takılmaz.

19.14Kavram listesi

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

• sıralama sorting
• tutanak record
• anahtar key
• kararlı stable (sort)
• yerinde sıralama in-place sort
• makro macro
• seçimli sıralama selection sort
• eklemeli sıralama insertion sort
• değişmez invariant
• bekçi sentinel
• permütasyon permutation
• kabarcık sıralaması bubble sort
• evrik inversion
• sayarak sıralama counting sort
• basamak sıralaması radix sort
• Shell sıralaması Shell sort
• kova bucket
• kova sıralaması bucket sort
• karar ağacı decision tree
• alt sınır lower bound
• bellek sızıntısı memory leak

19.15Kendini Dene

1. selection yordamı [3, 1, 2] dizisinde kaç karşılaştırma ve kaç gerçek takas yapar? Her turun sonundaki dizi nedir?

   Cevap

   3 karşılaştırma ve 2 takas. Tur 0'da en küçük 1'dir: [1, 3, 2]. Tur 1'de 2 < 3'tür ve takas yapılır: [1, 2, 3]. İki takas da gerçektir.

2. [4, 1, 3, 2] dizisinin evrik sayısı kaçtır? insertion bu diziyi kaç kaydırma ve kaç karşılaştırmayla sıralar?

   Cevap

   4 evrik: (4, 1), (4, 3), (4, 2), (3, 2). Kaydırma sayısı evrik sayısına eşittir: 4. Karşılaştırma 6'dır: i = 1'de 1 (1 başa gider), i = 2'de 2, i = 3'te 3.

3. bubble2, [5, 1, 2, 3, 4] ve [2, 3, 4, 5, 1] dizilerinde kaçar tur döner? İki dizinin evrik sayısı aynı olduğu hâlde neden fark vardır?

   Cevap

   Birincide 4 tur, ikincide 2 tur. İç döngü sağdan sola ilerlediği için küçük bir öğe tek turda en sola gidebilir, ama büyük bir öğe her turda yalnız bir konum sağa ilerler. [5, 1, 2, 3, 4]'te 5'in sona varması dört tur ister.

4. counting_sort, a = [1, 0, 1, 2] ve k = 2 ile çağrılıyor. L3 sonunda c nedir? a[0]'daki 1 çıktıda hangi indise yazılır?

   Cevap

   c = [1, 3, 4]. L4 sağdan sola gezer: a[3] = 2 → b[3], a[2] = 1 → b[2], a[1] = 0 → b[0], a[0] = 1 → b[1]. Girdide önce gelen 1 çıktıda da öndedir; algoritma kararlıdır.

5. Eklemeli sıralamada beşinci öğe (j = 4) yerleştirilirken beklenen karşılaştırma sayısı kaçtır?

   Cevap

   E(C₄) = (4 + 2)/2 − 1/5 = 2,8. Beş durumun karşılaştırma sayıları 1, 2, 3, 4 ve 4'tür; ortalamaları 14/5 = 2,8.

6. 5 öğeyi sıralayan karşılaştırmalı bir algoritma en kötü durumda en az kaç karşılaştırma yapmak zorundadır? Seçimli sıralama kaç yapar?

   Cevap

   ⌈lg 5!⌉ = ⌈lg 120⌉ = ⌈6,91⌉ = 7. Seçimli sıralama her girdide 10 karşılaştırma yapar; alt sınırın üç fazlası.

7. bucket_sort, n = 5 ve girdi 0,94, 0,93, 0,92, 0,91, 0,90 ile çağrılıyor. Kovalara nasıl dağılır ve bu girdi neden kötüdür?

   Cevap

   ⌊5x⌋ beş sayının hepsi için 4'tür; hepsi 4 numaralı kovaya düşer. Sayılar azalan sırada geldiği için her yeni sayı listenin başına girer, ama while döngüsü her seferinde yalnız bir karşılaştırma yapar. Girdi artan sırada gelseydi her ekleme bütün listeyi gezerdi. Tek kovaya düşen n öğe için en kötü durum O(n²)'dir; düzgün dağılım varsayımı bozulmuştur.

8. shell_sort 10 öğelik bir dizide hangi aralıkları kullanır? Son aralık neden her zaman 1'dir ve bu neden önemlidir?

   Cevap

   5, 2, 1. Aralık her adımda tamsayı bölmesiyle yarıya iner ve 1'e varmadan 0 olamaz: h = 1 iken bir sonraki değer 0'dır ve döngü biter. h = 1 turu tam bir eklemeli sıralamadır; önceki turlar ne yapmış olursa olsun diziyi sıralar. Algoritmanın doğruluğu bu son turdan gelir.

19.16İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Bölüm 7. Sıralama kavramları, eklemeli sıralamanın analizi ve karar ağacı bu kaynağın düzenini izler.
• R. Sedgewick, Algorithms in C, Parts 1–4, 3. baskı, Bölüm 6. kucuk ve SWAP makrolarıyla yazılmış temel sıralama algoritmaları, bekçili eklemeli sıralama ve Shell sıralamasının aralık dizileri ayrıntılı deneylerle tartışılır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, Bölüm 2 ve 8. Eklemeli sıralamanın döngü değişmeziyle doğruluk kanıtı, sayarak ve kova sıralaması, kova sıralamasının ortalama durum analizi ve alt sınır teoremi.
• D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2. baskı, Kesim 5.2. Evriklerin, Shell sıralamasının ve h-sıralı dizilerin derinlemesine incelemesi; bu konuların başvuru kaynağı.

19.17Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. bs., Silicon Press, 2008. Bölüm 7, Sorting.
2. R. Sedgewick, Algorithms in C, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching, 3. bs., Addison-Wesley, 1998. Bölüm 6, Elementary Sorting Methods.
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. bs., MIT Press, 2022. Bölüm 2 (Getting Started) ve Bölüm 8 (Sorting in Linear Time).
4. D. L. Shell, “A High-Speed Sorting Procedure”, Communications of the ACM, 2(7), 30–32, 1959.
5. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2. bs., Addison-Wesley, 1998.

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