18 Ağustos 2014 Pazartesi

Quick Sort

Quick Sort, eleman kümesi içerisinde seçilen pivot sayının diğer sayılarla karşılaştırılarak büyüklük ve küçüklük durumuna göre pivot sayının sağ ve sol tarafına yerleştirilmesi sonucu oluşan sıralama algoritmasıdır. Quick sort algoritmasını Türkçe kaynaklarda ‘Hızlı Sıralama Algoritması’ olarak görebilirsiniz.

Quick sort algoritması, sürekli olarak aynı mantık ile eleman kümesinden pivot sayı seçip karşılaştırma yaptığı için recursive fonksiyon ile çözüme kavuşturulması daha uygundur.

En kötü durum performansı (worst case performance) O(n²)‘dir. En iyi durum performansı O(n log n)‘dir. Ortalama durum performansı ise yine O(n log n) kabul edilir.

Rastgele üretilmiş sayıları temsil eden çubukların quick sort algoritması ile nasıl sıralandığını aşağıda vermiş olduğum animasyonda görebilirsiniz.

Tanımlardan anlam çıkartmakta güçlük çeken arkadaşlarımızın bu animasyonları dikkatle incelemesini tavsiye ederim. Quick sort algoritmasını biraz daha somut bir örnekle inceleyelim.

9 elemanlı kümenin (dizi) quick sort diyagramı ile hangi adımlardan geçerek sıralandığını dikkatle incelediğimizde bölünen her birimin kendine özel pivot sayısı olduğunu daha net görmüş olduk.

Diyagramı adım adım takip ettiğinizde, inanıyorum ki çalışma mantığı kafanızda oturmaya başlamıştır. Şimdi 8 elemanlı dizimizin quick sort algoritması ile sıralanmasını animasyon üzerinde inceleyelim.

Animasyon içerisinde ilk olarak 3 sayısını pivot olarak belirledik. Kendinden küçükleri sol, büyükleri sağ tarafına aldık. Ardından 3 sayısının sol tarafında kalan sayılar içerisinde 1 sayısını pivot olarak belirledik ve sıralama yaptık. Sonraki adımda 3 sayısının sağ tarafında kalan sayılar içerisinde 4 sayısını pivot olarak belirledik. Yani işlemimiz dallanmaya başladı. Bu şekilde yalnızca pivot sayı tek kalana kadar işlemimizi sürdürüyoruz. Son hamlemizde ise sıralamanın tamamlandığını görmüş oluyoruz. Uygulama üzerinde görürsek daha yararlı olur herhalde.

C# Console Uygulaması

static void Main(string[] args)

{

int[] dizi = new int[] { 6, 5, 3, 1, 8, 7, 2, 4 };

siralamayap(dizi, 0, dizi.Length - 1);

}

public static int parca(int[] dizi, int sol, int sag)

{

int i = sol, j = sag;

int gecici;

int pivot = dizi[(sol + sag) / 2];

while (i <= j)

{

  while (dizi[i] < pivot) i++;

  while (dizi[j] > pivot) j--;

  if (i <= j)

  {

     gecici = dizi[i];

     dizi[i] = dizi[j];

     dizi[j] = gecici;

     i++;

     j--;

  }

};

return i;

}

public static void siralamayap(int[] dizi, int sol, int sag)

{

int index = parca(dizi, sol, sag);

if (sol < index - 1) siralamayap(dizi, sol, index - 1);

if (index < sag) siralamayap(dizi, index, sag);

}

Java

int partition(int arr[], int left, int right)

{

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };

      return i;

}

void quickSort(int arr[], int left, int right) {

      int index = partition(arr, left, right);

      if (left < index - 1)

            quickSort(arr, left, index - 1);

      if (index < right)

            quickSort(arr, index, right);

}

C++

void quicksort(int a[],int left,int right){

int i=left,j=right;
int tmp;
int pivot=a[(left+right)/2];
while(i<=j){
while(a[i]<pivot)
i++;
while(a[j]>pivot)
j--;
if(i<=j){
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
i++;
j--;
}

}
if(left<j)
quicksort(a,left,j);
if(i<right)
quicksort(a,i,right);

for(int i=0;i<10;i++){
cout<<a[i]<<" ";
}
cout<<endl;
}