Subversion Repositories Kolibri OS

(*

   adapted to Oberon-07 by 0CodErr, KolibriOS team

                                                   *)

(* ********* Zonnon online collection ***********

 * Sorting: Heap Sort (Chapter 2, Example 2.8)

 *

 * This example is a part of Prof. Nikalus Wirth's book

 * www.zonnon.ethz.ch/usergroup

 * (c) ETH Zurich

 *)

MODULE HeapSort;

IMPORT In, Out, Console;

CONST

    MAX_SIZE = 20;

TYPE

    DefaultArray = ARRAY MAX_SIZE OF INTEGER;

VAR

    MyArray: DefaultArray;

 (***** Implementation *****)

PROCEDURE sift(VAR a: DefaultArray; L,R:INTEGER);

VAR

    i, j, x: INTEGER;

BEGIN

    i := L; j:= 2 * L; x:= a[L];

    IF (j < R) & (a[j] < a[j + 1]) THEN j := j + 1 END;

    WHILE (j <= R) & (x < a[j]) DO

        a[i] := a[j]; i := j; j := 2 * j;

        IF (j < R) & (a[j] < a[j + 1]) THEN j := j + 1 END

    END;

    a[i] := x

END sift;

PROCEDURE HeapSort(VAR a: DefaultArray; n: INTEGER);

VAR

    L, R, x: INTEGER;

BEGIN

    L := (n DIV 2); R := n - 1;

    WHILE L > 0 DO L := L - 1; sift(a, L, R) END;

    WHILE R > 0 DO

        x := a[0]; a[0] := a[R]; a[R]:= x;

        R := R - 1; sift(a, L, R)

    END

END HeapSort;

(***** Example support *****)

PROCEDURE FillTheArray;

VAR

    i: INTEGER;

BEGIN

    FOR i := 0 TO MAX_SIZE - 1 DO

        MyArray[i] := ABS(10 - i)

    END

END FillTheArray;

PROCEDURE PrintTheArray;

VAR

    i: INTEGER;

BEGIN

    Out.String("Array:"); Out.Ln;

    FOR i := 0 TO MAX_SIZE - 1 DO

        Out.Int(MyArray[i], 2); Out.String(", ")

    END;

    Out.Ln

END PrintTheArray;

PROCEDURE Execute;

BEGIN

    HeapSort(MyArray, MAX_SIZE)

END Execute;

BEGIN

    Console.open;

    Out.String("Example 2.8 (Heap sort)"); Out.Ln;

    FillTheArray;

    PrintTheArray;

    Execute;

    PrintTheArray;

    Out.String("Press Enter to continue"); In.Ln;

    Console.exit(TRUE)

END HeapSort.