Answer to Question #224204 in Algorithms for Reyad

Question

Give recurrence for quick sort algorithm runtime when it sorts n-randomly sorted

integers. Derive the closed form solution using sum-method.

Answer 1

The concept of Quick short algorithm is based on the divide and conquer. In which it divides the array into the smaller parts and then it shorts the array elements.

• Select the highest indexed pivoted value.
• We have to define two variable, one is for the left and other is for the right but excluding pivot.
• The left points to the low index.
• Right points to high.
• The 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.

The pseudo-code is given below:

function partFunc(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