Hızlı Sıralama Algoritması (Quick Sort Algorithm)

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.

« Birleştirme Sıralaması (Merge Sort) | Seçerek Sıralama (Selection Sort) »

Yorumlar

Toplam 4 yorum var.

mehmet usta | 30 Oct 2009, 19:07
Teşekkürler, gayet güzel ve anlaşılır bir anlatım olmuş.
ERol | 26 Dec 2009, 08:23
Merhaba,
yararli bir makale, emeginiz icin tesekkürler.
Fakat gördügüm bir yanlislik var :

ilk verdiginiz deger :

Sıralanmak istenen verimiz:

5,7,2,9,6,1,3,7

(buradaki 3 degeri 2. Asamada 4 olarak yaziliyor)
Şadi Evren ŞEKER | 26 Dec 2009, 12:29
hatayı düzelttim, ilginiz için teşekkürler
Bekir | 04 Jan 2010, 23:53
Teşekkürler hocam konuyu burdaki anlatım sayesinde daha iyi anladım fakat bir de c dilinde bir kod örneği yayınlayabilirseniz adım adım yorumlayarak tam oturcak konu hocam.İyi çalışmalar(aynı sıkıntı bubblesort,mergesort tada yapabilirseniz çok iyi olur hocam binary search te anlattığınız gibi.)

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Hızlı Sıralama Algoritması (Quick Sort Algorithm)' isimli yazı 09 Aug 2008 tarihinde, saat: 22:22 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 4530 defa okunmuştur.

Benzer yazıları JAVA, algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar