Sıralama I: bubble, selection, insertion

Sıralama (sorting), bilgisayar bilimlerinin en çok çalışılan problemidir: veriyi sıralarsan arama O(log n)‘e düşer, tekrarlar yan yana gelir, en küçük/en büyük hemen bulunur. Bu hafta üç basit algoritma var. Üçü de O(n²) ve büyük veride yavaş, ama mantıkları sezgisel ve sınavda geçiş geçiş iz istenir. Bir sonraki hafta O(n log n) algoritmalara geçeceğiz.

Altın kurallar:

1. Bubble: her geçişte en büyük eleman sona “kabarcıklanır”.
2. Selection: her geçişte kalan kısmın en küçüğü başa seçilir.
3. Insertion: her geçişte bir sonraki eleman, soldaki sıralı kısımda doğru yerine sokulur.
4. “Pass” tanımına dikkat. Bu sayfada geçiş = dış döngünün bir turu.

Bubble sort

Komşu iki elemanı karşılaştır; soldaki büyükse takas et. Bir geçiş boyunca en büyük eleman, köpük gibi en sona çıkar. Sonraki geçişin son elemana bakmasına gerek yoktur.

static void bubbleSort(int[] a) {
    int n = a.length;
    for (int pass = 1; pass < n; pass++) {
        boolean swapped = false;
        for (int j = 0; j < n - pass; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break;   // takas yoksa dizi sıralı
    }
}

{7, 3, 9, 1, 5} üzerinde her geçişten sonra:

pass 1: [3, 7, 1, 5, 9]
pass 2: [3, 1, 5, 7, 9]
pass 3: [1, 3, 5, 7, 9]
pass 4: [1, 3, 5, 7, 9]
comps=10 swaps=6 inversions(orig)=6

Geçiş 1’in içi, karşılaştırma karşılaştırma:

[7, 3, 9, 1, 5]   7 > 3 takas  → [3, 7, 9, 1, 5]
                  7 < 9        → değişiklik yok
                  9 > 1 takas  → [3, 7, 1, 9, 5]
                  9 > 5 takas  → [3, 7, 1, 5, 9]   9 yerine oturdu

Geçiş 3’te dizi sıralı hale geldi, ama o geçişte bir takas yapıldığı için algoritma bunu bilemez; geçiş 4 takassız biter ve durur.

Ters çevrim (inversion): i < j iken a[i] > a[j] olan çift. Her komşu takas tam olarak bir ters çevrimi düzeltir; bu yüzden bubble sort’un takas sayısı = ters çevrim sayısı.

Selection sort

Kalan kısmı tara, en küçüğün indeksini bul, onu kalan kısmın başıyla takas et. Baştaki kısım her geçişte bir büyür ve nihai haldedir.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++)
            if (a[j] < a[min]) min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;
    }
}

{38, 12, 45, 7, 29, 16}:

pass 1: [7, 12, 45, 38, 29, 16]
pass 2: [7, 12, 45, 38, 29, 16]
pass 3: [7, 12, 16, 38, 29, 45]
pass 4: [7, 12, 16, 29, 38, 45]
pass 5: [7, 12, 16, 29, 38, 45]
comps=15 swaps=3

Geçiş 2 ve 5’te en küçük zaten yerindeydi, gerçek takas olmadı (sayaçta sadece min != i olan takaslar sayıldı). Karşılaştırma sayısı girdiden bağımsız: her zaman $\frac{n(n-1)}{2}$. Sıralı bir dizi verdiğinde de 15 karşılaştırma yapar.

TUZAK · Selection sort erken duramaz. Bubble’daki bayrak fikri burada işe yaramaz; minimumu bulmak için kalan kısmın hepsini taramak zorundasın. En iyi durum da O(n²).

Insertion sort

Kart oyununda elindeki kartları dizer gibi: her yeni kartı alır, soldaki sıralı kartların arasında doğru yere sokarsın. Büyük kartlar bir sağa kayar.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];   // kaydır
            j--;
        }
        a[j + 1] = key;
    }
}

{38, 12, 45, 7, 29, 16}:

pass 1: [12, 38, 45, 7, 29, 16]
pass 2: [12, 38, 45, 7, 29, 16]
pass 3: [7, 12, 38, 45, 29, 16]
pass 4: [7, 12, 29, 38, 45, 16]
pass 5: [7, 12, 16, 29, 38, 45]
comps=12 shifts=9 inversions=9

Geçiş 3’ün içi (key = 7):

[12, 38, 45, 7, 29, 16]   key = 7
45 > 7 → kaydır    [12, 38, 45, 45, 29, 16]
38 > 7 → kaydır    [12, 38, 38, 45, 29, 16]
12 > 7 → kaydır    [12, 12, 38, 45, 29, 16]
j = -1, dur        [7, 12, 38, 45, 29, 16]

Insertion sort uyarlanabilir (adaptive): dizi ne kadar sıralıysa o kadar hızlı. Sıralı dizide n − 1 karşılaştırma, ters sıralıda $\frac{n(n-1)}{2}$:

insertion sorted: comps=5 shifts=0
insertion reverse: comps=15 shifts=15

Geçişten algoritmayı tanımak

Sınavda bazen ara durum verilip “hangi algoritma?” diye sorulur. Aynı girdi {4, 2, 6, 1, 3}, ilk geçişten sonra:

Kararlılık (stability)

Eşit anahtarlı elemanların sıralamadan sonra orijinal sıralarını koruması. Önce isme göre sıralı bir öğrenci listesini nota göre sıraladığında, aynı notu alanlar isme göre sıralı kalsın istersin; bu ancak kararlı bir algoritmayla olur.

Anahtarları 3, 3, 1 olan kayıtlar (harfler orijinal sırayı gösteriyor):

selection [1, 3b, 3a] insertion [1, 3a, 3b] bubble [1, 3a, 3b]

Selection sort uzak takas yapar: 1’i başa getirirken 3a’yı en sona fırlatır ve 3b’nin önünden atlatır. Bubble ve insertion sadece komşuları ve sadece kesin büyükse (>) yer değiştirir, eşitler birbirini geçmez.

Karşılaştırma tablosu

Rastgele dizilerde karşılaştırma sayısı (n her seferinde iki kat):

n=1000 bubble comps=498275 selection comps=499500 insertion comps=245712
n=2000 bubble comps=1996855 selection comps=1999000 insertion comps=985303
n=4000 bubble comps=7996674 selection comps=7998000 insertion comps=3980580

Hepsi x4 büyüyor: karesel. Insertion sort ortalamada diğerlerinin yarısı kadar karşılaştırma yapıyor, çünkü her eleman sıralı kısmın ortalama yarısında durur.

Sık yapılan hatalar

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];   // büyükleri sağa kaydır
            j--;
        }
        a[j + 1] = key;        // boşluğa yerleştir
    }
}

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++)
            if (a[j] < a[min]) min = j;
        int t = a[i];
        a[i] = a[min];
        a[min] = t;
    }
}