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.