Quick Sort (Hızlı Sıralama) Algoritması

Quick Sort (Hızlı Sıralama) algoritması C.A.R.Hoare tarafından bulunan etkin bir sıralama yöntemidir. Siyaset biliminde çok kullanılan “böl ve yönet” stratejisine dayanan basit ve hızlı bir sıralama yöntemi kullanır. 

Algoritma, başlarken dizinin terimleri arasından bir terimi mihenk (pivot) olarak seçer. Sonra verilen diziyi üç alt diziye ayrıştırır. Mihenk’ten küçük olan terimlerin hepsini (soldaki) birinci altdiziye taşır. İkinci alt dizi biricik öğesi mihenk olan tek terimli {mihenk} altdizsidir. Mihenk’ten büyük olan terimlerin hepsini (sağdaki) ikinci altdiziye taşır. Sonra sol ve sağ altdizilere aynı ayrıştırma yöntemini, altdiziler tek terimli birer diziye indirgenene kadar uygular ve sıralama işlemi biter. Algoritma özyinelemelidir (recursive).

Çalışma Prensibi

• Bir pivot öğesi seçilir.
• Dizi yeniden düzenlenir. Dizinin elemanları, pivottan küçük olan elemanlar sola ve pivottan büyük olan elemanlar sağa gelecek şekilde yeniden düzenlenir.

• Pivot elemana bir işaretçi sabitlenir. Pivot eleman, ilk indekten başlayan elemanlarla karşılaştırılır.
• Eleman pivot elemandan büyükse, bu eleman için ikinci bir işaretçi ayarlanır. 
• Pivot diğer elemanlarla karşılaştırılır. Pivot elemandan daha küçük bir elemana ulaşırsa, küçük eleman daha önce bulunan daha büyük elemanla değiştirilir.
• Bir sonraki daha büyük elemanı ikinci işaretçi olarak ayarlamak için işlem tekrarlanır. Ve bunu başka bir küçük elemanla değiştirin.
• Süreç ikinci son elemana ulaşılana kadar devam eder.
• Son olarak, pivot eleman ikinci işaretçi ile değiştirilir.
• Pivot elemanlar yine sol ve sağ alt parçalar için ayrı ayrı seçilir. Ve 2. adım tekrarlanır.

Quick Sort Algoritmasının Pseudocode

quickSort(array, leftmostIndex, rightmostIndex)
  if(leftmostIndex < rightmostIndex)
    pivotIndex <- partition(array, leftmostIndex, rightmostIndex)
    quickSort(array, leftmostIndex, pivotIndex - 1)
    quickSort(array, pivotIndex, rightmostIndex)

partition(array, leftmostIndex, rightmostIndex)
  set rightmostIndex as pivotIndex
  storeIndex <- leftmostIndex - 1
  for i <- leftmostIndex + 1 to rightmostIndex
  if element[i] < pivotElement 
    swap element[i] and element[storeIndex]
    storeIndex++
  swap pivotElement and element[storeIndex+1]
return storeIndex + 1

Java ile Quick Sort Algoritması

import java.util.Arrays;
class Quicksort {
  static int partition(int array[], int low, int high) {
    int pivot = array[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
      if (array[j] <= pivot) {   
        i++;
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }

    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return (i + 1);
  }

  static void quickSort(int array[], int low, int high) {
    if (low < high) {
      int pi = partition(array, low, high);
      quickSort(array, low, pi - 1);
      quickSort(array, pi + 1, high);
    }
  }
}

class Main {
  public static void main(String args[]) {
    int[] data = { 8, 7, 2, 1, 0, 9, 6 };
    System.out.println("Unsorted Array");
    System.out.println(Arrays.toString(data));

    int size = data.length;
    Quicksort.quickSort(data, 0, size - 1);

    System.out.println("Sorted Array in Ascending Order: ");
    System.out.println(Arrays.toString(data));
  }
}

^{Quick Sort Algoritması animasyonu}