Sıralama algoritmaları makale serimizin bu bölümünde Quick Sort yani hızlı sıralama algoritmasına değineceğiz. Bu algoritma dizideki orta nokta (mean) veya ortaya yakın bir değeri seçerek diğer bütün elemanları bu orta noktadaki elemana göre büyük veya küçük diye sınıflandırır. Daha sonra bu sınıflandırma içerisinde de en alt noktaya ulaşana kadar aynı sınıflandırmayı yapmaya devam eder. Bu açıdan parçala ve fethet yaklaşımlarından bir tanesidir. (Divide & Concouer)
Seçilen orta noktaya veya ortaya yakın olan noktaya eksen (pivot) denilmektedir. Diğer elemanlar bu eksen etrafında sıralanacaklardır. Seçilen pivot noktasından büyük elemanları sağ tarafa, küçük elemanları ise sol tarafa koyar. Bu aşamadan sonra pivot elemanın sağındakiler ve solundakilerden de yeni pivotlar seçilir ce onlar da Quick Sort mantığına göre sağ ve sol olarak sınıflandırılır. Bu şekilde sıralanırken bölünen diziler en son birleştirilir ve ortaya sıralanmış dizi çıkar. (Recursive)
Tam orta nokta yerine ortanın yanındaki değer pivot seçilerek yapılan örnekleri de görmemiz mümkündür.
Seçilen pivot raslantısal olarak en büyük veya en küçük değer olabilir. Böyle bir durumda sıralamada mantık değişmeyecektir.
Zaman Karmaşıklığı:
En kötü durumda Worst Case : O(N^2)
En iyi durumda Best Case: O(nlogn)
Örnek:
85,30,53,23,95,12,31,61,24,78 sayılarından oluşan dizi için Quick Sort algoritmasını uygulayalım.
- sayı dizisi içerisinden orta noktaya yakın olarak tercih ettiğim 53 sayısını pivot olarak seçiyorum.
- bu sayıdan büyükleri sağa küçükleri sola olacak şekilde yeniden yazıyorum. 30,23,12,32,24, 53 , 85,95,61,78
- Bu sayı gruplarından sol taraftakileri ve sağ taraftakilerin içerisinden yeni pivotlar seçiyor ve aynı işlemi yineliyorum.
- sol taraf için 24 pivot olsun. 12,23 < 53 < 24,30,31
- sağ taraf için pivot 78 olsun. 61,78 < 85,95
- 12,23 < 24 < 53 < 61 ,78 < 85,95 halini alacaktır. şimdi son gruplarımızdan yeni pivotlar daha seçelim.
- sol taraftaki 12,23 grubu için 23 pivot olsun. 12 < 23
- sağ taraftaki 85,95 grubu için 95 pivot olsun. 85 < 95
- şimdi gruplar artık bittiğine göre sayıları küçükten büyüğe doğru yazabiliriz.
- 12,23,24,30,31,53,61,78,85,95 şeklinde birleştirilerek sıralanmış olur.
Bu konuyla ilgili sorularınızı alt kısımda bulunan yorumlar alanını kullanarak sorabilirsiniz.
Referanslar
Algoritmalara Giriş: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
TAGs: Quick Sort, Sorting Algorithms, Hızlı Sıralama, Quick Sort nedir,Hızlı Sıralama nedir, Sıralama algoritmaları
