Kodlama Merkezi Yazılımcı Dostu Paylaşım Merkezi
Quick sort algoritması türkçe adıyla hızlı sıralama algoritması, günümüzde hala sıklıkla kullanılan bir algoritmadır. Sıralanması istenen dizi, dizi içerisinden belirlenen bir nokta (pivot noktası) yardımıyla iki alt diziye ayrılır. Pivot noktasından küçük olan elemanlar soldaki birinci alt diziye, büyük olan elemanlar ise sağdaki ikinci alt diziye taşınır. Daha sonra, yine aynı algoritma rekürsif olarak çağrılarak bu alt dizilerin sıralanması istenir. Bu işlem diziler parçalanamayacak duruma gelene kadar sürdürülür.
Örneğin sıralanacak dizi A={9,5,12,7,3,21} olsun. Şimdi bir pivot noktası belirleyelim. Pivot noktası seçimi algoritmanın çalışma prensibini etkilemese de, dizinin ortanca değerini pivot noktası olarak belirlemekte fayda var. Dizinin ilk indisi 0 ve son indisi 5’i toplayıp int türünde bir değişkene attığımızda, 2. indis numaralı dizi elemanını yani 12 değerini pivot noktası olarak belirleriz. Bu noktayı baz alarak 12 değerinden küçük sayıları soldaki diziye, büyük sayıları ise sağdaki diziye atalım. Alt dizilerimizin son durumu A1={9,5,3,7} ve A2={12,21} şeklinde oluştu. Pivot noktasını da sağdaki yada soldaki diziye dahil edebilirsiniz. Daha sonra sıralama algoritması rekürsif olarak tekrar çağrılır ve yukarıdaki işlemler tekrarlanır. Böylece dizinin öğeleri küçükten-büyüğe doğru sıralanmış olur.
Aşağıda quick sort sıralama algoritmasının java ile yazılmış örnek kodlarını inceleyebilirsiniz.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public class HizliSiralama { public static void main(String[] args) { int []dizi={9,5,12,7,3,21}; hizliSirala(dizi, 0, dizi.length-1); for (inti = 0; i < dizi.length; i++) System.out.print(dizi[i]); } public static int[] hizliSirala(intdizi[], intsol, intsag) { intpivot, gecici, i,j; i=sol; j=sag; pivot=dizi[(sol+sag)/2]; do { while(dizi[i]<pivot&& i<sag) i++; while(pivot<dizi[j]&&j>sol) j--; if(i<=j){ gecici=dizi[i]; dizi[i]=dizi[j]; dizi[j]=gecici; i++; j--; } } while (i<=j); if (sol<j) hizliSirala(dizi, sol, j); if (i<sag) hizliSirala(dizi, i, sag); returndizi; } } |
Yukarıda java kodları verilen hızlı sıralama algoritmasına üç adet parametre gelmektedir; biri dizi, diğer ikisi de dizinin sıralamaya koyulacak parçasının sol ve sağ taraflarının indis değerleridir. Algoritma ilk çağrıldığında, n elemanlı bir dizi için sol=0, sağ=n-1 olur. Rekürsif çağırmalar sırasında sol değeri büyürken sağ değeri küçülecektir; ne zaman ki, sol değeri sağdan büyük olursa dizide bölünecek eleman kalmadığı anlaşılır ve rekürsif çağırmaların geri dönüşü başlar.
Hızlı sıralama algoritmasının ortalama zaman karmaşıklı O(nlog2n), en kötü durumda ki zaman karmaşıklığı ise O(n2) olarak çıkmaktadır.
