QUICKSORT

Question

Could anyone describe how the partitioning algorithm vary when the pivot is  varied ?

In Cormen , last element is taken as pivot . Suppose I took first element or middle element or 3 rd element as pivot then how the partitioning algorithm will change.

Answer 1

Normal  quik sort can be implemented by two ways

1) select first element as pivot element: Declare two variables i,j(assumed) initially i,j and pivot will be at same place...now in partition algorithm make a whole loop with condition J will be looking for element greater than pivot and if smaller element occur then move i one position ahead and swap elements at position i and j....and so on...

2)Fix i and pivot at last position an dj at first position and run the partion algo in the same manner as illustrated above.

Third type of quik sort algo is RANDOMIZED quik sort:

In randomized quiksort pivot is calculated randomly...or we can say that array is shuffled. At every instatnt we exchange A[p] with an element chosen at random from A[p…r]

RANDOMIZED-PARTITION(A, p, r)

  i ← RANDOM(p, r)

  exchange A[p] ↔ A[i]

  return PARTITION(A, p, r)

Pivot element is likely to be any of r-p+1 

RANDOMIZED-QUICKSORT(A, p, r)

  if p < r

  then q ← RANDOMIZED-PARTITION(A, p, r)

  RANDOMIZED-QUICKSORT(A, p, q)

  RANDOMIZED-QUICKSORT(A, q + 1, r)

This is how randomized quik sort partition algorithm work.