Paylaşım Noktası

Quicksort algoritması, yapısındaki basitlik ve çalışmasındaki hızlılığa bağlı olarak günümüz bilgisayar sistemlerinde önemli yer etmiş bir sıralama algoritmasıdır.

1960 yılında küçük bir İngiliz şirketi olan Elliot Brothers'ta çalışan C. A. R. Hoare tarafından geliştirilmiştir.

Θ(nlogn) çalışma zamanında çalışan algoritmanın çalışma şekli çok basittir:

1. Sıralanmak istenen veri kümesinden bir sayı pivot olarak seçilir. (Genelde dizinin en son elemanıdır)
2. Veri kümesindeki her eleman tek tek kontrol edilir. Pivotun değerinden küçük elemanlar pivotun sol tarafına, büyük elemanlar pivotun sağ tarafına taşınır.
3. Pivotun sağ ve sol tarafı şeklinde 2 veri kümesine ayrılır ve algoritma tarafından tekrar işlenir.

Yukarıdaki basamaklar, fonksiyona giren veri kümesinde 1 eleman kalıncaya kadar devam eder. Sonunda tüm veri kümeleri bir araya getirilir.

Pseudocode:

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Örnek C++ kodu:

void quickSort(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--;
            }
      };

      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

C++, Algoritma sıralama algoritmalaları, quicksort