Sunday, June 15, 2008

Quick Sort

Procedure QuickSort (Q, p, r)
The above Procedure sorts the given list of elements recursively. It makes a recursive call to QuickSort. For partitioning the list (array) it makes a call to Partition Procedure.
Step 1 checking
if (p <>
calling procedure partition.
set q ¬ call to Partition (Q, p, r)
first sublist.
call to QuickSort (Q, p, q)
second sublist
call to QuickSort (Q, q + 1, r)
Function Partition (Q, p, r)
The above Function arranges the sub array Q [p---r] in place.
Step 1 Initialization
set x ¬ Q[p]
set i ¬ p
set j ¬ r + 1
Step 2 Checking
while (i <>
while (Q [i] < = x)
set i ¬ i + 1
while (Q [j] > x)
set j ¬ j – 1
if (i <>
set Q [i] « Q [j]
return j.

No comments: