{ Verschiedene Sortieralgorithmen als Pascal-Prozeduren }

{ Gemeinsamer Vorspann: }

PROGRAM Sortieren;

CONST
   n = 8;                { Laenge der zu sortierenden Felder }

TYPE
   elemtype = integer;      { der Einfachheit halber }
   Feld = ARRAY[1..n] of elemtype;

CONST
   B : Feld = (4,2,8,7,2,0,10,3);  { unsortiertes Feld, fuer Tests }

VAR
   A : Feld;
   
PROCEDURE exchange_elems (VAR A   : Feld;
                              i,j : integer);
VAR
   temp : elemtype;
BEGIN
   temp := A[i];
   A[i] := A[j];
   A[j] := temp
END; { exchange_elems }


{-------------------------------------------------------------}
{ Sortieren durch direktes Einfuegen: "insertion sort" }
{-------------------------------------------------------------}

PROCEDURE insert_into_seq (        
                   VAR A   : Feld;
                       pos : integer;
                       key : elemtype  );
VAR
   i : integer;
BEGIN
   i := pos - 1;
   WHILE (i > 0) AND (A[i] > key) DO
   BEGIN
      A[i+1] := A[i];
      i      := i - 1
   END;
   A[i+1] := key
END; { insert_into_seq }


PROCEDURE insertion_sort (VAR A : Feld);
VAR
   j   : integer;
   key : elemtype;
BEGIN
   FOR j := 2 TO n DO
   BEGIN
      key := A[j];
      insert_into_seq(A,j,key)
   END
END; { insertion_sort }


{-------------------------------------------------------------}
{ Sortieren durch direktes Austauschen: "bubble_sort" }
{-------------------------------------------------------------}

PROCEDURE bubble_sort (VAR A : Feld);
VAR
   i,j : integer;
BEGIN
   FOR i := n DOWNTO 1 DO
      FOR j := 2 TO i DO
         IF A[j-1] > A[j]
            THEN exchange_elems(A,j-1,j)
END; { bubble_sort }


{-------------------------------------------------------------}
{ Sortieren durch Zerlegen:  "quicksort"                      }
{ zu Beginn wird aufgerufen: quicksort(A,1,n)                 }
{-------------------------------------------------------------}

FUNCTION partition (VAR A           : Feld;
                        left, right : integer) : integer;
VAR 
   i,j : integer;
   key : elemtype;
BEGIN
   key := A[left];
   i := left - 1;
   j := right + 1;
   WHILE (i < j) DO
   BEGIN
      REPEAT j := j - 1 UNTIL A[j] <= key;
      REPEAT i := i + 1 UNTIL A[i] >= key;
      IF (i < j) THEN
         exchange_elems(A,i,j)
   END;
   partition := j
END; { partition }


PROCEDURE quicksort (VAR A           : Feld;
                         left, right : integer);
VAR
   q   : integer;
BEGIN
   IF (left < right) THEN
   BEGIN
      q := partition(A,left,right);
      quicksort(A,left,q);
      quicksort(A,q+1,right)
   END
END; { quicksort }

{-------------------------------------------------------------}

{ Test-Programm }

PROCEDURE printfeld(VAR A: Feld);
VAR
  i : integer;
BEGIN
   writeln;
   FOR i := 1 TO n do
   BEGIN
      write(A[i]);
      write(' ');
   END;
   writeln;
END; { printfeld }

   
BEGIN

   A := B;
   insertion_sort(A);
   printfeld(A);

   A := B;
   bubble_sort(A);
   printfeld(A);

   A := B;
   quicksort(A,1,n);
   printfeld(A);

END.