Lecture 6 - slide 18 : 46

Program sortering;
uses dos, crt;

Const Max = 30000;

Type TabelInterval = 1 .. Max;
     TabelElement = Integer;
     ArrayType = array[TabelInterval] of TabelElement;

Var T: ArrayType;
    starttid, sluttid, laengde: Longint;

Procedure Initialiser(var T: ArrayType);
(* Tilskriv startværdier af tabellen T *)
var i: integer;
begin
  Randomize;
  for i := 1 to max do T[i] := Random(10000);
end; (* Initialiser *)

procedure Udskriv(var T: ArrayType; fra, til: TabelInterval);
var i: TabelInterval;
begin
  writeln;
  for i := fra to til do
  begin
    write(T[i]:5);
  end;
  writeln
end; (* udskriv *)

procedure Sorter(var T: ArrayType; n: integer);
(* Sorter de førte n elementer i T i stigende orden.
   Sorteringen foregår ved at bytte om på elementerne i T *)
var i,m: TabelInterval;

  function FindMaxIndex(var T: ArrayType;
                        fra, til: TabelInterval): TabelInterval;
  (* Find elementet med den største værdi i T[fra..til],
     og returner dets indeks *)
  (* PREBETINGELSE: 1 <= fra <= til <= max *)
  var i, MaxIndex: TabelInterval;
      MaxElement: TabelElement;
  begin
    MaxIndex := fra; MaxElement := T[fra];
    for i := fra+1 to til do
    if T[i] > MaxElement
    then begin
           MaxElement := T[i];
           MaxIndex := i
         end;
    FindMaxIndex := MaxIndex
  (* POSTBETINGELSE: For alle j: T[j].Fornavn <= T[MaxIndex].Fornavn *)
  end; (* FindMaxIndex *)

  procedure Ombyt(var T: ArrayType; i,j: TabelInterval);
  (* Ombyt element i og j i T *)
  var temp: TabelElement;
  begin
    temp := T[i];
    T[i] := T[j];
    T[j] := temp
  end; (* Ombyt *)

begin (* sorter *)
  for i := n downto 2 do
  begin
    m := FindMaxIndex(T,1,i);
    (* Invariant: T[i+1..max] er sorteret i stigende orden.
                  T[1..i] <= T[i+1..max]. *)
    Ombyt(T,i,m);
  end
(* POSTBETINGELSE: T[1] <= T[2] <= ... <= T[max] *)
end; (* Sorter *)

Function time: LongInt;
(* Returner antal hundrede-dele sekunder siden
   sidste midnat *)
var t,m,s,h: Word;
begin
  GetTime(t,m,s,h);
  time := Longint(h) +
           100 * (longint(s) +
              60 * (longint(m) +
                 60 * longint(t)));
end;

function KoeretidsKvotient(koeretid, n: LongInt): Real;
(* n er problemstørrelse. Koeretid angiver det målte tidsforbrug.
Returner en normaliseret kvotient af den teoretisk estimerede køretid
og den faktiske køretid i mikrosekunder *)
var teoretiskTid, microtid: Longint;
begin
  microtid := koeretid * 10000;
  teoretiskTid := n * n + n div 2;
  KoeretidsKvotient := teoretiskTid / microtid;
end;

begin (* hovedprogram *)
  Clrscr; laengde := 4000;
  while laengde < 30000
  do begin
       Initialiser(T);
       starttid := time;
       Sorter(T,laengde);
       sluttid := time;
       writeln(laengde,' elementer. Tidsforbrug, 100-dele sek.:',
               sluttid-starttid);
       writeln('Køretidskvotient for sortering af ', laengde,
                ' elementer: ',
                koeretidsKvotient(sluttid-starttid, laengde):9:3);
       (* Udskriv(T,1,max); *)
       writeln;
       laengde := laengde + 4000;
     end;
  writeln('SLUT'); readkey;
end.