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 log2n 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ç nlog2n olarak bulunmaktadır.
« Birleştirme Sıralaması (Merge Sort) | Seçerek Sıralama (Selection Sort) »
Yorumlar
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
- Visual Basic ile Gösterici (Pointer) Kullanımı
- Hasse Çizgeleri (Hasse Diagrams)
- Zeki Vekiller (Akıllı Ajanlar, Intelligent Agents, Zeki Etmenler )
- Integral Kriptoanalizi ( Toplam Tecessüsü , Integral Cryptoanalysis)
- Diferansiyel Kriptoanalizi ( Fark Tecessüsü , Differential Cryptoanalysis)
- Sierpinski Üçgeni (Sierpinski Triangle)
- C ile programlamaya giriş final sınavı çözümleri
- Çok Seviyeli Sıralar (Multi Level Queues)
- Çift Özetleme (Double Hashing)
- İkinci Dereceden Sondalama (Quadratic Probing)
Yapılan Son Yorumlar
- Şadi Evren ŞEKER: Sıralama işleminiz poligonu...
- Şadi Evren ŞEKER: bahsettiğiniz sıralama algoritması...
- Abdurrahman ulusoy: merhaba hocam. gelişigüzel...
- Oguz Okutan: Merhaba hocam.. Fonksiyonlarda degere göre...
- Şadi Evren ŞEKER: Null, NULL, nil veya null olarak...
- Fatih Kabakci: hocam merhabalar,...
- kara: Çok güzel anlatılmış gerçekten teşekkürler...
- Şadi Evren ŞEKER: Bahsettiğiniz şekil dönüşümü...
- Caner: Kullanıcıdan açı girdisi almıyorsanız...
- Furkan Yediyildiz: Algoritmanin mantigi cok güzel...
- havva: çok sağolun çok güzel açıklamalar var tşk...
- Şadi Evren ŞEKER: typedef komutu, bir yapıdan yeni bir...
- fatih kabakci: hocam ben structures ile ilgili bir sorum...
- Şadi Evren ŞEKER: evet, yukarıda açıklanan, herhangi...
- Abdurrahman ulusoy: fi açısından teta kadar döndürme...
- Şadi Evren ŞEKER: Hayır yok, bir noktanın, herhangi...
- Abdurrahman ulusoy: Bu durumda yukarıdaki formüllerin...
- Abdurrahman ulusoy: Merhaba hocam Üstteki mesajımda...
- mustafa ekmekcioğlu: merhaba şadi bey ben hacettepe...
- Şadi Evren ŞEKER: Talebiniz üzerine...
Yakın Yazılar
Sıralama Algoritmaları (Sorting Algorithms)
Sokma Sıralaması (Ekleme Sıralaması, Insertion Sorting)
Sallayıcı Sıralaması (Shaker Sort)
Buket Sıralaması (Bucket Sort)
Harici Sıralama (External Sort)
Serseri sıralaması (Stooge Sort)
Yerleşim Sıralaması (Topological Sort, İlinge Sıralaması)
Hızlı Sıralama Algoritması (Quick Sort Algorithm)
İkili Arama Algoritması (Binary Search Algorithm)
Dolaylı sıralama (Indirect Sort, Gayrimüstakim sıralama)
Sayarak Sıralama (Counting Sort)
Arama Algoritmaları (Search Algorithms)
Çokgenlerin Doldurulması (Filling Polygons)
Genişletilmiş Ufak Şifreleme Algoritması (Extended Tiny Encryption Algorithm (XTEA))
Bağlantılar
Teşekkürler, gayet güzel ve anlaşılır bir anlatım olmuş.
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)
hatayı düzelttim, ilginiz için teşekkürler
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.)