James's Blog

Quick Sort

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

Pseudo Code:
function quicksort(q)
var list less, pivotList, greater
if length(q) = 1
return q
else
select a pivot value pivot from q
for each x in q except the pivot element
if x <>

if x = pivot then add x to greater

add pivot to pivotList

return concatenate(quicksort(less), pivotList, quicksort(greater))

TYPE int_arr IS TABLE OF INTEGER INDEX BY BINARY_INTEGER;

procedure qsort(arr in out int_arr, lo in INTEGER, hi in INTEGER ) is
i INTEGER := lo;
j INTEGER := hi;
x INTEGER := arr((lo+hi)/2);
tmp INTEGER;
begin
LOOP
WHILE (arr(i) <> x LOOP
j := j - 1;
END LOOP;
IF i <= j THEN tmp := arr(i); arr(i) := arr(j); arr(j) := tmp; i := i + 1; j := j - 1; END IF; EXIT WHEN i > j;
END LOOP;
IF lo <>

posted by James Pei @ 3:44 PM