The Gateway to Computer Science Excellence

+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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,382 answers

198,530 comments

105,323 users