Answer to Question #224162 in Algorithms for Begum

Question

1. Give recurrence for quick sort algorithm runtime when it sorts n-randomly sorted integers. Derive the closed form solution using sum-method.

Answer 1

A quick short algorithm is based on the divide and conquer method. It divides the array in smaller parts and then shorts the array elements.

• choose the highest indexed value has pivot.
• Take two variables to point left and right of the list excluding pivot.
• Left points to the low index.
• Right points to high.
• While value at left is less than pivot move right.
• While value at right is greater than pivot move left.
• If step 5 and step 6 does not match swap left and right.
• If left > right, the point where they met is new pivot.

Pseudo code:

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1
   while True do
      while A[++leftPointer] < pivot do
      end while
      while rightPointer > 0 && A[--rightPointer] > pivot do
      end while
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
   end while 
	   swap leftPointer,right
   return leftPointer
end function