Sıralama Algoritmaları Sınav Soruları ve Adım Adım Çözümleri

Veri yapıları ve algoritmalar dersinin vize ve finalinde sıralama sorusu neredeyse hiç eksik olmaz ve çoğu zaman kod yazdırmaz: bir dizi verir, "her geçişten sonra diziyi gösterin" der. Bu yazıda beş klasik algoritmayı tek tabloda karşılaştırıyor, ardından sınavda karşına çıkacak soru tiplerini elle, adım adım çözüyorum. Puan kaybı genelde algoritmayı bilmemekten değil, izi yanlış formatta ya da eksik yazmaktan gelir; o yüzden çözümlerde formatı da gösteriyorum.

Karmaşıklık ifadeleri sana yabancı geliyorsa önce Big O notasyonu ve zaman karmaşıklığı rehberine göz at; aşağıdaki tablo onun üzerine kurulu.

Beş Algoritmanın Karşılaştırma Tablosu

Algoritma	En iyi	Ortalama	En kötü	Ek bellek	Kararlı mı?	Yerinde mi?
Bubble sort (erken çıkışlı)	O(n)	O(n²)	O(n²)	O(1)	Evet	Evet
Selection sort	O(n²)	O(n²)	O(n²)	O(1)	Hayır	Evet
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Evet	Evet
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Evet	Hayır
Quick sort	O(n log n)	O(n log n)	O(n²)	O(log n) ortalama yığın	Hayır	Evet

İki terimi netleştirelim. Kararlı (stable) sıralama, anahtarı eşit olan elemanların girişteki sırasını korur. Yerinde (in-place) sıralama, girdiyle orantılı ek dizi kullanmaz. Tablodaki bubble sort satırı "takas olmadıysa dur" kontrolü olan sürüm içindir; o kontrol yoksa en iyi durum da O(n²) olur. Sınavda hangi sürümün sorulduğunu mutlaka kontrol et.

Kodlar: Üç Basit Algoritma

Çözümlerde saydığım karşılaştırma ve takaslar tam olarak bu kodlara göredir.

static void BubbleSort(int[] a)
{
    for (int i = 0; i < a.Length - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < a.Length - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                (a[j], a[j + 1]) = (a[j + 1], a[j]);
                swapped = true;
            }
        }
        if (!swapped) break; // bu geçişte takas yok: dizi sıralı
    }
}

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;
        if (min != i) (a[i], a[min]) = (a[min], a[i]);
    }
}

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

Kodlar: Merge Sort ve Quick Sort

static void MergeSort(int[] a, int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    MergeSort(a, left, mid);
    MergeSort(a, mid + 1, right);
    Merge(a, left, mid, right);
}

static void Merge(int[] a, int left, int mid, int right)
{
    int[] l = a[left..(mid + 1)];
    int[] r = a[(mid + 1)..(right + 1)];
    int i = 0, j = 0, k = left;
    while (i < l.Length && j < r.Length)
        a[k++] = l[i] <= r[j] ? l[i++] : r[j++]; // <= kararlılığı korur
    while (i < l.Length) a[k++] = l[i++];
    while (j < r.Length) a[k++] = r[j++];
}

static void QuickSort(int[] a, int low, int high)
{
    if (low >= high) return;
    int p = Partition(a, low, high);
    QuickSort(a, low, p - 1);
    QuickSort(a, p + 1, high);
}

// Lomuto bölümleme: pivot = son eleman
static int Partition(int[] a, int low, int high)
{
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (a[j] < pivot)
        {
            i++;
            (a[i], a[j]) = (a[j], a[i]);
        }
    }
    (a[i + 1], a[high]) = (a[high], a[i + 1]);
    return i + 1;
}

Quick sort'un birden fazla bölümleme şeması vardır (Lomuto, Hoare). Ara adımlar şemaya göre değişir; sınavda dersin slaytındaki şemayı kullan ve hangisini kullandığını cevabın başına yaz.

Soru 1: Bubble Sort — Her Geçişten Sonra Dizi

Soru: [5, 1, 4, 2, 8] dizisini erken çıkışlı bubble sort ile sıralayın. Her geçişten sonra diziyi, toplam karşılaştırma ve takas sayısını yazın.

Çözüm: Her geçişte komşu çiftler soldan sağa karşılaştırılır; en büyük eleman sona "yüzer".

Başlangıç : [5, 1, 4, 2, 8]
1. geçiş  : [1, 4, 2, 5, 8]   4 karşılaştırma, 3 takas (5-1, 5-4, 5-2)
2. geçiş  : [1, 2, 4, 5, 8]   3 karşılaştırma, 1 takas (4-2)
3. geçiş  : [1, 2, 4, 5, 8]   2 karşılaştırma, 0 takas -> dur

Toplam 9 karşılaştırma, 4 takas. Erken çıkış olmasaydı 1 karşılaştırmalık dördüncü geçiş de yapılır, toplam n(n−1)/2 = 10 olurdu. Dizi ikinci geçişte sıralandı ama algoritma bunu ancak takas yapılmayan üçüncü geçişte anlar; bu geçişi atlamak en sık görülen hatadır.

Soru 2: Selection Sort İzi

Soru: [64, 25, 12, 22, 11] dizisini selection sort ile sıralayın; her geçişi gösterin.

Çözüm: Her geçişte sıralanmamış kısmın en küçüğü bulunur ve o kısmın ilk elemanıyla tek bir takas yapılır.

Başlangıç : [64, 25, 12, 22, 11]
1. geçiş  : [11, 25, 12, 22, 64]   en küçük 11 <-> 64
2. geçiş  : [11, 12, 25, 22, 64]   en küçük 12 <-> 25
3. geçiş  : [11, 12, 22, 25, 64]   en küçük 22 <-> 25
4. geçiş  : [11, 12, 22, 25, 64]   en küçük 25 zaten yerinde, takas yok

Karşılaştırma sayısı girdiden bağımsızdır: 4 + 3 + 2 + 1 = 10. Takas sayısı 3. Selection sort'un tek güçlü yanı budur: en fazla n−1 takas yapar, yani yazma işleminin pahalı olduğu durumlarda anlamlıdır.

Soru 3: Insertion Sort ve Karşılaştırma Sayımı

Soru: [7, 3, 5, 1, 9, 2] dizisini insertion sort ile sıralayın. Her adımdaki karşılaştırma ve kaydırma sayısını verin.

Çözüm: "Karşılaştırma" derken a[j] > key kıyasını sayıyoruz.

Başlangıç    : [7, 3, 5, 1, 9, 2]
i=1, key=3   : [3, 7, 5, 1, 9, 2]   1 karşılaştırma, 1 kaydırma
i=2, key=5   : [3, 5, 7, 1, 9, 2]   2 karşılaştırma, 1 kaydırma
i=3, key=1   : [1, 3, 5, 7, 9, 2]   3 karşılaştırma, 3 kaydırma
i=4, key=9   : [1, 3, 5, 7, 9, 2]   1 karşılaştırma, 0 kaydırma
i=5, key=2   : [1, 2, 3, 5, 7, 9]   5 karşılaştırma, 4 kaydırma

Toplam 12 karşılaştırma, 9 kaydırma. Kontrol etmenin güzel bir yolu var: kaydırma sayısı dizideki ters çift (inversion) sayısına eşittir. Ters çiftler: (7,3), (7,5), (7,1), (7,2), (3,1), (3,2), (5,1), (5,2), (9,2) — tam 9 tane.

Soru 4: Merge Sort — Bölme ve Birleştirme Ağacı

Soru: [38, 27, 43, 3, 9, 82, 10] dizisi için merge sort'un birleştirme adımlarını sırasıyla yazın.

Çözüm: mid = (left + right) / 2 ile 7 elemanlı dizi 4 + 3 olarak bölünür. Birleştirmeler özyinelemenin bitiş sırasıyla gerçekleşir:

Bölme:  [38, 27, 43, 3]                 [9, 82, 10]
        [38, 27]   [43, 3]              [9, 82]   [10]

1) [38] + [27]            -> [27, 38]                      1 karşılaştırma
2) [43] + [3]             -> [3, 43]                       1 karşılaştırma
3) [27, 38] + [3, 43]     -> [3, 27, 38, 43]               3 karşılaştırma
4) [9] + [82]             -> [9, 82]                       1 karşılaştırma
5) [9, 82] + [10]         -> [9, 10, 82]                   2 karşılaştırma
6) [3, 27, 38, 43] + [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]   6 karşılaştırma

Toplam 14 karşılaştırma. Dikkat: sol yarı tamamen bitmeden sağ yarıya geçilmez; 4. adımı 2. adımdan önce yazarsan özyineleme sırasını yanlış göstermiş olursun.

Soru 5: Quick Sort — İlk Bölümleme

Soru: [10, 80, 30, 90, 40, 50, 70] dizisinde pivot son eleman olacak şekilde Lomuto bölümlemesini uygulayın. İlk bölümlemeden sonra dizi nedir?

Çözüm: pivot = 70, i = -1. j soldan sağa ilerler; pivottan küçük her eleman i artırılıp a[i] ile takas edilir.

j=0 (10 < 70)  i=0  [10, 80, 30, 90, 40, 50, 70]
j=1 (80)       -    [10, 80, 30, 90, 40, 50, 70]
j=2 (30 < 70)  i=1  [10, 30, 80, 90, 40, 50, 70]
j=3 (90)       -    [10, 30, 80, 90, 40, 50, 70]
j=4 (40 < 70)  i=2  [10, 30, 40, 90, 80, 50, 70]
j=5 (50 < 70)  i=3  [10, 30, 40, 50, 80, 90, 70]
Son takas a[4] <-> a[6]:  [10, 30, 40, 50, 70, 90, 80]

Pivot 70, 4. indekse, yani nihai yerine oturdu. Özyineleme [10, 30, 40, 50] ve [90, 80] parçalarıyla devam eder; sağ parça bir bölümlemeyle [80, 90] olur. Tüm sıralama 6 + 3 + 2 + 1 + 1 = 13 karşılaştırma tutar.

Soru 6: Quick Sort'un En Kötü Durumu ve Pivot Seçimi

Soru: Pivot her zaman son elemansa [1, 2, 3, 4, 5, 6] dizisinde kaç karşılaştırma yapılır? Bu durum nasıl önlenir?

Çözüm: Dizi sıralı olduğu için pivot her seferinde en büyük elemandır; bölümleme n−1 elemanlık bir parça ve boş bir parça üretir. Karşılaştırmalar 5 + 4 + 3 + 2 + 1 = 15 = n(n−1)/2 olur, yani O(n²). Özyineleme derinliği de n'e çıkar, ek bellek O(n) olur. Aynı şey ters sıralı dizide ve pivot ilk eleman seçildiğinde de yaşanır.

Çözüm pivotu girdiden bağımsız seçmektir: rastgele pivot ya da ilk-orta-son elemanların ortancası (median-of-three).

// Partition'ın başına eklenir: rastgele elemanı sona al, gerisi aynı
int r = Random.Shared.Next(low, high + 1);
(a[r], a[high]) = (a[high], a[r]);

Rastgele pivot en kötü durumu yok etmez ama belirli bir girdiye bağlı olmaktan çıkarır; beklenen süre O(n log n) olur.

Soru 7: Hangisi Kararlı? Küçük Bir Senaryo

Soru: İsme göre sıralı kayıtlar nota göre sıralanacak: (Ali,85), (Berk,70), (Can,85), (Deniz,70). Selection sort ve insertion sort'un çıktısını karşılaştırın.

Çözüm:

Selection sort:
1. geçiş : (Berk,70), (Ali,85), (Can,85), (Deniz,70)
2. geçiş : (Berk,70), (Deniz,70), (Can,85), (Ali,85)   <- Ali, Can'ın arkasına düştü
3. geçiş : değişiklik yok

Insertion sort:
Sonuç    : (Berk,70), (Deniz,70), (Ali,85), (Can,85)

Selection sort'taki uzun mesafeli takas Ali'yi Can'ın arkasına attı: eşit notlu iki kaydın sırası bozuldu, algoritma kararlı değil. Insertion sort yalnızca kesin büyük olanları kaydırdığı için isim sırasını korudu. Gerçek kodda aynı ayrım geçerlidir: .NET'te Array.Sort ve List<T>.Sort kararsız, LINQ OrderBy kararlıdır.

var students = new[] { ("Ali", 85), ("Berk", 70), ("Can", 85), ("Deniz", 70) };
var byGrade = students.OrderBy(s => s.Item2).ToArray(); // eşit notlarda isim sırası korunur

Soru 8: Neredeyse Sıralı Veri ve Karşılaştırma Sınırları

Soru: (a) [1, 2, 4, 3, 5, 6, 8, 7] gibi neredeyse sıralı bir dizi için hangi algoritmayı seçersiniz, neden? (b) 4'er elemanlı iki sıralı dizi birleştirilirken en az ve en çok kaç karşılaştırma yapılır?

Çözüm (a): Insertion sort. Çalışma süresi O(n + d)'dir; d ters çift sayısıdır. Bu dizide d = 2 olduğundan 9 karşılaştırma ve 2 kaydırma yeter. Selection sort aynı dizide her koşulda 28 karşılaştırma yapar. Erken çıkışlı bubble sort 7 + 6 = 13 karşılaştırmayla bitirir ama dizinin sonunda küçük bir eleman varsa (örneğin [2, 3, 4, 5, 1]) o eleman her geçişte yalnızca bir adım sola gelir ve geçiş sayısı n'e yaklaşır. Merge sort ise girdinin sıralı olmasından hiç yararlanmaz.

Çözüm (b): En az 4: bir dizinin tüm elemanları diğerinden küçükse ([1,2,3,4] + [5,6,7,8]) dört karşılaştırmadan sonra dizi tükenir, kalan kopyalanır. En çok n + m − 1 = 7: elemanlar dönüşümlü geliyorsa ([1,3,5,7] + [2,4,6,8]) son elemana kadar her adımda karşılaştırma gerekir.

Ne Zaman Kullanılır, Ne Zaman Kullanılmaz?

• Insertion sort: küçük diziler (birkaç on eleman) ve neredeyse sıralı veri. Büyük, rastgele veride kullanılmaz.
• Merge sort: kararlılık ve garantili O(n log n) gerekiyorsa, bağlı liste ya da diske sığmayan veri sıralanıyorsa. O(n) ek bellek sorunsa kullanılmaz.
• Quick sort: bellek içi genel amaçlı sıralama; iyi pivot seçimiyle pratikte hızlıdır. Kararlılık gerekiyorsa ya da en kötü durum kabul edilemezse merge sort veya heap sort seçilir.
• Bubble ve selection sort: öğretim amaçlıdır. Üretim kodunda kendi sıralamanı yazmak yerine Array.Sort ya da OrderBy kullan; bu algoritmaları bilmenin değeri, o hazır metotların davranışını ve maliyetini anlayabilmektir.

Sıralı veriyi sürekli ekleme-silme yaparak tutman gerekiyorsa tekrar tekrar sıralamak yerine binary search tree gibi sıralı bir yapı daha doğru araçtır.

Sık Yapılan Hatalar

1. İç döngü sınırını yanlış yazmak. j < a.Length yazarsan a[j + 1] dizinin dışına taşar ve program IndexOutOfRangeException ile çöker. Doğrusu j < a.Length - 1 - i'dir; - i kısmını unutmak çöküşe değil gereksiz karşılaştırmaya yol açar.

2. Kararlılığı tek karakterle bozmak. Insertion sort'ta a[j] > key yerine >=, merge'de <= yerine < yazarsan algoritma hâlâ doğru sıralar ama eşit elemanların sırası değişir. Belirtisi sinsi: sayılarla test geçer, kayıt sıralarken sıra bozulur.

while (j >= 0 && a[j] >= key) // YANLIŞ: eşit elemanı da kaydırır, kararlılık gider
while (j >= 0 && a[j] > key)  // DOĞRU

3. Selection sort izinde her küçük elemanda takas yapmak. Selection sort geçiş başına en fazla bir takas yapar. Tarama sırasında bulduğun her küçük elemanı hemen takas edersen başka bir algoritmanın izini yazmış olursun ve ara diziler cevap anahtarıyla tutmaz.

4. "Quick sort O(n log n)'dir" deyip geçmek. Bu ortalama durumdur. Soru en kötü durumu soruyorsa cevap O(n²)'dir ve hangi girdi-pivot ikilisinin buna yol açtığını da yazman beklenir.

Bu soru tiplerini kendi dersinin çıkmış sorularıyla çalışmak istersen sınav destek sayfasında nasıl ilerlediğimi anlattım.

Sık Sorulan Sorular

Sınavda en çok hangi sıralama algoritması sorulur?

İz sorularında bubble, selection ve insertion sort; analiz sorularında merge sort'un özyinelemesi ve quick sort'un en kötü durumu öne çıkar. Beşini de elle izleyebilecek kadar çalışmak en güvenli yoldur.

Quick sort en kötü durumda O(n²) iken neden bu kadar yaygın?

Yerinde çalışır, önbellek dostudur ve rastgele ya da median-of-three pivotla en kötü durum pratikte çok nadirdir. Ortalama durumda sabit çarpanları merge sort'tan küçük olma eğilimindedir.

Kararlı sıralama ne zaman gerçekten önemlidir?

Aynı veriyi art arda birden fazla anahtara göre sıraladığında. Önce isme, sonra nota göre sıralayıp eşit notlarda isim sırasının korunmasını istiyorsan ikinci sıralamanın kararlı olması gerekir.

Karşılaştırma sayısı sorusunda neyi saymalıyım?

Yalnızca iki veri elemanının kıyaslandığı işlemleri say; j >= 0 gibi indeks kontrolleri sayılmaz. Hocanın tanımı farklıysa onu kullan ve cevabın başında neyi saydığını belirt.