NUMAL Section 3.3.1.1.3.1
BEGIN SECTION : 3.3.1.1.3.1 (November, 1976)
AUTHORS: J.J.G. ADMIRAAL, A.C. YSSELSTEIN.
CONTRIBUTOR: J.J.G. ADMIRAAL.
INSTITUTE: UNIVERSITY OF AMSTERDAM.
RECEIVED: 761101.
BRIEF DESCRIPTION:
THIS SECTION CONTAINS THREE PROCEDURES FOR SORTING THE
ELEMENTS OF A VECTOR AND CORRESPONDINGLY PERMUTING THE
ELEMENTS OF A VECTOR OR A MATRIX ROW.
A) MERGESORT DELIVERS A PERMUTATION OF INDICES
CORRESPONDING TO SORTING THE ELEMENTS OF A GIVEN
VECTOR INTO NON-DECREASING ORDER.
B) VECPERM PERMUTES THE ELEMENTS OF A GIVEN VECTOR
CORRESPONDING TO A GIVEN PERMUTATION OF INDICES.
C) ROWPERM PERMUTES THE ELEMENTS OF A GIVEN ROW OF A
MATRIX CORRESPONDING TO A GIVEN PERMUTATION OF
INDICES.
KEYWORDS:
SORTING,
PERMUTING.
SUBSECTION: MERGESORT.
CALLING SEQUENCE:
THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
"PROCEDURE" MERGESORT(VEC1,VEC2,LOW,UPP);
"VALUE" LOW,UPP;"INTEGER" LOW,UPP;"ARRAY" VEC1;
"INTEGER""ARRAY" VEC2; "CODE" 36405;
THE MEANING OF THE FORMAL PARAMETERS IS:
VEC1 :<ARRAY IDENTIFIER>;
"ARRAY" VEC1[LOW:UPP];
ENTRY: THE VECTOR TO BE SORTED INTO
NONDECREASING ORDER;
EXIT: THE CONTENTS OF VEC1 ARE LEFT INVARIANT;
VEC2 :<ARRAY IDENTIFIER>;
"INTEGER""ARRAY" VEC2[LOW:UPP];
EXIT: THE PERMUTATION OF INDICES CORRESPONDING TO
SORTING THE ELEMENTS OF VEC1 INTO
NON-DECREASING ORDER;
LOW : <ARITHMETIC EXPRESSION>;
THE LOWER INDEX OF THE ARRAYS VEC1 AND VEC2;
UPP : <ARITHMETIC EXPRESSION>;
THE UPPER INDEX OF THE ARRAYS VEC1 AND VEC2;
PROCEDURES USED: NONE.
REQUIRED CENTRAL MEMORY: ONE LOCAL INTEGER ARRAY OF
LENGTH N,WHERE N = UPP - LOW + 1.
RUNNING TIME: AVERAGE PROPORTIONAL TO N * LN(N).
LANGUAGE: ALGOL 60.
METHOD AND PERFORMANCE: SORTING BY MERGING. ([1],[2])
EXAMPLE OF USE: THE PROCEDURE MERGESORT IS USED IN SYMEIGIMP
(SECTION 3.3.1.1.3.3).
SUBSECTION: VECPERM.
CALLING SEQUENCE:
THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
"PROCEDURE" VECPERM(PERM,LOW,UPP,VECTOR);
"VALUE" LOW,UPP; "INTEGER" LOW,UPP;
"INTEGER" "ARRAY" PERM;"ARRAY" VECTOR;
"CODE" 36404;
THE MEANING OF THE FORMAL PARAMETERS IS:
PERM :<ARRAY IDENTIFIER>;
"INTEGER" "ARRAY" PERM[LOW:UPP];
ENTRY: A GIVEN PERMUTATION (E.G.AS PRODUCED BY
MERGESORT) OF THE NUMBERS IN THE ARRAY VECTOR;
LOW :<ARITHMETIC EXPRESSION>;
THE LOWER INDEX OF THE ARRAYS PERM AND VECTOR;
UPP :<ARITHMETIC EXPRESSION>;
THE UPPER INDEX OF THE ARRAYS PERM AND VECTOR;
VECTOR :<ARRAY IDENTIFIER>;
"ARRAY" VECTOR[LOW:UPP];
ENTRY: THE REAL VECTOR TO BE PERMUTED;
EXIT: THE PERMUTED VECTOR ELEMENTS.
PROCEDURE USED: NONE.
REQUIRED CENTRAL MEMORY :
ONE LOCAL BOOLEAN ARRAY OF LENGTH N IS DECLARED.
RUNNING TIME: PROPORTIONAL TO N.
LANGUAGE: ALGOL 60.
EXAMPLE OF USE: THE PROCEDURE VECPERM IS USED IN SYMEIGIMP;
(SECTION 3.3.1.1.3.3).
SUBSECTION: ROWPERM.
CALLING SEQUENCE:
THE DECLARATION OF THE PROCEDURE IN THE CALLING PROGRAM READS:
"PROCEDURE" ROWPERM(PERM,LOW,UPP,I,MATRIX);
"VALUE" LOW,UPP,I;"INTEGER" LOW,UPP,I;
"INTEGER" "ARRAY" PERM;"ARRAY" MATRIX;
"CODE" 36403;
THE MEANING OF THE FORMAL PARAMETERS IS:
PERM :<ARRAY IDENTIFIER>;
"INTEGER" "ARRAY" PERM[LOW:UPP];
ENTRY: A GIVEN PERMUTATION (E.G. AS PRODUCED BY
MERGESORT) OF THE NUMBERS IN THE ARRAY VECTOR;
LOW :<ARITHMETIC EXPRESSION>;
THE LOWER INDEX OF THE ARRAY PERM;
UPP :<ARITHMETIC EXPRESSION>;
THE UPPER INDEX OF THE ARRAY PERM;
I :<ARITHMETIC EXPRESSION>;
THE ROW INDEX OF THE MATRIX ELEMENTS;
MATRIX :<ARRAY IDENTIFIER>:
"ARRAY" MATRIX [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;
PROCEDURES USED: NONE.
REQUIRED CENTRAL MEMORY:
ONE LOCAL BOOLEAN ARRAY OF LENGTH N IS DECLARED.
RUNNING TIME: PROPORTIONAL TO N, WHERE N = UPP - LOW + 1.
LANGUAGE: ALGOL 60.
EXAMPLE OF USE: THE PROCEDURE ROWPERM IS USED IN SYMEIGIMP.
(SECTION 3.3.1.1.3.3).
REFERENCES:
[1] D.E. KNUTH , THE ART OF COMPUTER PROGRAMMING,
VOL. 3/ SORTING AND SEARCHING,ADDISON-WESLEY 1973.
(SECTION 5.2.4 P.159-173).
[2] A.V. AHO, J.E. HOPCROFT & J.D. ULLMAN,
THE DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS,
ADDISON-WESLEY 1974.
(SECTION I.M, P65-67).
SOURCE TEXTS:
"CODE" 36405;
"CODE" 36404;
"CODE" 36403;