Arama ve sıralama: linear, binary, selection, insertion, merge sort

Arama (searching) ve sıralama (sorting), algoritma analizinin ilk durağı. Bu hafta iki arama ve üç sıralama algoritmasını adım adım izliyorsun. Sınavda tipik soru: “bu diziye selection sort uygulanınca ikinci geçişten sonra dizi ne olur”, “binary search hangi indekslere bakar”, ve “Big-O’su nedir, neden”. Kodları ezberlemek yerine her algoritmanın tek cümlelik fikrini bil; kod o fikirden çıkar.

Altın kurallar:

1. Binary search sadece sıralı dizide çalışır. Her adımda aralığı yarıya böler.
2. Selection sort: kalanın en küçüğünü bul, başa koy.
3. Insertion sort: sıradaki elemanı soldaki sıralı kısımda yerine kaydır.
4. Merge sort: ikiye böl, iki yarıyı sırala, birleştir.
5. Big-O: linear $O(n)$, binary $O(\log n)$, selection ve insertion $O(n^2)$, merge $O(n \log n)$.

Arama

Linear search

Diziyi baştan sona tek tek gez, aranan değeri görünce indeksini döndür. Dizi sıralı olmak zorunda değil.

static int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++)
        if (a[i] == key) return i;
    return -1;
}
int[] data = {42, 7, 19, 3, 25, 7};

Karşılaştırma sayılarını da sayarak üç arama:

1 comps=2
4 comps=5
-1 comps=6

(7 aranınca ilk 7 bulunur, indeks 1; 25 için 5 karşılaştırma; 99 yok, dizinin hepsine bakıldı.)

Binary search

Dizi sıralıysa ortadaki elemana bak. Aranan daha büyükse sol yarıyı, daha küçükse sağ yarıyı tamamen eleyebilirsin. Geçen hafta özyinelemeli yazdık; döngülü sürümü:

static int binarySearch(int[] a, int key) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;    // sağ yarı
        else high = mid - 1;                // sol yarı
    }
    return -1;
}
int[] sorted = {2, 5, 9, 14, 20, 27, 33, 41, 48, 56, 63};
binarySearch(sorted, 41);
binarySearch(sorted, 4);

  low=0 high=10 mid=5 a[mid]=27
  low=6 high=10 mid=8 a[mid]=48
  low=6 high=7 mid=6 a[mid]=33
  low=7 high=7 mid=7 a[mid]=41
index 7 comps=4
  low=0 high=10 mid=5 a[mid]=27
  low=0 high=4 mid=2 a[mid]=9
  low=0 high=1 mid=0 a[mid]=2
  low=1 high=1 mid=1 a[mid]=5
index -1 comps=4

4 aranırken son adımda low = 1, high = 1, a[1] = 5 > 4 olduğu için high = 0 olur; low > high ve döngü biter: −1.

TUZAK · low < high. Koşulu < yazarsan aralık tek elemana indiğinde o eleman hiç kontrol edilmez. {2, 5, 9} dizisinde bu hatalı sürüm 5’i buldu ama 9 ve 2 için −1 döndü.

Java’nın hazır sürümü: Arrays.binarySearch(sorted, 27) → 5. O da dizinin sıralı olmasını bekler; sıralı değilse sonuç anlamsızdır.

Sıralama

Üç algoritmayı aynı dizi üzerinde izleyeceğiz: {29, 10, 14, 37, 13}.

Selection sort

Fikir: dizinin sıralanmamış kısmındaki en küçük elemanı bul, o kısmın başıyla yer değiştir (swap). Her geçişte (pass) baştan bir eleman daha kesin yerine oturur.

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 tmp = a[i]; a[i] = a[min]; a[min] = tmp;   // swap
    }
}

Her geçişten sonra dizi:

  pass 1: [10, 29, 14, 37, 13]
  pass 2: [10, 13, 14, 37, 29]
  pass 3: [10, 13, 14, 37, 29]
  pass 4: [10, 13, 14, 29, 37]
comps=10

pass 1: [29 10 14 37 13]  en küçük 10 (indeks 1) ↔ indeks 0   → [10 | 29 14 37 13]
pass 2: [10 | 29 14 37 13] en küçük 13 (indeks 4) ↔ indeks 1  → [10 13 | 14 37 29]
pass 3: en küçük 14 zaten indeks 2'de                         → [10 13 14 | 37 29]
pass 4: en küçük 29 (indeks 4) ↔ indeks 3                     → [10 13 14 29 | 37]

Karşılaştırma sayısı her girdide aynı: $(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$. n = 5 için 10. Bu yüzden selection sort her durumda $O(n^2)$.

Insertion sort

Fikir: kartları elinde sıralar gibi. Soldaki kısım her zaman sıralı. Sıradaki elemanı (key) al, kendisinden büyük olanları birer sağa kaydır, açılan boşluğa key’i koy.

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];     // sağa kaydır
            j--;
        }
        a[j + 1] = key;
    }
}

  pass 1: [10, 29, 14, 37, 13]
  pass 2: [10, 14, 29, 37, 13]
  pass 3: [10, 14, 29, 37, 13]
  pass 4: [10, 13, 14, 29, 37]
comps=8

İki algoritmanın geçişlerini karşılaştır: selection sort’ta baştaki elemanlar kesin yerindedir (pass 2’den sonra 10 ve 13 bir daha değişmez). Insertion sort’ta baştaki kısım sıralıdır ama kesin değildir: pass 3’te [10, 14, 29, 37] sıralı ama 13 daha sonra araya girdi.

Insertion sort’un karşılaştırma sayısı girdiye bağlı:

Sıralı girdide insertion sort her eleman için bir karşılaştırma yapıp durur: en iyi durum $O(n)$. Ters sıralıda her eleman başa kadar kayar: en kötü durum $O(n^2)$.

Merge sort

Fikir: böl ve yönet (divide and conquer). Diziyi ikiye böl, iki yarıyı özyinelemeli olarak sırala, sonra iki sıralı yarıyı tek sıralı diziye birleştir (merge). Tek elemanlı dizi zaten sıralıdır: base case.

static void mergeSort(int[] a, int low, int high) {
    if (low >= high) return;                 // 0 ya da 1 eleman
    int mid = (low + high) / 2;
    mergeSort(a, low, mid);                  // sol yarı
    mergeSort(a, mid + 1, high);             // sağ yarı
    merge(a, low, mid, high);                // birleştir
}
static void merge(int[] a, int low, int mid, int high) {
    int[] tmp = new int[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // küçük olanı al
    while (i <= mid) tmp[k++] = a[i++];                // kalanlar
    while (j <= high) tmp[k++] = a[j++];
    System.arraycopy(tmp, 0, a, low, tmp.length);
}

{38, 27, 43, 3, 9, 82, 10} için her merge’den sonra o aralığın hali:

  merge [0..1]: [27, 38]
  merge [2..3]: [3, 43]
  merge [0..3]: [3, 27, 38, 43]
  merge [4..5]: [9, 82]
  merge [4..6]: [9, 10, 82]
  merge [0..6]: [3, 9, 10, 27, 38, 43, 82]
[3, 9, 10, 27, 38, 43, 82] comps=14

                 [38 27 43 3 9 82 10]
            [38 27 43 3]          [9 82 10]
         [38 27]   [43 3]       [9 82]   [10]
        [38] [27] [43] [3]     [9] [82]
         └─┬─┘     └─┬─┘        └─┬─┘
        [27 38]   [3 43]       [9 82]
           └────┬────┘            └──┬──┘
        [3 27 38 43]            [9 10 82]
                └──────────┬──────────┘
              [3 9 10 27 38 43 82]

Bölme $\log_2 n$ seviye sürer, her seviyede toplam n eleman birleştirilir: $O(n \log n)$, girdiden bağımsız. Bedeli: geçici dizi için ek $O(n)$ bellek.

Big-O karşılaştırması

Teorinin pratikteki karşılığı: ters sıralı dizilerde sayılan karşılaştırmalar.

n her iki katına çıktığında selection sort’un işi dört katına çıkıyor ($n^2$), merge sort’unki iki kattan biraz fazla ($n \log n$).

İPUCU · gerçek hayatta. Kendi sıralamanı yazmazsın: Arrays.sort(dizi) ve Collections.sort(liste) hazır ve $O(n \log n)$. Sınavda ise algoritmayı elle izlemen ve yazman istenir; hazır metot kabul edilmez.

Sık yapılan hatalar

int[] a = {29, 10, 14, 37, 13};

int[] a = {29, 10, 14, 37, 13};

static int search(int[] a, int key) {
    int low = 0, high = a.length - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

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