| 1 |
{***************************************************************************** |
| 2 |
* A Pascal quicksort. |
| 3 |
*****************************************************************************} |
| 4 |
PROGRAM Sort(input, output); |
| 5 |
CONST |
| 6 |
{ Max array size. } |
| 7 |
MaxElts = 50; |
| 8 |
TYPE |
| 9 |
{ Type of the element array. } |
| 10 |
IntArrType = ARRAY [1..MaxElts] OF Integer; |
| 11 |
|
| 12 |
VAR |
| 13 |
{ Indexes, exchange temp, array size. } |
| 14 |
i, j, tmp, size: integer; |
| 15 |
|
| 16 |
{ Array of ints } |
| 17 |
arr: IntArrType; |
| 18 |
|
| 19 |
{ Read in the integers. } |
| 20 |
PROCEDURE ReadArr(VAR size: Integer; VAR a: IntArrType); |
| 21 |
BEGIN |
| 22 |
size := 1; |
| 23 |
WHILE NOT eof DO BEGIN |
| 24 |
readln(a[size]); |
| 25 |
IF NOT eof THEN |
| 26 |
size := size + 1 |
| 27 |
END |
| 28 |
END; |
| 29 |
|
| 30 |
{ Use quicksort to sort the array of integers. } |
| 31 |
PROCEDURE Quicksort(size: Integer; VAR arr: IntArrType); |
| 32 |
{ This does the actual work of the quicksort. It takes the |
| 33 |
parameters which define the range of the array to work on, |
| 34 |
and references the array as a global. } |
| 35 |
PROCEDURE QuicksortRecur(start, stop: integer); |
| 36 |
VAR |
| 37 |
m: integer; |
| 38 |
|
| 39 |
{ The location separating the high and low parts. } |
| 40 |
splitpt: integer; |
| 41 |
|
| 42 |
{ The quicksort split algorithm. Takes the range, and |
| 43 |
returns the split point. } |
| 44 |
FUNCTION Split(start, stop: integer): integer; |
| 45 |
VAR |
| 46 |
left, right: integer; { Scan pointers. } |
| 47 |
pivot: integer; { Pivot value. } |
| 48 |
|
| 49 |
{ Interchange the parameters. } |
| 50 |
PROCEDURE swap(VAR a, b: integer); |
| 51 |
VAR |
| 52 |
t: integer; |
| 53 |
BEGIN |
| 54 |
t := a; |
| 55 |
a := b; |
| 56 |
b := t |
| 57 |
END; |
| 58 |
|
| 59 |
BEGIN { Split } |
| 60 |
{ Set up the pointers for the hight and low sections, and |
| 61 |
get the pivot value. } |
| 62 |
pivot := arr[start]; |
| 63 |
left := start + 1; |
| 64 |
right := stop; |
| 65 |
|
| 66 |
{ Look for pairs out of place and swap 'em. } |
| 67 |
WHILE left <= right DO BEGIN |
| 68 |
WHILE (left <= stop) AND (arr[left] < pivot) DO |
| 69 |
left := left + 1; |
| 70 |
WHILE (right > start) AND (arr[right] >= pivot) DO |
| 71 |
right := right - 1; |
| 72 |
IF left < right THEN |
| 73 |
swap(arr[left], arr[right]); |
| 74 |
END; |
| 75 |
|
| 76 |
{ Put the pivot between the halves. } |
| 77 |
swap(arr[start], arr[right]); |
| 78 |
|
| 79 |
{ This is how you return function values in pascal. |
| 80 |
Yeccch. } |
| 81 |
Split := right |
| 82 |
END; |
| 83 |
|
| 84 |
BEGIN { QuicksortRecur } |
| 85 |
{ If there's anything to do... } |
| 86 |
IF start < stop THEN BEGIN |
| 87 |
splitpt := Split(start, stop); |
| 88 |
QuicksortRecur(start, splitpt-1); |
| 89 |
QuicksortRecur(splitpt+1, stop); |
| 90 |
END |
| 91 |
END; |
| 92 |
|
| 93 |
BEGIN { Quicksort } |
| 94 |
QuicksortRecur(1, size) |
| 95 |
END; |
| 96 |
|
| 97 |
BEGIN |
| 98 |
{ Read } |
| 99 |
ReadArr(size, arr); |
| 100 |
|
| 101 |
{ Sort the contents. } |
| 102 |
Quicksort(size, arr); |
| 103 |
|
| 104 |
{ Print. } |
| 105 |
FOR i := 1 TO size DO |
| 106 |
writeln(arr[i]) |
| 107 |
END. |
| 108 |
|
| 109 |
{ From http://sandbox.mc.edu/~bennet/cs404/doc/qsort_pas.html } |
| 110 |
|
