Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. (*
  2.    adapted to Oberon-07 by 0CodErr, KolibriOS team
  3.                                                    *)
  4. (* ********* Zonnon online collection ***********
  5.  * Sorting: Heap Sort (Chapter 2, Example 2.8)
  6.  *
  7.  * This example is a part of Prof. Nikalus Wirth's book
  8.  * www.zonnon.ethz.ch/usergroup
  9.  * (c) ETH Zurich
  10.  *)
  11.  
  12. MODULE HeapSort;
  13.  
  14. IMPORT In, Out, Console;
  15.  
  16.  
  17. CONST
  18.     MAX_SIZE = 20;
  19.  
  20.  
  21. TYPE
  22.     DefaultArray = ARRAY MAX_SIZE OF INTEGER;
  23.  
  24.  
  25. VAR
  26.     MyArray: DefaultArray;
  27.  
  28.  (***** Implementation *****)
  29.  
  30. PROCEDURE sift(VAR a: DefaultArray; L,R:INTEGER);
  31. VAR
  32.     i, j, x: INTEGER;
  33.  
  34. BEGIN
  35.     i := L; j:= 2 * L; x:= a[L];
  36.     IF (j < R) & (a[j] < a[j + 1]) THEN j := j + 1 END;
  37.     WHILE (j <= R) & (x < a[j]) DO
  38.         a[i] := a[j]; i := j; j := 2 * j;
  39.         IF (j < R) & (a[j] < a[j + 1]) THEN j := j + 1 END
  40.     END;
  41.     a[i] := x
  42. END sift;
  43.  
  44.  
  45. PROCEDURE HeapSort(VAR a: DefaultArray; n: INTEGER);
  46. VAR
  47.     L, R, x: INTEGER;
  48.  
  49. BEGIN
  50.     L := (n DIV 2); R := n - 1;
  51.     WHILE L > 0 DO L := L - 1; sift(a, L, R) END;
  52.     WHILE R > 0 DO
  53.         x := a[0]; a[0] := a[R]; a[R]:= x;
  54.         R := R - 1; sift(a, L, R)
  55.     END
  56. END HeapSort;
  57.  
  58. (***** Example support *****)
  59.  
  60. PROCEDURE FillTheArray;
  61. VAR
  62.     i: INTEGER;
  63.  
  64. BEGIN
  65.     FOR i := 0 TO MAX_SIZE - 1 DO
  66.         MyArray[i] := ABS(10 - i)
  67.     END
  68. END FillTheArray;
  69.  
  70.  
  71. PROCEDURE PrintTheArray;
  72. VAR
  73.     i: INTEGER;
  74.  
  75. BEGIN
  76.     Out.String("Array:"); Out.Ln;
  77.     FOR i := 0 TO MAX_SIZE - 1 DO
  78.         Out.Int(MyArray[i], 2); Out.String(", ")
  79.     END;
  80.     Out.Ln
  81. END PrintTheArray;
  82.  
  83.  
  84. PROCEDURE Execute;
  85. BEGIN
  86.     HeapSort(MyArray, MAX_SIZE)
  87. END Execute;
  88.  
  89.  
  90. BEGIN
  91.     Console.open;
  92.  
  93.     Out.String("Example 2.8 (Heap sort)"); Out.Ln;
  94.     FillTheArray;
  95.     PrintTheArray;
  96.     Execute;
  97.     PrintTheArray;
  98.     Out.String("Press Enter to continue"); In.Ln;
  99.  
  100.     Console.exit(TRUE)
  101. END HeapSort.