Veri Yapıları · Ünite 4

Sıralama Algoritmaları (C#)

1. Sıralama algoritması nedir?

Sıralama, çok sayıda ögeyi küçükten büyüğe, büyükten küçüğe, kısadan uzuna gibi bir ölçüte göre düzenleme işlemidir. Telefon rehberi alfabetik, kargo dağıtımı adrese göre, alışveriş sitesi fiyata ya da tarihe göre sıralar. Bilgisayarda en çok yapılan iki iş sıralama ve aramadır; bu yüzden en çok araştırılan konular arasındadır.

Sıralama algoritması, sırasız bir listeyi girdi olarak alıp üzerinde işlemler yapan ve sıralı bir dizi çıktı veren algoritmadır. Hepsi görünüşte aynı işi yapar; onları ayıran şey performans, yani çalışırken harcadıkları kaynak ve süredir.

• →Küçük veride (ör. 1000 eleman) fark milisaniyelerdir, kimse fark etmez.
• →Veri büyüdükçe kötü seçilmiş algoritma saniyeler, hatta dakikalar kaybettirir. Alışveriş sitesinde «fiyata göre sırala»ya basan kullanıcı beklerse siteyi terk eder.
• →Bu yüzden algoritma seçerken çalışılacak en büyük veri boyutu göz önüne alınır.

Sıralı veri başka algoritmaları da hızlandırır: arama ve birleştirme algoritmaları sıralı listeyle çok daha verimli çalışır. Sıralama ayrıca veriyi standart hâle getirir ve insanın okuyabileceği çıktılar üretir; veritabanlarında ve böl-yönet yöntemlerinde doğrudan kullanılır.

Test için bir dizi sınıfı

Algoritmaları denemek için önce küçük bir dizi sınıfı yazılır: eleman ekleyen, yazdıran ve diziyi sıfırlayan üç metot. Sıralama metotları da bu sınıfın içine eklenir.

class Dizi
{
    private int[] arr;
    private int sonIndis;      // boyut - 1
    private int adet = 0;      // eklenen eleman sayısı

    public Dizi(int boyut) { arr = new int[boyut]; sonIndis = boyut - 1; }

    public void Ekle(int x) { arr[adet] = x; adet++; }

    public void Yazdir()
    {
        for (int i = 0; i <= sonIndis; i++) Console.Write(arr[i] + " ");
    }

    public void Temizle()
    {
        for (int i = 0; i <= sonIndis; i++) arr[i] = 0;
        adet = 0;
    }
}

Algoritmayı sıralı veriyle denemek anlamsızdır; işini görmek için dizi rastgele, sırasız sayılarla doldurulur. C#'ın Random sınıfı bunu yapar: NextDouble() 0 ile 1 arasında bir sayı verir, 100 ile çarpıp int'e çevirince 0–99 arası bir tam sayı elde edilir.

Dizi d = new Dizi(10);
Random rnd = new Random(100);
for (int i = 0; i < 10; i++)
    d.Ekle((int)(rnd.NextDouble() * 100));
d.Yazdir();   // ör. 96 15 66 90 35 94 71 61 34 14

2. Baloncuk sıralama (bubble sort)

Baloncuk sıralama, listedeki elemanları yan yana ikişer ikişer karşılaştırıp yanlış sıradaysa yerlerini değiştiren algoritmadır. Büyük eleman her turda bir baloncuk gibi listenin sonuna doğru kayar; adını buradan alır.

• →Küçükten büyüğe (artan) sıralamada baloncuk sağa, büyükten küçüğe (azalan) sıralamada sola kayar.
• →Artan sıralamada büyük eleman sağa, küçük eleman sola alınır.
• →n elemanlı dizi en fazla n tur sonunda sıralanır. Her tur bittiğinde en sondaki eleman yerine oturmuş olur, bir sonraki tur ondan önce durur.

public void BaloncukSirala()
{
    for (int dis = sonIndis; dis >= 1; dis--)          // her turda sınır bir azalır
        for (int ic = 0; ic <= dis - 1; ic++)
            if (arr[ic] > arr[ic + 1])                   // komşular yanlış sıradaysa
            {
                int temp = arr[ic];                      // yer değiştir (swap)
                arr[ic] = arr[ic + 1];
                arr[ic + 1] = temp;
            }
}

3. Seçerek sıralama (selection sort)

Seçerek sıralama, dizinin sıralanmamış kısmındaki en küçük elemanı seçip o kısmın başına koyan algoritmadır. 1. adımda tüm dizideki en küçük eleman bulunur ve 0. indisle yer değiştirir; 2. adımda 1. indisten sona kadar bakılır ve en küçük 1. indise gelir; böyle devam eder.

public void SecerekSirala()
{
    for (int dis = 0; dis <= sonIndis; dis++)
    {
        int min = dis;                                   // en küçüğün indisi
        for (int ic = dis + 1; ic <= sonIndis; ic++)
            if (arr[ic] < arr[min]) min = ic;
        int temp = arr[dis];                             // en küçüğü başa al
        arr[dis] = arr[min];
        arr[min] = temp;
    }
}

4. Ekleme sıralama (insertion sort)

Ekleme sıralama, sıradaki elemanı alıp önceden sıralanmış elemanlar arasındaki doğru yerine ekleyen algoritmadır. Kitaplığa kitap dizmek gibi: soldan başlarsın, her yeni kitabı önceki kitapların arasında olması gereken yere koyarsın.

public void EklemeSirala()
{
    for (int dis = 1; dis <= sonIndis; dis++)
    {
        int temp = arr[dis];                             // yerleştirilecek eleman
        int ic = dis;
        while (ic > 0 && arr[ic - 1] >= temp)            // büyükleri bir sağa kaydır
        {
            arr[ic] = arr[ic - 1];
            ic--;
        }
        arr[ic] = temp;                                  // boşalan yere koy
    }
}

Fark: baloncuk ve seçerek sıralama elemanları yer değiştirerek çalışır; ekleme sıralama ise büyük elemanları sağa kaydırıp yeni geleni araya ekler. Dış döngü elemanları tek tek gezer, içteki while döngüsü sıradaki elemanı sıralı kısımda yerine yerleştirir.

5. Hızlı sıralama (quick sort)

Hızlı sıralama, diziden bir pivot eleman seçip diğer elemanları pivottan küçükler ve büyükler diye iki gruba ayıran, sonra her grubu aynı yöntemle özyinelemeli (recursive) olarak sıralayan algoritmadır. Dört algoritmanın en performanslısıdır, ama dikkatli yazılmazsa işlem yükü artar.

• →Pivot baştaki, sondaki ya da rastgele bir eleman olabilir. Kitaptaki kod grubun en sağındaki elemanı pivot alır.
• →Pivottan küçük eleman yoksa sol grup oluşmaz, yalnızca sağ grupla devam edilir (ve tersi).
• →Pivotun nerede seçildiği, algoritmanın başarısını etkileyen en önemli etkendir. Hep en küçük ya da en büyük eleman pivot olursa gruplar dengesiz bölünür ve algoritma yavaşlar.

public void HizliSirala() { HizliSirala(0, arr.Length - 1); }

void HizliSirala(int sol, int sag)
{
    if (sol < sag)                                       // en az 2 eleman varsa
    {
        int p = Parcala(sol, sag);                       // pivot yerine oturdu
        HizliSirala(sol, p - 1);                         // küçükler grubu
        HizliSirala(p + 1, sag);                         // büyükler grubu
    }
}

int Parcala(int sol, int sag)
{
    int pivot = arr[sag];                                // en sağdaki eleman
    int i = sol;                                         // küçüklerin yazılacağı yer
    for (int j = sol; j < sag; j++)
        if (arr[j] < pivot)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);         // küçüğü sola al
            i++;
        }
    (arr[i], arr[sag]) = (arr[sag], arr[i]);             // pivotu araya koy
    return i;
}

8 3 6 1 5 dizisinde pivot 5'tir. Parcala küçükleri (3, 1) sola toplar ve pivotu araya koyar: 3 1 5 8 6. Sonra sol grup (3 1) ve sağ grup (8 6) ayrı ayrı sıralanır ve sonuç 1 3 5 6 8 olur.

6. Hangisi ne kadar hızlı?

Dört algoritma aynı rastgele dizilerle çalıştırılıp süreleri Stopwatch ile ölçülür: StartNew() saati başlatır, Stop() durdurur, ElapsedMilliseconds geçen süreyi verir, Restart() sıfırlayıp yeniden başlatır. Her algoritmadan önce dizi Temizle() ile sıfırlanıp yeniden rastgele doldurulur.

Bu dördü dışında da sıralama algoritmaları var: yığınlama sıralaması (heap sort), sayarak sıralama (counting sort), taban sıralaması (radix sort), birleştirmeli sıralama (merge sort) ve şakayla karışık bogosort (rastgele karıştırıp sıralı mı diye bakar). Hangisinin seçileceği sıralanacak veriye bağlıdır.

Bu not ders kitabının yerine geçmez; konu kendi cümlelerimizle, yapay zekâ desteğiyle özetlendi.