Hızlı sıralama - Quick Sort

  Hızlı(Quick sort) sıralama algoritması çok hızlı algoritmalardan birisidir. Sadece eğitim amaçlı değil programların içerisinde de sıralama için kullanılmaktadır. Algoritma çok basittir ve yerinde sıralama yapar yani tek dizi üzerinde elemanların yerlerini değiştirerek işlem yapar. Böyle olması da zaman açısından ve alan açısından hız demektir.

Algoritmanın çalışma mantığı
  Sayı dizisinden herhangi bir sayıyı dayanak eleman(pivot) eleman olarak seç.
  Sayı dizisini dayanak elemandan(pivot) küçük olan tüm sayılar dayanak elemanın(pivot) önüne, dayanak elemandan(pivot) büyük olan tüm sayılar dayanak elemanın(pivot)  arkasına gelecek biçimde düzenle (dayanak elemana eşit olan sayılar her iki yana da geçebilir).
  Bu bölümlendirme işleminden sonra eleman sıralanmış son dizide olması gerektiği yere gelir. Algoritmanın bu aşamasına bölümlendirme aşaması denir.
  Dayanak elemanın sol ve sağ yanında olmak üzere oluşan iki ayrı küçük sayı dizisi, hızlı sıralama algoritması bu küçük parçalar üzerinde yeniden özyineli olarak çağrılarak sıralanır.

Algoritmanın karmaşıklığı
Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, {O}(nlog(n)) karmaşıklığıyla, en kötü durumda ise {O}(n^2) karmaşıklığıyla sıralar.

Hızlı sıralama algoritması java kodları

 public static void hizliSiralama(int dizi[], int sol, int sag) {
  int indis = parca(dizi, sol, sag);
  if (sol < indis - 1) {
   hizliSiralama(dizi, sol, indis - 1);
  }
  if (indis < sag) {
   hizliSiralama(dizi, indis, sag);
  }
 }

 public static int parca(int dizi[], int sol, int sag) {
  int i = sol, j = sag;
  int gecici;
  int dayanakEleman = dizi[(sol + sag) / 2];

  while (i <= j) {
   
   //soldan başlayarak dayanak elemanı(pivot)tan küçük elemanı bul
   while (dizi[i] < dayanakEleman) {
    i++;
   }
   //sağdan başlayarak dayanak elemanı(pivot)tan büyük elemanı bul
   while (dizi[j] > dayanakEleman) {
    j--;
   }
   //bulunan elamanların yerlerini değiştir
   if (i <= j) {
    gecici = dizi[i];
    dizi[i] = dizi[j];
    dizi[j] = gecici;
    i++;
    j--;
   }
  };

  return i;
 }

Kodlara ulaşmak için github adresine gidin