/    /  Data Structures-Quick Sort

Quick Sort

 

Quicksort is a sorting algorithm that is based on partitioning the array into smaller arrays. A larger array is partitioned into two smaller arrays, one of which holds a smaller value than the other. 

Quicksort calls itself recursively twice creating subarrays. The array is divided into two sections by the pivot value. 

 

The Algorithm:

Quick Sort Pivot Pseudocode :

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

 

Quick Sort Pseudocode:

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

 

Reference

Quick Sort