Hafta 10 — Sıralama¶

CEN207 Veri Yapıları (eski adıyla CE205) · 2026–2027 Güz

Sunumun içine tıklayıp ok tuşlarıyla ilerleyin; tam ekran için sunumun sağ altındaki düğmeyi ya da yukarıdaki "Sunumu tam ekran aç" bağlantısını kullanın.

0. Başlamadan önce¶

0.1 Zaten bildikleriniz¶

Önceki haftalardan iki şey bugün en çok önem taşıyor.

Hafta 1'den — diziler ve Big-O. Bu haftaki her algoritma düz bir dizi üzerinde çalışır, arr[i] Hafta 1'de öğrendiğiniz gibi O(1)'de erişilir. Ve bu haftaki her algoritma Big-O karmaşıklığıyla tanımlanır — en iyi durum, ortalama durum ve en kötü durum akademik süsleme değildir; on bir farklı sıralama algoritmasının var olmasının tam nedenidir. O(n), O(n log n) ve O(n²) sizin için henüz otomatik değilse, bu hafta onları otomatik hale getirecek, çünkü aynı girdinin farklı algoritmalar altında önünüzde yazılı sayılarla ne kadar farklı karşılaştırma sayıları ürettiğini izleyeceksiniz.

Hafta 4'ten — öbek sıralaması, ilk O(n log n) yerinde sıralamanız. Zaten tam bir ikili öbek kurdunuz, zaten sift_down yazdınız, ve zaten onu kullanarak bir diziyi O(n log n) sürede, yerinde, köke tekrar tekrar küçülen öbeğin sınırına taşıyarak sıraladınız. Öbek sıralaması bu hafta kendi bölümünü almayacak — onu zaten hak ettiniz — ama aklınızda bir ölçüt olarak tutun: birleştirmeli sıralama O(n) ek bellek pahasına öbek sıralamasının O(n log n) garantisini eşler (öbek sıralaması hiç ek bellek gerektirmiyordu); hızlı sıralama bunu yalnızca ortalamada eşler ama en kötü durumda O(n²)'ye düşebilir (öbek sıralaması asla düşmez); ve kabarcık, seçmeli ya da eklemeli sıralamanın hiçbiri büyük girdilerde ona yaklaşamaz (öbek sıralaması n yeterince büyüdüğünde onları her zaman geçer).

Gerçekten yeni bir fikir, iki kez. Hem birleştirmeli hem hızlı sıralama böl ve yönet'i (divide and conquer) tanıtır: problemi daha küçük parçalara böl, her parçayı aynı şekilde (özyinelemeli olarak) çöz, sonra sonuçları birleştir. Bu fikir bu dersin ve bir sonrakinin geri kalanında sürekli tekrar karşınıza çıkacak. Ve sayma sıralaması, radix sıralaması ve kova sıralaması şimdiye kadar hiçbir sıralamada görmediğiniz bir şey tanıtır: anahtarları hiç karşılaştırmamak. Hafta 1'den (doğrusal ve ikili aramanın sıralı bir dizi varsaydığını hatırlayın — o sırayı önce birinin üretmesi gerekiyordu) kabarcık, seçmeli, eklemeli, shell, birleştirmeli ve hızlı sıralamaya kadar her sıralama, iki anahtarı < ya da > ile karşılaştırarak sırayı belirler. Ünlü, kanıtlanmış bir alt sınır vardır — hiçbir karşılaştırmalı sıralama, bu türden herhangi bir algoritma için, en kötü durumda O(n log n)'den daha iyisini asla garanti edemez; bu haftaki bir alıştırmada bunu kendiniz kanıtlayacaksınız. Sayma, radix ve kova sıralaması bu sınırı, karşılaştırma oyununu oynamayı reddederek aşar: değerlerin kendisini adres olarak kullanırlar — hash'lemeye O(1) ortalama durumu veren "aramak yerine konumu hesapla" fikrinin tıpkısı.

0.2 Bu haftanın haritası¶

flowchart TD
    W10["Hafta 10: Sıralama"]
    W10 --> S["Karşılaştırmalı, O(n^2) ailesi"]
    S --> S1["Kabarcık sıralaması: bitişik yer değiştirme, erken çıkış"]
    S --> S2["Seçmeli sıralama: minimumu bul, az yer değiştirme"]
    S --> S3["Eklemeli sıralama: sıralı önek büyüt, kaydır"]
    S --> S4["Shell sıralaması: küçülen aralıklı eklemeli sıralama"]
    W10 --> DC["Böl ve yönet: garantili O(n log n)"]
    DC --> M1["Birleştirmeli sıralama, yukarıdan aşağı: böl, özyinele, birleştir"]
    DC --> M2["Birleştirmeli sıralama, aşağıdan yukarı: büyüyen parçaları birleştir, özyineleme yok"]
    W10 --> Q["Hızlı sıralama: ortalama O(n log n), yerinde"]
    Q --> Q1["Lomuto bölümleme: pivot = son eleman"]
    Q --> Q2["Hoare bölümleme: pivot = ilk eleman, iki tarama"]
    Q --> Q3["En kötü durum: kötü pivot seçimi O(n^2) verir"]
    W10 --> NC["Karşılaştırmasız sıralamalar: O(n log n) alt sınırını aşar"]
    NC --> N1["Sayma sıralaması: tekrar sayısı say, O(n + k)"]
    NC --> N2["Radix sıralaması (LSD): basamak başına sayma sıralaması"]
    NC --> N3["Kova sıralaması: dağıt, küçük kovaları sırala, birleştir"]
    W10 --> ST["Kararlılık: eşit anahtarlar girdi sırasını korur mu?"]
    W10 --> CH["Sıralama seçmek: tek kazanan yok, girdiye bağlı"]

Aşağıdaki her kutu kendi bölümünü alır, çoğu adım adım bir animasyon, tam bir C ve Java programı, ve karmaşıklık ile sık yapılan hatalar üzerine bir not içerir.

1. Sıralama problemi, ve onu ölçme yöntemi¶

1.1 Problem, yeniden ifade edilmiş¶

n değerlik bir dizi ve bir karşılaştırma kuralı ("a, b'den küçük mü?") verildiğinde, diziyi her eleman kendinden sonrakine eşit ya da ondan küçük olacak şekilde yeniden düzenleyin. Bu tek cümle, bilgisayarlığın tarihi boyunca düzinelerce farklı algoritma üretti, çünkü "diziyi yeniden düzenle" nasıl sorusuna muazzam bir alan bırakır: ne kadar ek bellek kullanmanıza izin var, sıradaki hangi çifti karşılaştıracağınıza nasıl karar veriyorsunuz, girdi hakkında zaten bildiğiniz bir şeyi kullanıyor musunuz (zaten çoğunlukla sıralı mı? hepsi küçük tam sayı mı? hepsi eşit olasılıklı mı?), ve "eşit" elemanların göreli sırasını değiştirmesine izin var mı.

1.2 Maliyeti ölçmek: karşılaştırmalar ve taşımalar¶

Bu haftaki her algoritma, hem animasyonlarda hem programlarda, aynı girdi üzerinde iki şeyi sayacak şekilde donatılmıştır:

Bu iki sayı her zaman hangi algoritmanın "kazandığı" konusunda hemfikir olmaz: seçmeli sıralama (bölüm 3) her seferinde aynı sayıda karşılaştırma yapar ama bu haftaki en az yer değiştirmeyi yapar; sayma, radix ve kova sıralaması tasarım gereği sıfır anahtar-anahtar karşılaştırması yapar, çünkü tekrar sayısını saymak karşılaştırmak değildir. Bölüm 12'nin sorting-comparison animasyonu, tam olarak bu iki sayının nasıl ayrıştığını görebilmeniz için beş algoritmayı aynı girdi üzerinde yan yana koyar.

1.3 Kararlılık (stability)¶

Bir sıralama, eşit anahtarlı iki eleman çıktıda özgün göreli sırasını koruyorsa kararlıdır (stable). Zaten isme göre sıralı bir öğrenci tablosunu, şimdi nota göre sıraladığınızı düşünün: kararlı bir sıralama her aynı-not grubunu isim sırasında bırakır (çünkü girişte o sıradaydılar); kararsız bir sıralama onları karıştırabilir. Kararlılık doğrulukla ilgili değildir — kararsız bir sıralamanın çıktısı istediğiniz anahtara göre yine de "doğru sıralanmıştır" — bazı algoritmaların size ücretsiz verdiği, bazılarının vermediği ek bir garantidir. Bölüm 11 bunu özel bir animasyonla somutlaştırır: aynı girdi, aynı anahtara göre sıralanır ve yalnızca hangi algoritmanın sıraladığına bağlı olarak iki farklı etiket sırası üretir.

1.4 Yerinde (in-place) mi, ek bellek mi¶

Bir algoritma, girdi dizisini yalnızca O(1) ek bellek (birkaç geçici değişken) kullanarak yeniden düzenliyorsa, n ile orantılı ikinci bir dizi hiç kullanmıyorsa yerinde (in-place) sıralar. Kabarcık, seçmeli, eklemeli, shell ve hızlı sıralamanın hepsi yerindedir. Birleştirmeli sıralama, bölüm 6'da göreceğiniz gibi, birleştirme adımı için n büyüklüğünde bir yardımcı dizi gerektirir — bu, garantili O(n log n)'i için ödediği bedeldir. Sayma sıralaması ve radix sıralaması da ek diziler gerektirir (bir output[] dizisi ve küçük bir count[] dizisi). Her algoritmayla karşılaştıkça hem zaman karmaşıklığını hem alan karmaşıklığını aklınızda tutun; "en iyi" sıralama her zaman ikisi arasında bir ödünleşimdir — tam olarak bu yüzden bölüm 13 haftayı tek bir kazananla değil bir karar tablosuyla bitirir.

2. Kabarcık sıralaması (bubble sort)¶

2.1 Başlangıç sorusu¶

Bir kitap rafını elle sıralamanız gerekseydi, çok doğal bir içgüdü şu olurdu: ilk ikisini karşılaştır, sırası yanlışsa yer değiştir, sonra sıradaki ikisini karşılaştır, ve böyle rafın sonuna kadar devam et — sonra bu tüm taramayı tekrar yap, tekrar yap, ta ki bir tam tarama hiçbir şeyi değiştirmeyene kadar. Bu içgüdü tam olarak kabarcık sıralamasıdır. Hızlı sıralama ya da birleştirmeli sıralamanın aksine tek bir adı geçen mucidi ve net bir doğuş tarihi yoktur; bilgisayarlık literatüründe 1950'lerin ortasından itibaren görünen en eski ve en basit sıralama fikirlerinden biridir ve genellikle icat etmek için hiç zekâ gerektirmediği için — yalnızca ne zaman durulacağını bilme disiplini gerektirdiği için — ilk öğretilen sıralamadır.

2.2 Fikir: bitişik yer değiştirmeler, erken çıkışla¶

Diziyi soldan sağa yürüyün. Her konumda, geçerli elemanı komşusuyla karşılaştırın; sırası yanlışsa yer değiştirin. Bu tek tarama sona ulaştığında, en büyük eleman son konuma kadar itilmiş ("kabarcıklanmış") olur — taramanın daha büyük bir eleman bulduğu her adım onu bir hücre daha sağa taşır. Tüm taramayı tekrarlayın, ama her seferinde bir hücre daha kısa (kuyruk zaten yerleşmiştir). Kabarcık sıralamasını öğretmeye değer kılan tek incelik: bir tarama sırasında herhangi bir yer değiştirme olup olmadığını izleyin. Bir tarama sıfır yer değiştirme yaparsa, dizi zaten sıralıdır — kalan taramalar için boşuna uğraşmak yerine hemen durun.

2.3 Bellekte, ve kod¶

bubble_sort aşağıda comparisons (karşılaştırmalar) ve swaps (yer değiştirmeler) sayaçlarını iki int * üzerinden izler — animasyonun sağda gösterdiği aynı iki sayı, böylece kendi elle-izleme sonucunuzu hem resimle hem kodla karşılaştırabilirsiniz.

void bubble_sort(int a[], int n, int *comparisons, int *swaps) {
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;
        for (int i = 0; i < n - 1 - pass; i++) {
            (*comparisons)++;
            if (a[i] > a[i + 1]) {
                int tmp = a[i]; a[i] = a[i + 1]; a[i + 1] = tmp;
                (*swaps)++;
                swapped = 1;
            }
        }
        if (!swapped) break;      /* zaten sıralı: erken çıkış */
    }
}

void bubbleSort(int[] a, int n) {
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;
        for (int i = 0; i < n - 1 - pass; i++) {
            if (a[i] > a[i + 1]) {
                int tmp = a[i]; a[i] = a[i + 1]; a[i + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;      // zaten sıralı: erken çıkış
    }
}

Seçicide ayrıca zaten sıralı — tek taramada erken çıkış (tek bir taramadan sonra durduğunu izleyin) ve tersten sıralı (en kötü durum: hiçbir zaman erken çıkış mümkün değildir) örneklerini deneyin, ya da dört zorluk seviyesinde rastgele veri için 🎲'e basın, ya da kendi diziniz yazın.

2.4 Deneyin¶

/* Week 10 -- Sorting
 * Bubble sort with early exit: repeatedly walk the array, swapping adjacent
 * out-of-order pairs; a pass with zero swaps means the array is already
 * sorted and the algorithm stops early. Prints the array after every pass
 * and the total comparisons/swaps.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>

static void print_array(const int a[], int n) {
    printf("[");
    for (int i = 0; i < n; i++) printf("%d%s", a[i], i + 1 < n ? ", " : "");
    printf("]\n");
}

void bubble_sort(int a[], int n, int *comparisons, int *swaps) {
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;
        for (int i = 0; i < n - 1 - pass; i++) {
            (*comparisons)++;
            if (a[i] > a[i + 1]) {
                int tmp = a[i]; a[i] = a[i + 1]; a[i + 1] = tmp;
                (*swaps)++;
                swapped = 1;
            }
        }
        printf("  pass %d: ", pass + 1);
        print_array(a, n);
        if (!swapped) { printf("  no swaps this pass -> early exit\n"); break; }
    }
}

static void run_scenario(const char *label, int a[], int n) {
    printf("-- %s --\n", label);
    printf("before: ");
    print_array(a, n);
    int comparisons = 0, swaps = 0;
    bubble_sort(a, n, &comparisons, &swaps);
    printf("after:  ");
    print_array(a, n);
    printf("total: %d comparisons, %d swaps\n\n", comparisons, swaps);
}

int main(void) {
    int normal[] = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
    int hard[] = {40, 11, 27, 8, 33, 16, 45, 2, 19, 37, 24, 6, 50, 29};
    int already_sorted[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int reverse_sorted[] = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    run_scenario("normal: 10 unordered values", normal, 10);
    run_scenario("hard: 14 values, needs many passes", hard, 14);
    run_scenario("edge: already sorted -- early exit after one pass", already_sorted, 12);
    run_scenario("edge: reverse sorted -- worst case, no early exit", reverse_sorted, 12);

    return 0;
}

/* Week 10 -- Sorting
 * Bubble sort with early exit: repeatedly walk the array, swapping adjacent
 * out-of-order pairs; a pass with zero swaps means the array is already
 * sorted and the algorithm stops early. Prints the array after every pass
 * and the total comparisons/swaps.
 * CEN207 Data Structures (formerly CE205)
 */
public class BubbleSort {
    static int comparisons, swaps;

    static void printArray(int[] a) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < a.length; i++) { sb.append(a[i]); if (i + 1 < a.length) sb.append(", "); }
        sb.append(']');
        System.out.println(sb);
    }

    static void bubbleSort(int[] a) {
        int n = a.length;
        for (int pass = 0; pass < n - 1; pass++) {
            boolean swapped = false;
            for (int i = 0; i < n - 1 - pass; i++) {
                comparisons++;
                if (a[i] > a[i + 1]) {
                    int tmp = a[i]; a[i] = a[i + 1]; a[i + 1] = tmp;
                    swaps++;
                    swapped = true;
                }
            }
            System.out.print("  pass " + (pass + 1) + ": ");
            printArray(a);
            if (!swapped) { System.out.println("  no swaps this pass -> early exit"); break; }
        }
    }

    static void runScenario(String label, int[] a) {
        System.out.println("-- " + label + " --");
        System.out.print("before: ");
        printArray(a);
        comparisons = 0; swaps = 0;
        bubbleSort(a);
        System.out.print("after:  ");
        printArray(a);
        System.out.println("total: " + comparisons + " comparisons, " + swaps + " swaps");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normal = {5, 2, 9, 1, 7, 3, 8, 4, 6, 0};
        int[] hard = {40, 11, 27, 8, 33, 16, 45, 2, 19, 37, 24, 6, 50, 29};
        int[] alreadySorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int[] reverseSorted = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

        runScenario("normal: 10 unordered values", normal);
        runScenario("hard: 14 values, needs many passes", hard);
        runScenario("edge: already sorted -- early exit after one pass", alreadySorted);
        runScenario("edge: reverse sorted -- worst case, no early exit", reverseSorted);
    }
}

Deneyin

gcc -std=c11 -Wall -Wextra -o /tmp/x bubble_sort.c && /tmp/x

-- normal: 10 unordered values --
before: [5, 2, 9, 1, 7, 3, 8, 4, 6, 0]
  pass 1: [2, 5, 1, 7, 3, 8, 4, 6, 0, 9]
  pass 2: [2, 1, 5, 3, 7, 4, 6, 0, 8, 9]
  pass 3: [1, 2, 3, 5, 4, 6, 0, 7, 8, 9]
  pass 4: [1, 2, 3, 4, 5, 0, 6, 7, 8, 9]
  pass 5: [1, 2, 3, 4, 0, 5, 6, 7, 8, 9]
  pass 6: [1, 2, 3, 0, 4, 5, 6, 7, 8, 9]
  pass 7: [1, 2, 0, 3, 4, 5, 6, 7, 8, 9]
  pass 8: [1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
  pass 9: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
total: 45 comparisons, 25 swaps

-- hard: 14 values, needs many passes --
before: [40, 11, 27, 8, 33, 16, 45, 2, 19, 37, 24, 6, 50, 29]
  pass 1: [11, 27, 8, 33, 16, 40, 2, 19, 37, 24, 6, 45, 29, 50]
  pass 2: [11, 8, 27, 16, 33, 2, 19, 37, 24, 6, 40, 29, 45, 50]
  pass 3: [8, 11, 16, 27, 2, 19, 33, 24, 6, 37, 29, 40, 45, 50]
  pass 4: [8, 11, 16, 2, 19, 27, 24, 6, 33, 29, 37, 40, 45, 50]
  pass 5: [8, 11, 2, 16, 19, 24, 6, 27, 29, 33, 37, 40, 45, 50]
  pass 6: [8, 2, 11, 16, 19, 6, 24, 27, 29, 33, 37, 40, 45, 50]
  pass 7: [2, 8, 11, 16, 6, 19, 24, 27, 29, 33, 37, 40, 45, 50]
  pass 8: [2, 8, 11, 6, 16, 19, 24, 27, 29, 33, 37, 40, 45, 50]
  pass 9: [2, 8, 6, 11, 16, 19, 24, 27, 29, 33, 37, 40, 45, 50]
  pass 10: [2, 6, 8, 11, 16, 19, 24, 27, 29, 33, 37, 40, 45, 50]
  pass 11: [2, 6, 8, 11, 16, 19, 24, 27, 29, 33, 37, 40, 45, 50]
  no swaps this pass -> early exit
after:  [2, 6, 8, 11, 16, 19, 24, 27, 29, 33, 37, 40, 45, 50]
total: 88 comparisons, 42 swaps

-- edge: already sorted -- early exit after one pass --
before: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  pass 1: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  no swaps this pass -> early exit
after:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
total: 11 comparisons, 0 swaps

-- edge: reverse sorted -- worst case, no early exit --
before: [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
  pass 1: [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 12]
  pass 2: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 11, 12]
  pass 3: [9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 11, 12]
  pass 4: [8, 7, 6, 5, 4, 3, 2, 1, 9, 10, 11, 12]
  pass 5: [7, 6, 5, 4, 3, 2, 1, 8, 9, 10, 11, 12]
  pass 6: [6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12]
  pass 7: [5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 11, 12]
  pass 8: [4, 3, 2, 1, 5, 6, 7, 8, 9, 10, 11, 12]
  pass 9: [3, 2, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  pass 10: [2, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  pass 11: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
after:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
total: 66 comparisons, 66 swaps

javac -Xlint:all -d /tmp/j BubbleSort.java && java -cp /tmp/j BubbleSort

2.5 Karmaşıklık, hatalar, kendini sına¶

Karmaşıklık. En iyi durum O(n) (zaten sıralı: tek tarama, n-1 karşılaştırma, erken çıkış hemen tetiklenir). En kötü durum ve ortalama durum ikisi de O(n²) (tersten sıralı ya da rastgele girdi: kabaca n²/2 karşılaştırma ve ortalamada n²/4 yer değiştirme). Alan: O(1), yerinde. Kabarcık sıralaması kararlıdır: yalnızca kesinlikle sırası yanlış komşuları yer değiştirir (a[i] > a[i+1]), yani iki eşit eleman asla birbirinin üzerinden geçirilmez.

3. Seçmeli sıralama (selection sort)¶

3.1 Başlangıç sorusu¶

Kabarcık sıralamasının küçük, yerel yer değiştirmeleri toplamda çok fazla veri hareketine dönüşür — bölüm 2'nin "tersten sıralı" örneği 12 değeri sıralamak için 66 yer değiştirme yaptı. Onun yerine, kalan en küçük değeri tam bir taramayla bulup tek bir yer değiştirmeyle doğrudan son konumuna taşısanız ne olur? Yine de her seferinde tüm sıralanmamış bölgeyi taramanız gerekir (erken çıkış mümkün değildir — bir elemanın minimum olduğunu her adayı kontrol etmeden bilemezsiniz), ama çok daha az yer değiştirirsiniz. Bu ödünleşim — tam taramalar, ama en az yazma — seçmeli sıralamadır. Kabarcık sıralaması gibi, onun da tek bir adı geçen mucidi yoktur; "kalan en küçüğü tekrar tekrar seç" fikrinin doğrudan algoritmik ifadesidir, en az sıralamanın kendisi kadar eski bir fikir.

3.2 Fikir: minimumu bul, yerine yerleştir¶

0'dan n-2'ye kadar her i konumu için, kalanı (i+1'den n-1'e) tarayarak minimum değerinin indisini, min_idx'i bulun. Tarama bitince, a[i] ile a[min_idx]'i yer değiştirin — ama yalnızca min_idx != i ise; i konumu zaten minimumu tutuyorsa, anlamsız yer değiştirmeyi atlayın. Sıralı bölge bu kez soldan büyür (kabarcık sıralamasının sağdan büyüyen sıralı kuyruğunun tersi), çünkü her adım i konumunun son değerini i+1'e geçmeden önce kalıcı olarak sabitler.

3.3 Bellekte, ve kod¶

void selection_sort(int a[], int n, int *comparisons, int *swaps) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            (*comparisons)++;
            if (a[j] < a[min_idx]) min_idx = j;
        }
        if (min_idx != i) {              /* i zaten minimumsa yer değiştirmeyi atla */
            int tmp = a[i];
            a[i] = a[min_idx];
            a[min_idx] = tmp;
            (*swaps)++;
        }
    }
}

void selectionSort(int[] a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) minIdx = j;
        }
        if (minIdx != i) {                // i zaten minimumsa yer değiştirmeyi atla
            int tmp = a[i];
            a[i] = a[minIdx];
            a[minIdx] = tmp;
        }
    }
}

Seçicide ayrıca tekrarlı değerler — eşitlikte ilk bulunan minimum kalır ve zaten sıralı — her i için yine de tam tarama yapılır (burada kabarcık sıralamasının aksine erken çıkış yoktur) örneklerini deneyin, ya da rastgele veri için 🎲'e basın, ya da kendi diziniz yazın.

3.4 Deneyin¶

/* Week 10 -- Sorting
 * Selection sort: for each position i, scan the unsorted remainder for its
 * minimum and swap it into place. The sorted region grows on the LEFT; at
 * most n-1 swaps ever happen, but every position still does a full scan
 * (no early exit). Prints the array after every position and the total
 * comparisons/swaps.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>

static void print_array(const int a[], int n) {
    printf("[");
    for (int i = 0; i < n; i++) printf("%d%s", a[i], i + 1 < n ? ", " : "");
    printf("]\n");
}

void selection_sort(int a[], int n, int *comparisons, int *swaps) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            (*comparisons)++;
            if (a[j] < a[min_idx]) min_idx = j;
        }
        if (min_idx != i) {
            int tmp = a[i]; a[i] = a[min_idx]; a[min_idx] = tmp;
            (*swaps)++;
        }
        printf("  i=%d: min_idx=%d -> ", i, min_idx);
        print_array(a, n);
    }
}

static void run_scenario(const char *label, int a[], int n) {
    printf("-- %s --\n", label);
    printf("before: ");
    print_array(a, n);
    int comparisons = 0, swaps = 0;
    selection_sort(a, n, &comparisons, &swaps);
    printf("after:  ");
    print_array(a, n);
    printf("total: %d comparisons, %d swaps\n\n", comparisons, swaps);
}

int main(void) {
    int normal[] = {29, 10, 14, 37, 14, 22, 5, 41, 18, 33};
    int hard[] = {50, 3, 47, 8, 44, 12, 39, 16, 34, 20, 29, 24, 25, 27};
    int already_sorted[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int reverse_sorted[] = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    run_scenario("normal: 10 unordered values", normal, 10);
    run_scenario("hard: 14 values, the minimum keeps moving", hard, 14);
    run_scenario("edge: already sorted -- a full scan still happens for every i", already_sorted, 12);
    run_scenario("edge: reverse sorted -- every step swaps", reverse_sorted, 12);

    return 0;
}

/* Week 10 -- Sorting
 * Selection sort: for each position i, scan the unsorted remainder for its
 * minimum and swap it into place. The sorted region grows on the LEFT; at
 * most n-1 swaps ever happen, but every position still does a full scan
 * (no early exit). Prints the array after every position and the total
 * comparisons/swaps.
 * CEN207 Data Structures (formerly CE205)
 */
public class SelectionSort {
    static int comparisons, swaps;

    static void printArray(int[] a) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < a.length; i++) { sb.append(a[i]); if (i + 1 < a.length) sb.append(", "); }
        sb.append(']');
        System.out.println(sb);
    }

    static void selectionSort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                comparisons++;
                if (a[j] < a[minIdx]) minIdx = j;
            }
            if (minIdx != i) {
                int tmp = a[i]; a[i] = a[minIdx]; a[minIdx] = tmp;
                swaps++;
            }
            System.out.print("  i=" + i + ": min_idx=" + minIdx + " -> ");
            printArray(a);
        }
    }

    static void runScenario(String label, int[] a) {
        System.out.println("-- " + label + " --");
        System.out.print("before: ");
        printArray(a);
        comparisons = 0; swaps = 0;
        selectionSort(a);
        System.out.print("after:  ");
        printArray(a);
        System.out.println("total: " + comparisons + " comparisons, " + swaps + " swaps");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normal = {29, 10, 14, 37, 14, 22, 5, 41, 18, 33};
        int[] hard = {50, 3, 47, 8, 44, 12, 39, 16, 34, 20, 29, 24, 25, 27};
        int[] alreadySorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int[] reverseSorted = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

        runScenario("normal: 10 unordered values", normal);
        runScenario("hard: 14 values, the minimum keeps moving", hard);
        runScenario("edge: already sorted -- a full scan still happens for every i", alreadySorted);
        runScenario("edge: reverse sorted -- every step swaps", reverseSorted);
    }
}

Deneyin

gcc -std=c11 -Wall -Wextra -o /tmp/x selection_sort.c && /tmp/x

-- normal: 10 unordered values --
before: [29, 10, 14, 37, 14, 22, 5, 41, 18, 33]
  i=0: min_idx=6 -> [5, 10, 14, 37, 14, 22, 29, 41, 18, 33]
  i=1: min_idx=1 -> [5, 10, 14, 37, 14, 22, 29, 41, 18, 33]
  i=2: min_idx=2 -> [5, 10, 14, 37, 14, 22, 29, 41, 18, 33]
  i=3: min_idx=4 -> [5, 10, 14, 14, 37, 22, 29, 41, 18, 33]
  i=4: min_idx=8 -> [5, 10, 14, 14, 18, 22, 29, 41, 37, 33]
  i=5: min_idx=5 -> [5, 10, 14, 14, 18, 22, 29, 41, 37, 33]
  i=6: min_idx=6 -> [5, 10, 14, 14, 18, 22, 29, 41, 37, 33]
  i=7: min_idx=9 -> [5, 10, 14, 14, 18, 22, 29, 33, 37, 41]
  i=8: min_idx=8 -> [5, 10, 14, 14, 18, 22, 29, 33, 37, 41]
after:  [5, 10, 14, 14, 18, 22, 29, 33, 37, 41]
total: 45 comparisons, 4 swaps

-- hard: 14 values, the minimum keeps moving --
before: [50, 3, 47, 8, 44, 12, 39, 16, 34, 20, 29, 24, 25, 27]
  i=0: min_idx=1 -> [3, 50, 47, 8, 44, 12, 39, 16, 34, 20, 29, 24, 25, 27]
  i=1: min_idx=3 -> [3, 8, 47, 50, 44, 12, 39, 16, 34, 20, 29, 24, 25, 27]
  i=2: min_idx=5 -> [3, 8, 12, 50, 44, 47, 39, 16, 34, 20, 29, 24, 25, 27]
  i=3: min_idx=7 -> [3, 8, 12, 16, 44, 47, 39, 50, 34, 20, 29, 24, 25, 27]
  i=4: min_idx=9 -> [3, 8, 12, 16, 20, 47, 39, 50, 34, 44, 29, 24, 25, 27]
  i=5: min_idx=11 -> [3, 8, 12, 16, 20, 24, 39, 50, 34, 44, 29, 47, 25, 27]
  i=6: min_idx=12 -> [3, 8, 12, 16, 20, 24, 25, 50, 34, 44, 29, 47, 39, 27]
  i=7: min_idx=13 -> [3, 8, 12, 16, 20, 24, 25, 27, 34, 44, 29, 47, 39, 50]
  i=8: min_idx=10 -> [3, 8, 12, 16, 20, 24, 25, 27, 29, 44, 34, 47, 39, 50]
  i=9: min_idx=10 -> [3, 8, 12, 16, 20, 24, 25, 27, 29, 34, 44, 47, 39, 50]
  i=10: min_idx=12 -> [3, 8, 12, 16, 20, 24, 25, 27, 29, 34, 39, 47, 44, 50]
  i=11: min_idx=12 -> [3, 8, 12, 16, 20, 24, 25, 27, 29, 34, 39, 44, 47, 50]
  i=12: min_idx=12 -> [3, 8, 12, 16, 20, 24, 25, 27, 29, 34, 39, 44, 47, 50]
after:  [3, 8, 12, 16, 20, 24, 25, 27, 29, 34, 39, 44, 47, 50]
total: 91 comparisons, 12 swaps

-- edge: already sorted -- a full scan still happens for every i --
before: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=0: min_idx=0 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=1: min_idx=1 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=2: min_idx=2 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=3: min_idx=3 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=4: min_idx=4 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=5: min_idx=5 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=6: min_idx=6 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=7: min_idx=7 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=8: min_idx=8 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=9: min_idx=9 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=10: min_idx=10 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
after:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
total: 66 comparisons, 0 swaps

-- edge: reverse sorted -- every step swaps --
before: [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
  i=0: min_idx=11 -> [1, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 12]
  i=1: min_idx=10 -> [1, 2, 10, 9, 8, 7, 6, 5, 4, 3, 11, 12]
  i=2: min_idx=9 -> [1, 2, 3, 9, 8, 7, 6, 5, 4, 10, 11, 12]
  i=3: min_idx=8 -> [1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12]
  i=4: min_idx=7 -> [1, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 12]
  i=5: min_idx=6 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=6: min_idx=6 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=7: min_idx=7 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=8: min_idx=8 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=9: min_idx=9 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=10: min_idx=10 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
after:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
total: 66 comparisons, 6 swaps

javac -Xlint:all -d /tmp/j SelectionSort.java && java -cp /tmp/j SelectionSort

3.5 Karmaşıklık, hatalar, kendini sına¶

Karmaşıklık. En iyi, ortalama ve en kötü durum hepsi O(n²) karşılaştırma — girdi sırasından bağımsız olarak her zaman n(n-1)/2 (iç taramanın hiç erken çıkışı yoktur, gerçek minimumdan emin olmak için kalan her adayı kontrol etmelisiniz). Ama en çok n-1 yer değiştirme, her zaman — kabarcık sıralamasının en çok n(n-1)/2'sinden çok daha az. Alan: O(1), yerinde. Seçmeli sıralama genelde kararlı DEĞİLDİR: minimumu i konumuna taşıyan uzun mesafeli yer değiştirme, arada duran eşit anahtarlı bir elemanın üzerinden geçebilir (bölüm 11 bunun gerçek veride olduğunu gösterir).

4. Eklemeli sıralama (insertion sort)¶

4.1 Başlangıç sorusu¶

Bir deste oyun kartını nasıl sıraladığınızı düşünün. Kabarcık ya da seçmeli sıralamanın yaptığı gibi her kartı her kartla karşılaştırmazsınız. Sol elinizde küçük, sıralı bir el tutar, sağ elinizle bir sonraki kartı alır ve arasındaki kartları bir hücre kaydırarak onu ait olduğu tek boşluğa sokarsınız. Bu tam olarak eklemeli sıralamadır — ve bu ders her hızlı örneğe ihtiyaç duyduğunda tahtaya elle çizeceğiniz sıralamadır, çünkü resmi insanların gerçekte bir şeyleri nasıl sıraladığıyla eşleşen tek sıralamadır.

4.2 Fikir, tam sizin çizeceğiniz şekilde¶

Eklemeli sıralama, A[0..i-1]'in zaten sıralı olduğu değişmezini (invariant) korur. Her i adımında, A[i]'yi anahtar (key) olarak dışarı çeker — elinizden bir kartı kaldırır gibi diziden ayrı tutar — sonra anahtarı sıralı önekle sağdan karşılaştırır: anahtarın hemen solundaki eleman anahtardan büyük olduğu sürece, o elemanı bir hücre sağa kaydırır (her kaydırmada solda hareket eden bir "boşluk" açarak) ve karşılaştırma noktasını bir daha sola taşır. Anahtardan büyük OLMAYAN bir eleman bulduğunuz an (ya da dizinin sol ucundan çıktığınız an), boşluk anahtarın doğru yeridir — onu oraya bırakın.

Bu, tahtada tam olarak şöyle çizilir — ve aşağıdaki animasyon da aynı şekilde çizer:

• A[0..i-1] üzerinde "zaten sıralı" etiketli bir parantez (brace), her dış-döngü adımında bir eleman büyür;
• anahtar diziden dışarı çekilir ve eski konumunun üzerinde ayrı bir kırmızı kutuda gösterilir — bu sırada dizinin parçası değildir, tam olarak diğer elinizde tuttuğunuz bir kart gibi;
• taranan bölge anında ikiye ayrılır: <= key olduğu doğrulanmış elemanlar (tarama onlara ulaşmamıştır, ya da orada durmuştur) yerinde kalır; > key bulunan elemanlar bir hücre sağa kayarak boşluğu açar;
• kayan elemanın eski hücresinden yeni hücresine bir kaydırma oku (shift arrow), böylece göz boşluğun bir adım sola hareketini takip eder;
• bir karşılaştırma a[j] <= key bulduğu an döngü durur ve anahtar boşluğa düşer — kırmızı kutu kaybolur, yerinde düz bir dizi hücresi belirir.

4.3 Bellekte, ve kod¶

void insertion_sort(int a[], int n, int *comparisons, int *shifts) {
    for (int i = 1; i < n; i++) {
        int key = a[i];               /* anahtarı dışarı çek (kırmızı kutu) */
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];           /* sağa kaydır, j'de boşluk aç */
            j--;
        }
        a[j + 1] = key;                /* anahtar boşluğa düşer */
    }
}

void insertionSort(int[] a, int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];               // anahtarı dışarı çek (kırmızı kutu)
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];           // sağa kaydır, j'de boşluk aç
            j--;
        }
        a[j + 1] = key;                // anahtar boşluğa düşer
    }
}

Seçicide ayrıca tekrarlı değerler — bir eşitlik kaydırmayı durdurur (kararlı) ve tersten sıralı — en kötü durum, her anahtar başa kadar kayar örneklerini deneyin, ya da rastgele veri için 🎲'e basın, ya da kendi diziniz yazın. Burada gördüklerinizi dersin başındaki kendi tahta notlarınızla karşılaştırın — bu animasyon onlarla eşleşecek şekilde çizilmiştir.

4.4 Deneyin¶

/* Week 10 -- Sorting
 * Insertion sort: for each i, pull out a[i] as the key, then shift every
 * element greater than the key one cell right until the key's correct spot
 * (its "hole") is found. Prints the key and the array after every
 * insertion, plus total comparisons/shifts.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>

static void print_array(const int a[], int n) {
    printf("[");
    for (int i = 0; i < n; i++) printf("%d%s", a[i], i + 1 < n ? ", " : "");
    printf("]\n");
}

void insertion_sort(int a[], int n, int *comparisons, int *shifts) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0) {
            (*comparisons)++;
            if (a[j] <= key) break;
            a[j + 1] = a[j];
            (*shifts)++;
            j--;
        }
        a[j + 1] = key;
        printf("  i=%d: key=%d -> ", i, key);
        print_array(a, n);
    }
}

static void run_scenario(const char *label, int a[], int n) {
    printf("-- %s --\n", label);
    printf("before: ");
    print_array(a, n);
    int comparisons = 0, shifts = 0;
    insertion_sort(a, n, &comparisons, &shifts);
    printf("after:  ");
    print_array(a, n);
    printf("total: %d comparisons, %d shifts\n\n", comparisons, shifts);
}

int main(void) {
    int normal[] = {31, 12, 25, 8, 19, 40, 3, 27, 15, 22};
    int hard[] = {45, 2, 38, 9, 33, 14, 29, 6, 41, 18, 24, 11, 36, 20};
    int already_sorted[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int reverse_sorted[] = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    run_scenario("normal: 10 unordered values", normal, 10);
    run_scenario("hard: 14 values, needs long shifts", hard, 14);
    run_scenario("edge: already sorted -- one comparison per i, zero shifts", already_sorted, 12);
    run_scenario("edge: reverse sorted -- worst case, every key shifts to the front", reverse_sorted, 12);

    return 0;
}

/* Week 10 -- Sorting
 * Insertion sort: for each i, pull out a[i] as the key, then shift every
 * element greater than the key one cell right until the key's correct spot
 * (its "hole") is found. Prints the key and the array after every
 * insertion, plus total comparisons/shifts.
 * CEN207 Data Structures (formerly CE205)
 */
public class InsertionSort {
    static int comparisons, shifts;

    static void printArray(int[] a) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < a.length; i++) { sb.append(a[i]); if (i + 1 < a.length) sb.append(", "); }
        sb.append(']');
        System.out.println(sb);
    }

    static void insertionSort(int[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0) {
                comparisons++;
                if (a[j] <= key) break;
                a[j + 1] = a[j];
                shifts++;
                j--;
            }
            a[j + 1] = key;
            System.out.print("  i=" + i + ": key=" + key + " -> ");
            printArray(a);
        }
    }

    static void runScenario(String label, int[] a) {
        System.out.println("-- " + label + " --");
        System.out.print("before: ");
        printArray(a);
        comparisons = 0; shifts = 0;
        insertionSort(a);
        System.out.print("after:  ");
        printArray(a);
        System.out.println("total: " + comparisons + " comparisons, " + shifts + " shifts");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normal = {31, 12, 25, 8, 19, 40, 3, 27, 15, 22};
        int[] hard = {45, 2, 38, 9, 33, 14, 29, 6, 41, 18, 24, 11, 36, 20};
        int[] alreadySorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int[] reverseSorted = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

        runScenario("normal: 10 unordered values", normal);
        runScenario("hard: 14 values, needs long shifts", hard);
        runScenario("edge: already sorted -- one comparison per i, zero shifts", alreadySorted);
        runScenario("edge: reverse sorted -- worst case, every key shifts to the front", reverseSorted);
    }
}

Deneyin

gcc -std=c11 -Wall -Wextra -o /tmp/x insertion_sort.c && /tmp/x

-- normal: 10 unordered values --
before: [31, 12, 25, 8, 19, 40, 3, 27, 15, 22]
  i=1: key=12 -> [12, 31, 25, 8, 19, 40, 3, 27, 15, 22]
  i=2: key=25 -> [12, 25, 31, 8, 19, 40, 3, 27, 15, 22]
  i=3: key=8 -> [8, 12, 25, 31, 19, 40, 3, 27, 15, 22]
  i=4: key=19 -> [8, 12, 19, 25, 31, 40, 3, 27, 15, 22]
  i=5: key=40 -> [8, 12, 19, 25, 31, 40, 3, 27, 15, 22]
  i=6: key=3 -> [3, 8, 12, 19, 25, 31, 40, 27, 15, 22]
  i=7: key=27 -> [3, 8, 12, 19, 25, 27, 31, 40, 15, 22]
  i=8: key=15 -> [3, 8, 12, 15, 19, 25, 27, 31, 40, 22]
  i=9: key=22 -> [3, 8, 12, 15, 19, 22, 25, 27, 31, 40]
after:  [3, 8, 12, 15, 19, 22, 25, 27, 31, 40]
total: 30 comparisons, 24 shifts

-- hard: 14 values, needs long shifts --
before: [45, 2, 38, 9, 33, 14, 29, 6, 41, 18, 24, 11, 36, 20]
  i=1: key=2 -> [2, 45, 38, 9, 33, 14, 29, 6, 41, 18, 24, 11, 36, 20]
  i=2: key=38 -> [2, 38, 45, 9, 33, 14, 29, 6, 41, 18, 24, 11, 36, 20]
  i=3: key=9 -> [2, 9, 38, 45, 33, 14, 29, 6, 41, 18, 24, 11, 36, 20]
  i=4: key=33 -> [2, 9, 33, 38, 45, 14, 29, 6, 41, 18, 24, 11, 36, 20]
  i=5: key=14 -> [2, 9, 14, 33, 38, 45, 29, 6, 41, 18, 24, 11, 36, 20]
  i=6: key=29 -> [2, 9, 14, 29, 33, 38, 45, 6, 41, 18, 24, 11, 36, 20]
  i=7: key=6 -> [2, 6, 9, 14, 29, 33, 38, 45, 41, 18, 24, 11, 36, 20]
  i=8: key=41 -> [2, 6, 9, 14, 29, 33, 38, 41, 45, 18, 24, 11, 36, 20]
  i=9: key=18 -> [2, 6, 9, 14, 18, 29, 33, 38, 41, 45, 24, 11, 36, 20]
  i=10: key=24 -> [2, 6, 9, 14, 18, 24, 29, 33, 38, 41, 45, 11, 36, 20]
  i=11: key=11 -> [2, 6, 9, 11, 14, 18, 24, 29, 33, 38, 41, 45, 36, 20]
  i=12: key=36 -> [2, 6, 9, 11, 14, 18, 24, 29, 33, 36, 38, 41, 45, 20]
  i=13: key=20 -> [2, 6, 9, 11, 14, 18, 20, 24, 29, 33, 36, 38, 41, 45]
after:  [2, 6, 9, 11, 14, 18, 20, 24, 29, 33, 36, 38, 41, 45]
total: 59 comparisons, 47 shifts

-- edge: already sorted -- one comparison per i, zero shifts --
before: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=1: key=2 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=2: key=3 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=3: key=4 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=4: key=5 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=5: key=6 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=6: key=7 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=7: key=8 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=8: key=9 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=9: key=10 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=10: key=11 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  i=11: key=12 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
after:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
total: 11 comparisons, 0 shifts

-- edge: reverse sorted -- worst case, every key shifts to the front --
before: [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
  i=1: key=11 -> [11, 12, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
  i=2: key=10 -> [10, 11, 12, 9, 8, 7, 6, 5, 4, 3, 2, 1]
  i=3: key=9 -> [9, 10, 11, 12, 8, 7, 6, 5, 4, 3, 2, 1]
  i=4: key=8 -> [8, 9, 10, 11, 12, 7, 6, 5, 4, 3, 2, 1]
  i=5: key=7 -> [7, 8, 9, 10, 11, 12, 6, 5, 4, 3, 2, 1]
  i=6: key=6 -> [6, 7, 8, 9, 10, 11, 12, 5, 4, 3, 2, 1]
  i=7: key=5 -> [5, 6, 7, 8, 9, 10, 11, 12, 4, 3, 2, 1]
  i=8: key=4 -> [4, 5, 6, 7, 8, 9, 10, 11, 12, 3, 2, 1]
  i=9: key=3 -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 2, 1]
  i=10: key=2 -> [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1]
  i=11: key=1 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
after:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
total: 66 comparisons, 66 shifts

javac -Xlint:all -d /tmp/j InsertionSort.java && java -cp /tmp/j InsertionSort

4.5 Karmaşıklık, hatalar, kendini sına¶

Karmaşıklık. En iyi durum O(n) (zaten sıralı: her i için tam bir karşılaştırma, a[j] <= key hemen doğrudur, sıfır kaydırma — yukarıda doğrulandı: n = 12 için 11 karşılaştırma, daha fazlası yok). En kötü durum O(n²) (tersten sıralı: her anahtar başa kadar tamamen kaymalıdır — yukarıda doğrulandı: 66 karşılaştırma ve 66 kaydırma, tam n(n-1)/2). Ortalama durum da O(n²), ama küçük bir sabit çarpanla — eklemeli sıralamayı küçük ya da neredeyse sıralı dizilerde gerçekten hızlı kılacak kadar küçük — gerçek dünya kütüphane sıralamaları (C'nin qsort'u ve Java'nın ilkel tür Arrays.sort'u dahil) özyinelemeli bir hızlı/ birleştirmeli sıralamanın alt dizisi belirli bir eşiğin (genellikle 16–32 eleman civarı) altına düştüğünde eklemeli sıralamaya geçer. Alan: O(1), yerinde. Eklemeli sıralama kararlıdır: kaydırma koşulu kesin a[j] > key'dir, bu yüzden anahtara eşit bir eleman asla onun üzerinden kaydırılmaz — döngü sadece durur (etiketli, işlenmiş bir örnek için bölüm 11'e bakın).

5. Shell sıralaması (shell sort)¶

5.1 Başlangıç sorusu¶

Eklemeli sıralama, elemanlar yalnızca kısa bir mesafe hareket etmesi gerektiğinde hızlıdır, ve bir eleman evinden uzakta başladığında yavaştır (bölüm 4.5'in tersten sıralı en kötü durumunda her anahtar bir seferde bir hücre olmak üzere başa kadar tamamen kaydı). Ya düz eklemeli sıralamayı çalıştırmadan önce, önce her elemanı büyük sıçramalarla evinin çoğu*na taşısaydınız? Donald **Shell* tam olarak bu soruyu sordu ve yanıtını — en kötü durumda O(n²)'yi aşan ilk sıralama algoritmasını — Communications of the ACM dergisinde 1959'da "A High-Speed Sorting Procedure" başlığıyla yayımladı.

5.2 Fikir: küçülen aralıklı eklemeli sıralama¶

Shell sıralaması, bitişik yerine gap (aralık) konum uzaklıktaki elemanları karşılaştırıp kaydıran eklemeli sıralamadır. Büyük bir aralıkla başlayın (bu bölüm en basit klasik diziyi kullanır, gap = n/2, sonra n/4, ve böyle gap = 1'e kadar yarıya inerek); her aralık için, "solundaki eleman" bir hücre değil gap hücre solundaki eleman anlamına gelen bir eklemeli-sıralama turu çalıştırın. Büyük bir aralık, kötü konumlanmış bir elemanın evine olan mesafenin çoğunu, bir hücrede bir kat ederek geçmekten çok daha az, çok daha ucuz karşılaştırmayla tek bir turda sıçramasına izin verir. Aralık sonunda gap = 1'e küçüldüğünde, dizi zaten "neredeyse sıralıdır", bu yüzden o son tur — düz eklemeli sıralama — ucuzdur.

5.3 Bellekte, ve kod¶

void shell_sort(int a[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {   /* aralık dizisi: n/2, n/4, ..., 1 */
        for (int i = gap; i < n; i++) {
            int key = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];               /* 1 değil gap kadar kaydır */
                j -= gap;
            }
            a[j] = key;
        }
    }
}

void shellSort(int[] a, int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {   // aralık dizisi: n/2, n/4, ..., 1
        for (int i = gap; i < n; i++) {
            int key = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap];               // 1 değil gap kadar kaydır
                j -= gap;
            }
            a[j] = key;
        }
    }
}

Seçicide ayrıca tersten sıralı — büyük aralıklar uzun mesafeleri hemen kapatır örneğini deneyin ve aynı tersten sıralı girdide bölüm 4'ün düz eklemeli sıralamasıyla karşılaştırın: elemanlar artık diziyi bir hücrede bir kat aşmak zorunda kalmadığında karşılaştırma ve kaydırma sayılarının keskin biçimde düştüğünü izleyin. Ya da rastgele veri için 🎲'e basın, ya da kendi diziniz yazın.

5.4 Deneyin¶

/* Week 10 -- Sorting
 * Shell sort: insertion sort, but comparing elements `gap` apart instead of
 * adjacent; the gap starts at n/2 and halves every round down to 1. Prints
 * the array after every gap round and the total comparisons/shifts.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>

static void print_array(const int a[], int n) {
    printf("[");
    for (int i = 0; i < n; i++) printf("%d%s", a[i], i + 1 < n ? ", " : "");
    printf("]\n");
}

void shell_sort(int a[], int n, int *comparisons, int *shifts) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = a[i];
            int j = i;
            while (j >= gap) {
                (*comparisons)++;
                if (a[j - gap] <= key) break;
                a[j] = a[j - gap];
                (*shifts)++;
                j -= gap;
            }
            a[j] = key;
        }
        printf("  gap=%d: ", gap);
        print_array(a, n);
    }
}

static void run_scenario(const char *label, int a[], int n) {
    printf("-- %s --\n", label);
    printf("before: ");
    print_array(a, n);
    int comparisons = 0, shifts = 0;
    shell_sort(a, n, &comparisons, &shifts);
    printf("after:  ");
    print_array(a, n);
    printf("total: %d comparisons, %d shifts\n\n", comparisons, shifts);
}

int main(void) {
    int normal[] = {23, 9, 41, 5, 33, 17, 2, 46, 12, 28};
    int hard[] = {50, 3, 47, 8, 44, 12, 39, 16, 34, 20, 29, 24, 25, 27, 1, 45};
    int already_sorted[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int reverse_sorted[] = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    run_scenario("normal: 10 values, gap sequence 5, 2, 1", normal, 10);
    run_scenario("hard: 16 values, gap sequence 8, 4, 2, 1", hard, 16);
    run_scenario("edge: already sorted -- zero shifts at every gap", already_sorted, 12);
    run_scenario("edge: reverse sorted -- large gaps close long distances immediately", reverse_sorted, 12);

    return 0;
}

/* Week 10 -- Sorting
 * Shell sort: insertion sort, but comparing elements `gap` apart instead of
 * adjacent; the gap starts at n/2 and halves every round down to 1. Prints
 * the array after every gap round and the total comparisons/shifts.
 * CEN207 Data Structures (formerly CE205)
 */
public class ShellSort {
    static int comparisons, shifts;

    static void printArray(int[] a) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < a.length; i++) { sb.append(a[i]); if (i + 1 < a.length) sb.append(", "); }
        sb.append(']');
        System.out.println(sb);
    }

    static void shellSort(int[] a) {
        int n = a.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int key = a[i];
                int j = i;
                while (j >= gap) {
                    comparisons++;
                    if (a[j - gap] <= key) break;
                    a[j] = a[j - gap];
                    shifts++;
                    j -= gap;
                }
                a[j] = key;
            }
            System.out.print("  gap=" + gap + ": ");
            printArray(a);
        }
    }

    static void runScenario(String label, int[] a) {
        System.out.println("-- " + label + " --");
        System.out.print("before: ");
        printArray(a);
        comparisons = 0; shifts = 0;
        shellSort(a);
        System.out.print("after:  ");
        printArray(a);
        System.out.println("total: " + comparisons + " comparisons, " + shifts + " shifts");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normal = {23, 9, 41, 5, 33, 17, 2, 46, 12, 28};
        int[] hard = {50, 3, 47, 8, 44, 12, 39, 16, 34, 20, 29, 24, 25, 27, 1, 45};
        int[] alreadySorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        int[] reverseSorted = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

        runScenario("normal: 10 values, gap sequence 5, 2, 1", normal);
        runScenario("hard: 16 values, gap sequence 8, 4, 2, 1", hard);
        runScenario("edge: already sorted -- zero shifts at every gap", alreadySorted);
        runScenario("edge: reverse sorted -- large gaps close long distances immediately", reverseSorted);
    }
}