Yazan : Şadi Evren ŞEKER

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan dizideki orta noktada (mean) bulunan bir sayıyı seçerek diğer bütün sayıları bu orta sayıdan büyük veya küçük diye sınıflayarak sıralama yapmayı hedeflemektedir. Bu açıdan bir parçala fethet (divide and conquere) yaklaşımıdır. Ayrıca bu seçilen orta noktaya eksen (pivot) adı da verilir çünkü bütün diğer sayılar bu sayının ekseninde sıralanacaktır.

Sıralanmak istenen verimiz:

5,7,2,9,6,1,4,7 (düzeltildi, Erol Bey'e teşekkürler)

olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Yukarıda verilen bu örnek dizinin sıralanması adım adım aşağıda anlatılmıştır:

1. adım, dizinin ortasındaki sayı bulunur. Bu örnekte 8 sayı olduğu için ortadaki sayı 4. elemandır. Bu elemanın değeri de 9′dur. Bu durum aslında biraz bahtsız bir durumdur çünkü tesadüfen dizideki en büyük sayıdır. Bu mesele 2. adımda ortaya çıkacaktır.

2.adım: Diziden 1.adımda seçilen sayıya göre dizideki bütün elemanları küçük veya büyük diye sınıflandır. Tabi 1. adımda şanssız bir şekilde en büyük sayı seçildiği için bütün sayılar 9′dan küçük olarak sınıflandırılacaktır.

5,7,2,6,1,4,7 (9)

3. adım: Sınıflandırılana küçük ve büyük dizileri tekrar hızlı sıralamaya ver. Yani 5,7,2,6,1,4,7 dizisini aynı adımlarla tekrar sıralıyoruz.

4. adım: eleman sayımız 7 ve ortadaki eleman 3. eleman olan 6 olur. Dizideki sayılar 6′dan büyük ve 6′dan küçük diye sınıflandırılırsa:

5,2,1,4 (6) 7,7

olarak iki grup elde edilir. Bu grupları da sıralamak üzere tekrar hızlı sıralama algoritmasına veririz. Dolayısıyla 5,2,1,4 sayıları ayrı ve 7,7 sayıları ayrı ayrı sıralanacaktır.

5. adım 5,2,1,4 sayılarının orta değeri 2′dir ve sınıflandırılırsa:

1 (2) 4,5 bulunur. Aynı zamanda diğer dizi olan 7,7 sıralanırsa sonuç değişmez ve 7,7 bulunur.

6. adım 1 sıralanırsa 1 ve 4,5 sıralanırsa 4,5 bulunur.

7.adım. Bu adımdan sonra artık birleştirme işlemine geçilebilir. Buna göre 6. adımda sıralanan değerleri birleştirirsek :

1,2,4,5 değerleri elde edilir.

8.adım: 4. adımdaki sayılar birleştirilirse 1,2,4,5,(6),7,7 sayıları elde edilir.

9.adım: 2. adımdaki sayılar birleştirilirse 1,2,4,5,6,7,7 (9) olarak dizinin sıralanmış hali elde edilir.

Bu algoritmanın JAVA dilindeki karşılığı aşağıdaki şekilde yazılabilir:

  public static void quickSort(int A[],int p, int r)
{
    int q;
    if(p<r)
    {
        q=partition(A,p, r);
        quickSort(A,p, q-1);
        quickSort(A,q+1, r);
    }
}

Görüldüğü üzere yukarıdaki kod özyineli (recursive) bir koddur ve kendi içerisinde orta değeri bulmak için partition adı verile harici bir fonksiyonu çağırmıştır. Bu fonksiyonun kodu da aşağıda verilmiştir:

public static int partition(int A[],int p, int r){
    int tmp;
    int x = A[r];
    int i = p-1;

    for(int j=p; j<=r-1; j++)
    {
        if(A[j]<=x)
        {
            i++;
            tmp=A[i];
            A[i]=A[j];
            A[j]=tmp;
        }
    }
    tmp=A[i+1];
    A[i+1]=A[r];
    A[r]=tmp;
    return i+1;
}

Yukarıdaki bu orta nokta bulmaya yarayan fonksiyonun en büyük özelliği tek bir dizi kullanarak bu dizi içerisindeki indisi döndürmeye çalışmasıdır. Bu yüzden hangi parça üzerinde orta nokta aradığını alt ve üst limitleri parametre alarak bulur. Bu parametreler koddaki p ve r değişkenleridir.

Hızlı sıralamanın algoritma karmaşıklığına bakıldığında O(nlogn) olarak bulunur çünkü üzerinde çalışılan dizi her adımda en fazla 2ye bölünmüştür (Big-O hesaplanırken en kötü ihtimalin hesaplandığını hatırlayınız) böylece sonuç dizisi olan 2şer elemanlı dizilere log₂n adımda ulaşılabilir. Daha sonra her n eleman için sıralama yapıldığı ve her n eleman üzerinden geçildiği için bu değer çarpan olarak gelmekte ve sonuç nlog₂n olarak bulunmaktadır.

Örnek görsel çalışma

Yapılan yorumlardan sonra hızlı sıralama algoritmasının çalışmasını görsel bir örnek üzerinden göstermeye karar verdim.

Sıralayacağımız sayılar 88,31,52,25,98,14,30,62,23,79 olarak verilsin

Yukarıdaki bu sayıları sıralamak için öncelikle ortadaki değer (pivot) bulunur. Bu değer sayılar arasından rast gele seçilebileceği gibi dizinin ilk elemanı, son elemanı gibi belirli bir yerdeki sayı olarak da atanabilir. Bu değer yukarıdaki kodda verilen p değişkeni ile gösterilen değerdir. Biz örneğimizde 52 olarak seçtiğimizi düşünelim:

Yukarıdaki şekilde gösterildiği üzere sayı rast gele olarak seçildikten sonra, diğer sayılar, bu seçilen rast gele sayıdan (52) büyük ve küçük olarak sınıflandırılır.

Görüldüğü üzere problem iki parçaya bölünmüş ve burada parçala fethet (divide and conquere) yaklaşımı kullanılmıştır. Artık problemin her iki alt kümesi ayrı ayrı yeniden hızlı sıralama algoritmasına verilecek ve bir önceki adımda olduğu gibi sayılar arasından rast gele bir sayı seçilerek problemi alt parçalara bölecektir:

Yukarıdaki son şekilde görüldüğü üzere problem bir önceki adımda bulunan parçaların alt parçalara bölünmesi ile daha küçük hale getirilmiştir. Burada rast gele olarak seçilen pivot sayıları ilk grup için 25 ve ikinci grup için 79 olmuştur.

Problem son kez alt adımlara bölünerek çözülür

Görüldüğü üzere son adımda son kümeler için yine pivot seçimi yapılmış ve 23, 31, 98 sayıları pivot olarak seçilmiştir. Problem bu aşamadan sonra çözülmüştür çünkü bu sayıların alt grupları tek elemanlı kümeler haline gelmiştir.

Ardından her küme kendi pivotunun solunda veya sağında olmasına göre yukarı doğru toplanır. Bu toplama işlemi yukarıkida şeklin en altında gösterilmiştir.