The Gateway to Computer Science Excellence
+1 vote
167 views
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.
in Algorithms by Active (1.8k points) | 167 views

1 Answer

+1 vote
Best answer

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.

by Active (1.5k points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,382 answers
198,530 comments
105,323 users