Veri Yapısı ve Algoritmalar - Hızlı Sıralama

Hızlı sıralama, oldukça verimli bir sıralama algoritmasıdır ve veri dizisinin daha küçük dizilere bölünmesine dayanır. Büyük bir dizi, hangisinin bölümün yapıldığına bağlı olarak, biri belirtilen değerden daha küçük değerleri tutan iki diziye, örneğin pivot'a bölünür ve başka bir dizi, pivot değerinden daha büyük değerleri tutar.

Hızlı sıralama bir diziyi bölümler ve ardından ortaya çıkan iki alt diziyi sıralamak için kendini yinelemeli olarak iki kez çağırır. Ortalama ve en kötü durum karmaşıklığı sırasıyla O (n ² ) olduğundan, bu algoritma büyük boyutlu veri kümeleri için oldukça etkilidir .

Hızlı Sıralamada Bölme

Aşağıdaki animasyonlu gösterim, bir dizideki pivot değerinin nasıl bulunacağını açıklar.

Pivot değeri, listeyi iki bölüme ayırır. Ve yinelemeli olarak, tüm listeler yalnızca bir öğe içerene kadar her alt listenin pivotunu buluruz.

Hızlı Sıralama Pivot Algoritması

Hızlı sıralamayla bölümleme anlayışımıza dayanarak, şimdi bunun için aşağıdaki gibi bir algoritma yazmaya çalışacağız.

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

Hızlı Sıralama Pivot Pseudocode

Yukarıdaki algoritma için sözde kod şu şekilde türetilebilir:

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
		
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
		
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
		
   end while 
	
   swap leftPointer,right
   return leftPointer
	
end function

Hızlı Sıralama Algoritması

Pivot algoritmasını yinelemeli olarak kullanarak, daha küçük olası bölümler elde ederiz. Her bölüm daha sonra hızlı sıralama için işlenir. Hızlı sıralama için yinelemeli algoritmayı aşağıdaki gibi tanımlıyoruz -

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

Hızlı Sıralama Sözde Kodu

Daha fazlasını öğrenmek için, hızlı sıralama algoritması için sözde koduna bakalım -

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
   
end procedure

C programlama dilinde hızlı sıralama uygulaması hakkında bilgi edinmek için lütfen buraya tıklayın .