Merhaba Arkadaşlar,
Bu yazımızda Quick Sort algoritmasının nasıl işlediği hakkında bilgi vereceğim.
Sıralama Algoritmaları elimizde bulunan veri setlerinin sıralı bir şekilde tutulmasını amaçlayan algoritmalardır. Hızlı Sırlama algoritmasının çalışma mantığı diğer böl-yönet tarzındaki sıralama algoritmaları ile benzerlik göstermektedir. Bu sebep nedeni ile Ortalama çalışma zamanı O(n.logn) dir. En kötü durumda ise bu çalışma zamanı O(n²) olarak belirlenir. En kötü zamanda algortimanın n² olarak şekillenmesi dizinin ters ya da düz sıralı olma durumudur.
Quick Sort’taki çalışma mantığını anlatmak gerekirse, dizinin elemanları arasında bulunan bir terim pivot olarak seçilir. Pivot seçildikten sonra dizi iki parçaya ayrılmış olur. Burası önemli bir adımdır çünkü algoritmanın ilerleyişinin O(n.logn) seviyesine indirgenmesi dizinin bölüntülenme işleminin doğru şekilde ilerlemesi gerekir. Daha sonra bu bölüntüleme işlemi devam eder son adım olarak da birleştirme işlemi yapılır.
Yani;
1.Böl: Dizilimi pivot (eksen sabit) x’in etrafında iki altdizilime bölüntüle; burada soldaki altdizilim elemanları ≤ x ≤ sağdaki altdizilim elemanları olsun.
2.Fethet:İki altdizilimi özyinelemeli sırala.
3.Birleştir: Önemsiz (yerinde sıraladığı için).
Sözde kod olarak kısaca belirtecek olursak;
Quicksort(A,p,r)
if p<r
then q <- Partition(A,p,r)
Quicksort(A,p,q-1)
Quicksort(A,q+1,r)
-----
Partition(A,p,q)//Bölüntü Kısmı
x <- A[p]
i <- p
for j <- p+1 to q
do if A[j] ≤ x
then i <- i+1
exchange A[i] <-> A[j]
exchange A[p] <-> A[i]
return i
Hızlı sıralamanın sahte kodu yukarıdaki gibi olacaktır. Hızlı sıralamanın seçilen pivotu yerine yerleştirmesi 1 tur alır. 1 turun sonunda seçilen pivot doğru yerine ulaşmış olur. Bunu aşağıdaki örnek ile anlayabiliriz.
Başlangıçta “6” sayısı pivot seçilmiş ve bir turun sonunda ulaşması gereken yere ulaşmıştır.
Hızlı sıralama ve diğer sıralama algoritmaları ile ilgili simulasyon örneğine buraya tıklayarak ulaşabilir ve uygulamalı bir şekilde daha net görebilirsiniz.
Teşekkürler.
