6. Hızlı Sıralama (Quick sort)

QUICK SORT’UN CALISMA MANTIĞI

Quick sort da Merge sort gibi parçala ve fethet mantığıyla çalışır. Problemi kendi içerisinde küçük parçalara ayırır ve çözer.  Quick sort’da yapılan ilk işlem bir pivot seçmektir. Nedir pivot? pivotu bir dayanak noktası gibi düşünebilirisniz. Bir pivot seçilir ve bu pivottan küçük olanlar pivotun soluna, pivottan büyük olanlar sağına atılır. Bu sebepten performans açısından pivotun seçimi önemlidir.

26 , 33 , 35 , 29 , 19 , 12 , 22 şeklinde bir dizimiz olsun. Pivot genelde ya en baştaki ya da en sondaki olmakla beraber istenilen eleman seçilebilir.

  • 26 yani ilk index pivot sayımız olsun.
    26  ,  33  ,  35  ,  29  ,  19  ,  12  ,  22 
  • ilk turda pivot dışındaki baştan ve sondan ilk indexler pivot ile kıyaslanır küçük olan sola büyük olan sağa alınır.
    26 I  ,  33  ,  35  ,  29  ,  19  ,  12  ,  22   ->   26  I   22 ,  35  ,  29  ,  19  ,  12  ,  33
  • İkinci adımda indexler birer artarak tekrar kıyaslama ve gerekirse yer değiştirme yapılır.
    26 I ,  22  ,  35  ,  29  ,  19  ,  12  ,  33    ->   26  I   ,  22 ,  12 ,  29  ,  19  , 35 ,  33
  • üçüncü adımda tekrar indexler artarak son kıyaslama ve gerekirse yer değiştirme yapılır.
    26 I   ,  22 ,  12 ,  29  19  , 35 ,  33   ->      26  I ,  22 ,  12 ,  1929, 35 ,  33

Daha sonra pivotu alıp ortaya koyuyoruz. Öyle ki yukarıdaki işlemler sonucunda pivotu ortaya koyduğumuzda solundakilerin pivottan küçük sağındakilerin büyük olacağını biliyoruz.

  •   26  I ,  22 ,  12  1929, 35 ,  33    ->   19 I ,  22 ,  12  2629, 35 ,  33

Artık elimizde yukarı soldaki ilk turun son haline gelmiş bir dizi var ikinci adımda artık bu diziyi iki ufak parçaya bölüp aynı adımları iki ufak parça için gerçekleştireceğiz. Yani iki parça için tekrardan quick sort uygulayacağız.

19 , 22 , 12   ———– 26 ————   29 , 35 , 33

Sol taraf için bir quick sort , sağ taraf için bir quick sort uygulanız

Sol taraf  için ;
19 I , 22 , 12    –> 19 I , 12 , 22  –>   12 , 19 , 22

Sağ taraf için ;
 29 I , 35 , 33  –>  29 I , 33 ,35   

12 , 19 , 22 , 26 , 29 , 33 , 35

QUICK SORT’UN ALGORITMA ANALIZI

Eğer sıralı bir diziyi quick sort ile sıralamak isteseydik. Yine aynı mantıkla giderdik ancak  tüm sayılar pivottan büyük olduğu için buarda bir noktada farklılık oluşurdu. Buradaki mantık , sol pointer’ı sabit tutup her seferinde sağ taraftakini bir ilerletmek, ta ki yer değiştirilmeye müsait eleman çifti bulana kadar. Eğer aşağıdaki örnekteki gibi bulunamazsa en sonunda pointer’lar aynı sayı üzerinde (aşağıdaki örnekte 19) buluşur ve artık sağ tarafı kendi içerisinde sırala işlemine geçeriz.

12I , 19 , 22 , 26 , 29 , 33 , 35  ->  12I , 19 , 22 , 26 , 29 , 33 , 35  -> 12I , 19 , 22 , 26 , 29 , 33 , 35  -> 12I , 19 , 22 , 26 , 29 , 33 , 35 ->  12I , 19 , 22 , 26 , 29 , 33 , 35 ->  12 I , 19 , 22 , 26 , 29 , 33 , 35 -> 12I , 19 , 22 , 26 , 29 , 33 , 35

Dizi parçalama maliyeti : O(n)=n
Kaç adımda tek elemana ineceği : O(logn)
Ortalama beklenen performans : O(n) = n logn
En kötü durum : Sıralı ya da tersten sıralı dizi , bir pivot seçtik tüm elemanlar sağda, sonra alt grubu sıralarken bir pivot sonra yine bütün elemanlar sağda, N elemanlı dizide N tane pivot seçmek anlamına gelir. O(n)= n^2

Yani Quick sortta şanslıysak ve güzel pivotlar gelirse hep iki eşit parçaya bölerek gitmek isteriz( O(n)=n ). Şansızsak kötü pivotlar seçerek hiç parçalayamadan gideriz ( O(n)= n^2 ).

QUICK SORT’UN  C# ile IMPLEMENTASYONU

 

public static int Quickpartition(List<double> arr, int low, int high)
 {
       double pivot = arr[high];
       int i = (low - 1);
       for (int j = low; j < high; j++)
      {
        if (arr[j] <= pivot)
        {
            i++;
           double temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
        }
      }

      double temp2 = arr[i + 1];
      arr[i + 1] = arr[high];
      arr[high] = temp2;

     return i + 1;
 }

  public static void Quicksort(List<double> arr, int low, int high)
  {
      if (low < high)
     {
      int pi = Quickpartition(arr, low, high);

      Quicksort(arr, low, pi - 1);
      Quicksort(arr, pi + 1, high);
     }
  }