program Sort1Example; {**************************************** * * * Example of Wirth's insertion sort * * * * Adapted from: "Algorithms + Data * * Structures = Programs", * * * * by Niklaus Wirth * * * * * * Bill Heidebrecht, TRW, 21 Jun 79 * * * ****************************************} const max = 100; nl = chr(10); 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 sort (var a: itemarray; n: index); { straight insertion sort algorithm } var i, j: index; x: item; begin { sort } for i := 2 to n do begin x := a[i] { sentinel item }; a[0] := x; j := i - 1; while x . key < a[j] . key do begin a[j+1] := a[j] { insert }; j := j - 1 end; a[j+1] := x end end { sort }; 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; { write items to output medium } var i: integer; begin write(outfile, ' key data', nl); for i := 1 to numberofitems do write(outfile, items[i] . key:5, items[i] . data:5, nl) end { outputdata }; begin { Sort1Example } rewrite (outfile, "SORT.LST", 2); inputdata; outputdata; sort (items, numberofitems); outputdata end.