3 Implemented in : Turbo Pascal 6.0
\r
4 DescriptionQuick sorts 1000 items and times how long it takes.
\r
15 list = array[1..max] of integer;
\r
20 procedure quicksort(var a : list; Lo,Hi: integer);
\r
21 procedure sort(l,r : integer);
\r
25 i := l; j := r; x := a[( l+r ) div 2];
\r
27 while a[i] < x do i := i+1;
\r
28 while x < a[j] do j := j-1;
\r
31 y := a[i]; a[i] := a[j]; a[j] := y;
\r
35 if l < j then sort( l , j );
\r
36 if i < r then sort( i , r );
\r
42 write('Now generating 1000 random numbers...');
\r
44 for i := 1 to max do data[i] := random(30000);
\r
46 writeln('Now sorting random numbers...');
\r
48 writeln('Start time is : ',h,' : ',m,' : ',s,' : ',hun);
\r
49 quicksort( data, 1, max );
\r
51 {for i := 1 to max do write(data[i] ); }
\r
53 writeln('Finish time is : ',h,' : ',m,' : ',s,' : ',hun);
\r
58 Explanation : Quick Sort
\r
59 Start at "begin {qsort}" ( last paragraph)
\r
60 Generate 1000 random numbers and say so.
\r
61 Get the current time and display it.
\r
62 Jump to "quicksort" procedure with the variables (data - the array), (1 - the
\r
63 start position), and (max - the last position).
\r
64 At quicksort data changes to the variable a, 1 to Lo and max to Hi. (so data,1,
\r
65 max ..... goto .....a, Lo, Hi )
\r
66 Now jump down to begin "{quicksort}" (This is the start of the main procedure)
\r
67 This calls the procedure "sort" with the variables Lo and Hi.
\r
68 Which then become l and r (left and right) (Don't ask me why!!! I think it's to
\r
69 tell the different procedure's own variables appart from each other, a bit
\r
71 So we now have l=1 and r=1000...(the first and last positions of the array)
\r
72 Now we need to keep l and r for later so we create i and j to use within the
\r
73 procedure and assign them the same values as l and r.
\r
74 x takes on the value of the item in the middle of the array ie. with a list of
\r
75 7,4,6... x would be 4. ( this sets the pivot value around which the program will
\r
76 sort left and right. ie. <list of no's on L><pivot val><list of no's on R>
\r
77 Ok so now we should have the hi, lo and middle values to sort.
\r
78 Now we're on the two while loops...
\r
79 The first says increment i until the value contained in position i is greater
\r
80 than the value pointed at by x (the middle value).
\r
81 Simerly the second lowers the value of j until the value of position j is lower
\r
82 than the value of the middle item.
\r
83 If the items pointed at have not crossed the middle value... Ie both pointers i
\r
84 and j are still on the side of the array they started on then swap the values
\r
85 contained in those two positions. And move both i and j pointers one towards the
\r
88 We have to repeat the testing and swapping section until everything greater than
\r
89 the middle value is on the right of it and everything lower than the middle
\r
90 value is on the left of it. This means that if the value of the middle position
\r
91 has not got an equal amount of higher and lower numbers in the array the value
\r
92 of the middle position will change addresses in the array, but it will still be
\r
93 the pivot or middle value...
\r
94 I think this needs an example...
\r
95 0,1,2,3,7,4,5,6,8,9 - array a.
\r
96 x = 1+10 div 2 = 5.....So the value of "the middle value" is
\r
97 7.....a[5]=7...........Hope you're getting this.
\r
98 now we test l against x...(0-7 no change necessary) (1-7..no change) (2-7..no
\r
99 change) (3-7..no change) (7-7..stop) i now equils 5..( ie a[5]=7 )
\r
100 and now r against x..(7-9..no change) (7-8..nochange) (7-6..stop) j now equils
\r
102 Swap 7 and 6 over (using a temporary value y) leaving 0,1,2,3,6,4,5,7,8,9....x
\r
104 The middle value will always be 7 this pass. (ie x=8 ... a[8]=7 .. a[x]=7 )
\r
105 As you can see now all higher numbers are to the right of 7 and all lower
\r
106 nimbers to the left of 7.
\r
107 Here we can say 7 is in the sorted place and can be left alone now.
\r
108 We seperate the left side of the list and call the sort procedure again passing
\r
109 in the parameters to say that the array only exists between positions 1 and 7 ie
\r
111 This will continue findind a middle value and putting it in the right place
\r
112 until all values have been the middle value ie lists of size one. it will go
\r
113 down the left hand side of the array splitting it like it was a binary tree.
\r
114 Once all Left hand options have been sorted the right hand options will be delt
\r
117 list a is 5,3,9,4,2 ... x=3 , l=1 , r=5....swap 9 and 2..
\r
118 5,3,2,4,9 ... x=5 , l=1 , r=5....split off left
\r
119 5,3,2,4 ... x=2 , l=1 , r=4....swap 5 and 2..
\r
120 So far ... 2,3,5,4,9 ... processed -9,3
\r
121 2,3,5,4... x=2 , l=1 , r=4....split off left
\r
122 2... x=1 , l=1 , r=1.... split off right
\r
123 So far ... 2,3,5,4,9 ... processed -9,3,2
\r
124 5,4 ... x=3 , l=3 , r=4....swap 5 and 4
\r
125 4,5 ... x=4 , l=3 , r=4...split off left
\r
126 So far ... 2,3,4,5,9 ... processed -9,3,2,5
\r
127 4 ... x=4 , l=4 , r=4....stop
\r
128 So far ... 2,3,4,5,9 ... processed -9,3,2,5,4
\r
130 positions... 1,2,3
\r
137 I think the key to this is realising that the array is split into unequil halves
\r
138 each pass around... recursivly the lefthand side is called with one set of
\r
139 parameters and then the righthand side is called with the opposing set of
\r
141 If you need any furthur help with this don't hesitate in contacting me... I'll
\r
projects / z.facultad / 75.40 / 1er-cuat / material.git / blob