Computing Course
AlgorithmQuick Sort
            Implemented in : Turbo Pascal 6.0
            DescriptionQuick sorts 1000 items and times how long it takes.
    
Explanation



program qsort;
uses crt,dos;
const
max = 1000;
type
list = array[1..max] of integer;
var
data : list;
i : integer;
h,m,s,hun : word;
procedure quicksort(var a : list; Lo,Hi: integer);
procedure sort(l,r : integer);
var
i,j,x,y : integer;
begin
i := l; j := r; x := a[( l+r ) div 2];
repeat
while a[i] < x do i := i+1;
while x < a[j] do j := j-1;
if i < j then
begin
y := a[i]; a[i] := a[j]; a[j] := y;
i := i+1; j := j-1;
end;
until i > j;
if l < j then sort( l , j );
if i < r then sort( i , r );
end;
begin {quicksort};
sort( Lo , Hi );
end;
begin {qsort};
write('Now generating 1000 random numbers...');
randomize;
for i := 1 to max do data[i] := random(30000);
writeln;
writeln('Now sorting random numbers...');
gettime(h,m,s,hun);
writeln('Start time is : ',h,' : ',m,' : ',s,' : ',hun);
quicksort( data, 1, max );
writeln;
{for i := 1 to max do write(data[i] ); }
gettime(h,m,s,hun);
writeln('Finish time is : ',h,' : ',m,' : ',s,' : ',hun);
end.



Explanation : Quick Sort
Start at "begin {qsort}" ( last paragraph)
Generate 1000 random numbers and say so.
Get the current time and display it.
Jump to "quicksort" procedure with the variables (data - the array), (1 - the 
start position), and (max - the last position).
At quicksort data changes to the variable a, 1 to Lo and max to Hi. (so data,1, 
max ..... goto .....a, Lo, Hi )
Now jump down to begin "{quicksort}" (This is the start of the main procedure)
This calls the procedure "sort" with the variables Lo and Hi.
Which then become l and r (left and right) (Don't ask me why!!! I think it's to 
tell the different procedure's own variables appart from each other, a bit 
confusing really)
So we now have l=1 and r=1000...(the first and last positions of the array)
Now we need to keep l and r for later so we create i and j to use within the 
procedure and assign them the same values as l and r.
x takes on the value of the item in the middle of the array ie. with a list of 
7,4,6... x would be 4. ( this sets the pivot value around which the program will 
sort left and right. ie. <list of no's on L><pivot val><list of no's on R>
Ok so now we should have the hi, lo and middle values to sort. 
Now we're on the two while loops...
The first says increment i until the value contained in position i is greater 
than the value pointed at by x (the middle value).
Simerly the second lowers the value of j until the value of position j is lower 
than the value of the middle item.
If the items pointed at have not crossed the middle value... Ie both pointers i 
and j are still on the side of the array they started on then swap the values 
contained in those two positions. And move both i and j pointers one towards the 
middle.
End of the if bit.
We have to repeat the testing and swapping section until everything greater than 
the middle value is on the right of it and everything lower than the middle 
value is on the left of it. This means that if the value of the middle position 
has not got an equal amount of higher and lower numbers in the array the value 
of the middle position will change addresses in the array, but it will still be 
the pivot or middle value...
I think this needs an example...
0,1,2,3,7,4,5,6,8,9 - array a.
x = 1+10 div 2 = 5.....So the value of "the middle value" is 
7.....a[5]=7...........Hope you're getting this.
now we test l against x...(0-7 no change necessary) (1-7..no change) (2-7..no 
change) (3-7..no change) (7-7..stop) i now equils 5..( ie a[5]=7 )
and now r against x..(7-9..no change) (7-8..nochange) (7-6..stop) j now equils 
8..( ie a[8]=6 )
Swap 7 and 6 over (using a temporary value y) leaving 0,1,2,3,6,4,5,7,8,9....x 
now equils 8..
The middle value will always be 7 this pass. (ie x=8 ... a[8]=7 .. a[x]=7 )
As you can see now all higher numbers are to the right of 7 and all lower 
nimbers to the left of 7.
Here we can say 7 is in the sorted place and can be left alone now. 
We seperate the left side of the list and call the sort procedure again passing 
in the parameters to say that the array only exists between positions 1 and 7 ie 
l=1 and r=7... 
This will continue findind a middle value and putting it in the right place 
until all values have been the middle value ie lists of size one. it will go 
down the left hand side of the array splitting it like it was a binary tree. 
Once all Left hand options have been sorted the right hand options will be delt 
with.
Furthur example...
list a is 5,3,9,4,2 ... x=3 , l=1 , r=5....swap 9 and 2..
5,3,2,4,9 ... x=5 , l=1 , r=5....split off left
5,3,2,4 ... x=2 , l=1 , r=4....swap 5 and 2..
So far ... 2,3,5,4,9 ... processed -9,3
2,3,5,4... x=2 , l=1 , r=4....split off left
2... x=1 , l=1 , r=1.... split off right
So far ... 2,3,5,4,9 ... processed -9,3,2
5,4 ... x=3 , l=3 , r=4....swap 5 and 4
4,5 ... x=4 , l=3 , r=4...split off left
So far ... 2,3,4,5,9 ... processed -9,3,2,5
4 ... x=4 , l=4 , r=4....stop
So far ... 2,3,4,5,9 ... processed -9,3,2,5,4
or
positions... 1,2,3 
sort 1,2,3
Pos 2 sorted
sort 1
pos 1 sorted
sort 3 
pos 3 sorted
I think the key to this is realising that the array is split into unequil halves 
each pass around... recursivly the lefthand side is called with one set of 
parameters and then the righthand side is called with the opposing set of 
parameters.
If you need any furthur help with this don't hesitate in contacting me... I'll 
try to help.