Quick Sort
Quick Sort bilgisayar alanında yaygın olarak kullanılan böl ve fethet algoritmasıdır. Algoritma da veri dizisini bir noktada 2 parçaya bölme işlemi yapıldığı için bir yandan merge sort algoritmasına da benziyor diyebiliriz. Algoritmanın işleyişine gelecek olarak kısaca veri dizimizin içerisinde bir adet pivot seçimi yapıyoruz. Seçtiğimiz pivotun sol tarafına pivottan küçük olan sayıları sağ tarafına ise pivottan büyük sayıları yerleştiriyoruz.
Algoritma adımları :
- Veri dizisi içerisinde bir adet pivot seçimi.
- Dizinin ilk öğesini sol işaretçi olarak seç.
- Dizinin son öğesini sağ işaretçi olarak seç.
- Sol işaretçi pivot değerinden küçük ise sağ tarafa doğru bir adım ilerlet. (index +1)
- Sağ işaretçi pivot değerinden büyük ise sola doğru bir adım geri al. (index -1)
- Solda yer alan işaretçi sağdakinden küçük veya eşit ise işaretçilerin değerlerini takas et. (swap)
- Sol işaretçi bir adım sağa ve sağ işaretçiyi bir adım sola al.
- İşaretçiler buluşmuyor ise birinci adıma geri dön.
Quick Sort Algoritması için bir örnek yapalım.
Yukarıdaki resimde sıralanmamış bir sayı dizisi görüyoruz. Bu veri dizisini Quick Sort algoritması ile sıralayacağız. İlk adımımız dizi içerisinde pivot seçimi yapmaktır. Peki pivot olarak hangi elemanı seçmemiz gerekiyor ? Araştırmalarım sonucunda algoritma ilk çıkış zamanında pivotun ilk eleman olarak seçildiği kanısına rastladım. Başka yazılarda ise pivotu başka elemanlardan seçerek algoritmanın performansını arttırabileceğimiz hakkında iddialara da rastladım. Biz bu yazımızda ilk elemanı pivot olarak seçeceğiz.
Evet, pivotumuzu seçtiğimize göre yapmamız gereken bir sonraki adım bu dizi içerisinde sol ve se sağ işaretleyiciyi eklemek.
İşaretçilerimizi ekledik. Şimdi karşılaştırmamızı yapalım. Sol işaretçi 28 değerini gösteriyor ve bu değer pivot olarak seçtiğimiz 21 sayısından büyük durumda. Sağ işaretçimiz 17 değerini gösteriyor bu değer pivot değerimizden küçük durumda. Bu iki değeri swap ediyor ve index değerlerini kuralımıza göre değiştiriyoruz.
İşlemimizi gerçekleştirdikten sonra durum yukarıdaki gibi oluyor. Bu durum aynı geçtiğimiz işlemin gerçekleşmesini sağlayan durum ile aynı. Sol işaretçi pivottan büyük durumda ve sağ işaretçi pivottan küçük durumda. Aynı şekilde takas işlemini gerçekleştirecek ve indexleri kuralımıza göre değiştiriyoruz. Hemen değiştirmeden evvel bir noktaya dikkat çekmek istiyorum. Örneğin sağ işaretleyici pivottan büyük olsaydı ne olacaktı ? Bu durumda işaret ettiği değer zaten yerinde olduğu için bir sonraki değere direkt geçiş sağlayacaktı. Takas işlemini gerçekleştirelim.
Sol işaretçi yine pivottan büyük ve sağ işaretçi pivottan küçük. Son swap işlemimizi gerçekleştiriyoruz ve veri dizimizi inceliyoruz.
Sol kısımda olan sayılar pivottan küçük sayılar, sağ kısımda olan sayılar pivottan büyük sayılar olarak yerlerini alıyorlar. Bu durumdan sonra 2 tarafa da Quick Sort algoritması uygulanıyor ve dizimiz sıralanmış oluyor.
Quick Sort Algoritmasının Java Programlama dili ile uygulanışı : Github
Kaynaklar :
https://medium.com/karuna-sehgal/a-quick-explanation-of-quick-sort-7d8e2563629b
https://www.geeksforgeeks.org/quick-sort/
https://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm
https://www.softwaretestinghelp.com/quicksort-in-java/
http://bilgisayarkavramlari.com/2008/08/09/hizli-siralama-algoritmasi-quick-sort-algorithm/
