Merhaba arkadaşlar birilerine faydalı olabilir diye bırakıyorum, iyi çalışmalar.
Quick sort algorithm, yada Türkçesi ile hızlı sıralama algoritması birçok kaynağa göre en efektif sıralama algoritmasıdır. Ancak hangi sıralama algoritması daha iyidir, daha efektiftir diye bir yaklaşım doğru değildir. Burada asıl soru hangi durum için hangi sıralama algoritması daha iyidir olmalıdır. Bu yazımızda sizlere Quick Sort Algoritmasının çalışma mantığından bahsedip akış diyagramını paylaşacağız.
Quick Sort Algoritması
Quick Sort Algoritması, karmaşıklığı Big O da ortalama bir durumda n log
iken kötü durumlar için n kare seviyesine kadar gidebilir. Quick sort algoritması da algoritma kısmında bir önceki konuda bahsettiğimiz merge sort algoritması gibi parçala ve fethet (divide and conquer) mantığı ile çalışmaktadır. Quick sort algoritması en temelde şu şekildedir: Bir adet pivot eleman seçilir ve küçükten büyüğe sıralama yaptığımızı varsayarsak bu elemandan küçükler pivotun sol tarafında büyükler sağ tarafına atılır. Daha sonra başka bir eleman pivot seçilir ve bu işlem dizi sıralı hale gelene kadar devam eder.
Başka bir eleman pivot seçilir?? Hangi eleman? Bu soruya yanıt verebilmek için hangi quick sort algoritmasının seçildiğinin bilinmesi gerekir. Quick sort algoritmasında pivot elemanın baştaki eleman olduğu, ortadaki eleman olduğu, sondaki eleman olduğu veya rastgele seçildiği olmak üzere 4 farklı temel durum vardır. Bu yazıda quick sort algoritmasında pivot elemanı dizinin başındaki eleman seçerek sıralama işlemini nasıl gerçekleştireceğimizden bahsedeceğiz. Başlamadan önce aşağıdaki GIF üzerinden quick sort algoritmasının nasıl çalıştığı hakkında biraz daha fikir edinelim.
Quick Sort Algoritması Adımları
Aşağıda küçükten büyüğe sıralama için dizinin başındaki elemanı pivot seçerek uygulanan quick sort algoritmasının adımları verilmiştir.
Dizinin başındaki eleman pivot olarak seçilir.
Pivot elemandan büyük olanlar pivotun sağ tarafına, küçük olanlar ise pivotun sol tarafına yerleştirilir.
Pivotun sağ ve sol tarafında yer alan elemanlar ayrı 2 dizi olarak tekrardan aynı işlemlere tabi tutulur.
Bu işlemler tüm dizi sıralı olana kadar devam eder.
Bir örnek üzerinden quick sort algoritmasının çalışma prensibini daha iyi anlayalım. Daha sonrada quick sort algoritması akış diyagramına bir göz atalım.
Dizinin Başlangıç Durumu:
-5 10 0 25 2 12
Pivot = -5
-5 10 0 25 2 12
Pivot olan eleman dizinin tamamından küçük olduğundan bir değişim gerçekleşmedi. Pivotun sağ tarafı için aynı işlemi uygulayalım.
Pivot = 10
-5 0 2 10 25 12
Şimdi de pivot elemanının hem sağ (0 2) hemde sol tarafını (25 12) tekrardan aynı işleme tabi tutalım. İlkinde pivot 0 olur olur ve dizi değişmez (0 2). Diğerinde pivot 25 olur ve dizi (12 25) halini alır.
-5 0 2 10 12 25
Burada (0 2) ve (25 12) dizilerinde dizinin sağ ve sol taraflarında ya 0 yada 1 eleman olduğu için artık algoritma çalışmayı durdurur. Bu şekilde sıralı diziyi elde etmiş olduk.
Dizinin Son Durumu:
-5 0 2 10 12 25
Quick Sort Algoritması Akış Diyagramı
Quick sort algoritmasının çalışmasını bir örnek üzerinde de inceledikten sonra şimdide algoritmanın akış diyagramına bir göz atalım.
Fonksiyona dizi, dizinin ilk elemanının ve son elemanının adresi gelir.
Pivot ilk eleman olarak seçilir.
Eğer son eleman ilk elemandan büyük ise i ve j gibi iki sayaç değişkenine başlangıç ve bitiş elemanları atanır ve aşağıdaki işlemler yapılır. Eğer değilse herhangi bir işlem yapılmaz.
j sayaç değeri i sayaç değerinden büyük olduğu sürece pivot iden büyük olduğu sürece i artar, jden küçük olduğu sürece j azalır. Burada yapılmak istenen pivotun solunda pivottan büyük olan bir elemanla pivotun sağında pivottan küçük olan bir eleman bulmaktır.
Daha sonra bu iki eleman yer değiştirilir ve bu işlem j değeri i değerinden büyük olduğu sürece yapılır.
Son olarak ise dizinin pivottan küçük olan kısmı ve büyük olan kısmı ayrı ayrı aynı işlemlere tabi tutulur ve bu şekilde sıralı dizi elde edilir.
Kaynak