{$T+} program SortExample; {**************************************** * * * Example of C.A.R. Hoare's quicksort * * * * Adapted from: "Algorithms + Data * * Structures = Programs", * * * * by Niklaus Wirth * * * * * * Bill Heidebrecht, TRW, 29 May 79 * * * ****************************************} const max = 100; type item = record key: integer; data: integer { other data fields } end; index = integer { 0 .. max } ; itemarray = array [1 .. max] of item; var items: itemarray; numberofitems: index; outfile: text; procedure quicksort (var a: itemarray; n: integer); procedure sort (left, right: index); var i, j: index; x, temp: item; begin { sort } i := left; j := right; x := a[(left + right) div 2]; repeat while a[i].key < x.key do i := i + 1; while x.key < a[j].key do j := j - 1; if i <= j then begin { exchange items } temp := a[i]; a[i] := a[j]; a[j] := temp; i := i + 1; j := j - 1 end until i > j; if left < j then sort (left, j); if i < right then sort (i, right) end { sort }; begin { quicksort } sort (1, n) end { quicksort }; procedure inputdata; { input data and store in items } var i: integer; begin { simulate reading the data for demonstration purposes: } for i := 1 to 10 do begin items[i] . key := 10 - i; items[i] . data := 2 * (items[i] . key) end; numberofitems := 10 end { inputdata }; procedure outputdata; var i: integer; begin writeln(outfile, ' key data'); for i := 1 to numberofitems do writeln(outfile, items[i] . key:5, items[i] . data:5) end { outputdata }; begin { SortExample } rewrite (outfile, "QUICK.LST", 2); inputdata; outputdata; quicksort (items, numberofitems); outputdata end.