DEFINITION MODULE SortLib;

  (*------------------------------------------------------------------------*)
  (* Stellt verschiedene Sortieralgorithmen primaer fuer Felder von Gleit-  *)
  (* kommazahlen aber auch anderer Datenstrukturen zur Verfuegung.          *)
  (* Module providing several sorting algorithms mainly for arrays of       *)
  (* reals but also genereal data structures                                *)
  (*------------------------------------------------------------------------*)
  (* Implementation : Michael Riedl                                         *)
  (* Licence        : GNU Lesser General Public License (LGPL)              *)
  (*------------------------------------------------------------------------*)

  (* $Id: SortLib.def,v 1.1 2018/01/16 09:20:20 mriedl Exp $ *)

FROM Deklera IMPORT VEKTOR,MATRIX,INTVEKTOR;

PROCEDURE InvertIndex(VAR In : ARRAY OF INTEGER;
                          I0 : ARRAY OF INTEGER;
                          n  : INTEGER);

          (*----------------------------------------------------------------*)
          (* Reverts the index provided by e.g. QuickSortNR in such a way   *)
          (* that it can be directly used to print out the underlaying      *)
          (* array in ascending order                                       *)
          (*                                                                *)
          (*   FOR i:=0 TO n-1 DO WrLngReal(A[I[i]],12,4); END;             *)
          (*----------------------------------------------------------------*)

PROCEDURE QuickSortNR(VAR A : ARRAY OF LONGREAL;
                      VAR I : ARRAY OF INTEGER;
                          n : INTEGER);

          (*----------------------------------------------------------------*)
          (* Non recursive Quicksort routine which returns in I the invers  *)
          (* sort index but does NOT reorder the original vector A. More    *)
          (* precisely I[i] indicates where to place A[i] in a              *)
          (* sorted array B, B sorted in ascending order B[i] <= B[i+1]     *)
          (*                                                                *)
          (*   FOR i:=0 TO n-1 DO B[I[i]]:=A[i]; END;                       *)
          (*----------------------------------------------------------------*)

PROCEDURE QuickSortRC(VAR A : ARRAY OF LONGREAL;
                          n : INTEGER);

          (*----------------------------------------------------------------*)
          (* Recursive Quicksort routine which returns in A the sorted      *)
          (* vector A in ascending order A[0..n-1]                          *)
          (*----------------------------------------------------------------*)

PROCEDURE Find(VAR A   : ARRAY OF LONGREAL;
                   n,k : INTEGER);

          (*----------------------------------------------------------------*)
          (* Reorder A such that A[k] is k-th largest                       *)
          (*----------------------------------------------------------------*)

PROCEDURE ShakerSort(VAR A : ARRAY OF LONGREAL;
                         n : INTEGER);

          (*----------------------------------------------------------------*)
          (* Shaker Sort returns the array A in ascending order as          *)
          (* as descibed in Wirths "Algorithmen und Datenstrukturen"        *)
          (*----------------------------------------------------------------*)

PROCEDURE ShellSort(VAR A : ARRAY OF LONGREAL;
                        n : INTEGER);

          (*----------------------------------------------------------------*)
          (* ShellSort returns the array A in ascending order as            *)
          (* as descibed in Wirths "Algorithmen und Datenstrukturen"        *)
          (*----------------------------------------------------------------*)

PROCEDURE HeapSort(VAR A : ARRAY OF LONGREAL;
                       n : INTEGER);

          (*----------------------------------------------------------------*)
          (* HeapSort returns the array A in ascending order as             *)
          (* as descibed in Wirths "Algorithmen und Datenstrukturen"        *)
          (*----------------------------------------------------------------*)

PROCEDURE StraightMerge(VAR A : ARRAY OF INTEGER;
                            n : INTEGER);

          (*----------------------------------------------------------------*)
          (* StraightMerge returns the integer array A in ascending order   *)
          (* as descibed in Wirths "Algorithmen und Datenstrukturen"        *)
          (* Please not that index range of A is 0 .. 2*n-1                 *) 
          (*----------------------------------------------------------------*)

PROCEDURE MergeSortRC(VAR A : ARRAY OF LONGREAL;
                          N : INTEGER);

          (*----------------------------------------------------------------*)
          (* Recursive Version von MergeSort (aufsteigende Ordnung)         *)
          (*----------------------------------------------------------------*)

PROCEDURE MergeSortNR(VAR A   : ARRAY OF LONGREAL;
                          num : INTEGER);

          (*----------------------------------------------------------------*)
          (* Nicht recursive Version von MergeSort (aufsteigende Ordnung)   *)
          (*----------------------------------------------------------------*)

PROCEDURE MergeSort(VAR a      : VEKTOR;
                    VAR p      : INTVEKTOR;
                        low,up : INTEGER);

          (*----------------------------------------------------------------*)
          (* MergeSort delivers a permutation of indices corresponding to   *)
          (* sorting the elements of a given vector into non-decreasing     *)
          (* order.                                                         *)
          (* The meaning of the formal parameters is:                       *)
          (*   a   : array low:upp]                                         *)
          (*         entry : vector to be sorted into nondecreasing order   *)
          (*         exit  : the contents of vec1 are left invariant        *)
          (*   p   : integer array [low:upp]                                *)
          (*         exit  : the permutation of indices corresponding to    *)
          (*                 sorting the elements of a into nondecreasing   *)
          (*                 order                                          *)
          (*   upp : the upper index of the arrays a and p                  *)
          (*----------------------------------------------------------------*)

PROCEDURE VecPerm(VAR perm    : INTVEKTOR;
                      low,upp : INTEGER;
                  VAR vector  : VEKTOR);

          (*----------------------------------------------------------------*)
          (* VecPerm permutes the elements of a given vector corresponding  *)
          (* to a given permutation of indices.                             *)
          (* The meaning of the formal parameters is:                       *)
          (* perm   : integer array [low:upp]                               *)
          (*          entry: a given permutation (e.g.as produced by        *)
          (*                 mergesort) of the numbers in the array vector  *)
          (* upp    : the upper index of the arrays perm and vector         *)
          (* vector : array [low:upp]                                       *)
          (*          entry : the real vector to be permuted                *)
          (*          exit  : the permuted vector elements.                 *)
          (*----------------------------------------------------------------*)

PROCEDURE CVecPerm(VAR perm    : ARRAY OF CARDINAL;
                       low,upp : CARDINAL;
                   VAR vector  : ARRAY OF LONGCOMPLEX);

          (*----------------------------------------------------------------*)
          (* Complex Version of VecPerm                                     *)
          (*----------------------------------------------------------------*)

PROCEDURE RowPerm(VAR perm : INTVEKTOR;
                      low  : INTEGER;                  
                      upp  : INTEGER;
                      i    : INTEGER;
                  VAR mat  : MATRIX);

          (*----------------------------------------------------------------*)
          (* RowPerm permutes the elements of a given row of a matrix       *)
          (* corresponding to a given permutation of indices.               *)
          (* The meaning of the formal parameters is:                       *)
          (*   perm   : integer array perm[low:upp]                         *)
          (*            entry: a given permutation as produced by mergesort *)
          (*                   of the numbers in the array vector           *)
          (*   upp    : the upper index of the array perm                   *)
          (*   i      : the row index of the matrix elements                *)
          (*   matrix : array [i:i,low:up]                                  *)
          (*            entry : matrix [i, low : up] should contain the     *)
          (*                    elements to be permuted                     *)
          (*            exit  : matrix[i, low : up] contains the row of     *)
          (*                    permuted elements                           *)
          (*----------------------------------------------------------------*)

TYPE  VergleichsProz = PROCEDURE(CARDINAL,CARDINAL) : BOOLEAN;
      VertauschProz  = PROCEDURE(CARDINAL,CARDINAL);

PROCEDURE HeapSortGeneral(N          : CARDINAL;
                          Vergleich  : VergleichsProz;
                          Vertausche : VertauschProz);

          (*---------------------------------------------------------------*)
          (* Soriert nach dem Heapsortalgorithmus Daten, die global durch  *)
          (* die Prozeduren Vergleich und Vertausche manipuliert werden    *)
          (* k"onnen.                                                      *)
          (* Dabei vergleicht Vergleich die Reihenfolge zweier beliebiger  *)
          (* Elemente i und j in der globalen Datenstruktur und Vertausch  *)
          (* f"uhrt ein Vertauschen dieser Elemente durch.                 *)
          (*                                                               *)
          (* F"ur ein einfaches Feld von Flie3kommazahlen                  *)
          (*                                                               *)
          (*   VAR X : ARRAY [1..N] OF REAL;                               *)
          (*                                                               *)
          (* k"onnte Vergleich als                                         *)
          (*                                                               *)
          (*   PROCEDURE Kleiner(i,j : CARDINAL) : BOOLEAN;                *)
          (*                                                               *)
          (*   BEGIN                                                       *)
          (*         RETURN X[i] < X[j];                                   *)
          (*   END Kleiner;                                                *)
          (*                                                               *)
          (* und Vertausch als                                             *)
          (*                                                               *)
          (*   PROCEDURE Vertausch(i,j : CARDINAL);                        *)
          (*                                                               *)
          (*             VAR z : REAL;                                     *)
          (*   BEGIN                                                       *)
          (*         z:=X[i]; X[i]:=X[j]; X[j]:=z;                         *)
          (*   END Vertausch;                                              *)
          (*                                                               *)
          (* implementiert sein, was zu einer Sortierung der Elemente im   *)
          (* Feld X nach ihrer Gr"o3e in aufsteigender Reihenfolge f"uhren *)
          (* w"urde. Allerdings ist der Algorithmus eher f"ur komplexere   *)
          (* Datenstrukturen gedacht, da es f"ur obiges Beispiel sicher    *)
          (* effizientere Algorithmen gibt.                                *)
          (*---------------------------------------------------------------*)

END SortLib.
