Here are a number of variations. I am personally fond of the Heap Sort,
it's not the fastest but it is never the slowest.
/* REXX */
HSORTA: Procedure Expose A.
/* REXX function
Invoke as: HSORTA(occurs)
Heapsort by J. W. J. Williams is a in place sorting
algorithm whose worst-case running time is O(N*lgN) on
an input vector.
Given an vector A. of n elements the result of sorting
the vector in place is to arrange elements of A. so that
A.1<=A.2<=...<=A.n
------------------------------------------------------- */
Parse ARG occurs;
Do i = occurs % 2 To 1 By -1;
x = SIFT(i,occurs);
End;
Do i = occurs To 2 By -1;
Parse VALUE A.1 A.i With A.i A.1; /*swap places*/
x = SIFT(1,i-1);
End;
Return 0;
SIFT: Procedure Expose A.
Parse ARG lpt,rpt;
i = lpt;
W = A.i;
j = 2 * i;
jp1 = j + 1;
If j < rpt Then;
If A.j < A.jp1 Then;
j = jp1;
Do While j <= rpt;
If W >= A.j Then;
Leave;
A.i = A.j;
i = j;
j = 2 * i;
jp1 = j + 1;
If j < rpt Then;
If A.j < A.jp1 Then;
j = jp1;
End;
A.i = W;
Return 0;
/* REXX */
QSORTA: Procedure Expose A.
/* REXX function
Invoke as: QSORTA(occurs)
Quicksort by C. A. R. Hoare is a in place sorting
algorithm whose worst-case running time is O(N**2);
its expected running time is O(N*lgN) on an input
vector. Sophisticated iterative version.
Given an vector A. of n elements the result of sorting
the vector in place is to arrange elements of A. so that
A.1<=A.2<=...<=A.n
------------------------------------------------------- */
Parse ARG occurs;
s = 1;
StackL.1 = 1;
StackR.1 = occurs;
Do Until S = 0;
lpt = StackL.s;
rpt = StackR.s;
s = s - 1;
Do Until lpt >= rpt;
i = lpt;
j = rpt;
p = (lpt + rpt) % 2;
If A.lpt > A.p Then;
Parse VALUE A.lpt A.p With A.p A.lpt; /*swap*/
If A.lpt > A.rpt Then;
Parse VALUE A.lpt A.rpt With A.rpt A.lpt; /*swap*/
if A.p > A.rpt Then;
Parse VALUE A.p A.rpt With A.rpt A.p; /*swap*/
X = A.p;
Do Until i > j;
Do i = i While A.i < X; /*ascending*/
End;
Do j = j By -1 While X < A.j; /*ascending*/
End;
/* Do i = i While A.I > X; /*decending*/
End;
Do j = j BY -1 While X > A.J; /*decending*/
End; */
If i <= j Then;
Do;
Parse VALUE A.i A.j With A.j A.i; /*swap*/
i = i + 1;
j = j - 1;
End;
End;
If j - lpt < rpt - i Then;
Do;
If i < rpt Then;
Do;
s = s + 1;
StackL.s = i;
StackR.s = rpt;
End;
rpt = j;
End;
Else;
Do;
If lpt < j Then;
Do;
s = s + 1;
StackL.s = lpt;
StackR.s = j;
End;
lpt = i;
End;
End; /* until lpt >= rpt */
End; /* until s = 0 */
Return 0;
/* REXX */
QSORTD: Procedure Expose A.
/* REXX function
Invoke as: QSORTD(occurs)
Quicksort by C. A. R. Hoare is a in place sorting
algorithm whose worst-case running time is O(N**2);
its expected running time is O(N*lgN) on an input
vector. Sophisticated iterative version.
Given an vector A. of n elements the result of sorting
the vector in place is to arrange elements of A. so that
A.1<=A.2<=...<=A.n
------------------------------------------------------- */
Parse ARG occurs;
s = 1;
StackL.1 = 1;
StackR.1 = occurs;
Do Until S = 0;
lpt = StackL.s;
rpt = StackR.s;
s = s - 1;
Do Until lpt >= rpt;
i = lpt;
j = rpt;
p = (lpt + rpt) % 2;
If A.lpt > A.p Then;
Parse VALUE A.lpt A.p With A.p A.lpt; /*swap*/
If A.lpt > A.rpt Then;
Parse VALUE A.lpt A.rpt With A.rpt A.lpt; /*swap*/
if A.p > A.rpt Then;
Parse VALUE A.p A.rpt With A.rpt A.p; /*swap*/
X = A.p;
Do Until i > j;
/* Do i = i While A.i < X; /*ascending*/
End;
Do j = j By -1 While X < A.j; /*ascending*/
End; */
Do i = i While A.i > X; /*decending*/
End;
Do j = j By -1 While X > A.j; /*decending*/
End;
If i <= j Then;
Do;
Parse VALUE A.i A.j With A.j A.i; /*swap*/
i = i + 1;
j = j - 1;
End;
End;
If j - lpt < rpt - i Then;
Do;
If i < rpt Then;
Do;
s = s + 1;
StackL.s = i;
StackR.s = rpt;
End;
rpt = j;
End;
Else;
Do;
If lpt < j Then;
Do;
s = s + 1;
StackL.s = lpt;
StackR.s = j;
End;
lpt = i;
End;
End; /* until lpt >= rpt */
End; /* until s = 0 */
Return 0;
/* REXX */
QSORTA1: Procedure Expose A.
/* REXX function
Invoke as: QSORTA1(left_idx,right_idx);
Quicksort by C. A. R. Hoare is a in place sorting
algorithm whose worst-case running time is O(N**2);
its expected running time is O(N*lgN) on an input
vector. Simple iterative version.
Given an vector A. of n elements the result of sorting
the vector in place is to arrange elements of A. so that
A.1<=A.2<=...<=A.n
------------------------------------------------------- */
Parse ARG lpt,rpt;
Push lpt rpt;
Do While Queued() > 0;
Pull lpt rpt;
If lpt < rpt Then;
Do;
Q = QSPART(lpt,rpt);
Push lpt Q;
Push Q+1 rpt;
End;
End;
Return 0;
QSPART: Procedure Expose A.
Parse ARG lpt,rpt;
X = A.lpt;
i = lpt - 1;
j = rpt + 1;
Do Forever;
Do Until A.j <= X;
j = j - 1;
End;
Do Until A.i >= X;
i = i + 1;
End;
If i < j Then;
Parse VALUE A.i A.j With A.j A.i; /*swap*/
Else;
Return j;
End;
/* REXX */
SSORTA: Procedure Expose A.
/* REXX function
Invoke as: SSORTA(occurs)
Shell sort by D. L. Shell is a in place sorting
algorithm whose worst-case running time is O(N**(3/2));
its expected running time is O(N**1.25) on an input
vector.
We first sort all elements that are at distance H.1
from each other, then re-sort the vector using increment
H.2, finally we do an ordinary insertion sort with
increment 1. i.e. H=...,1093,364,121,40,13,4,1
Generated by the formula H=3*H+1 with the initial
value H=1.
Given an vector A. of n elements the result of sorting
the vector in place is to arrange elements of A. so that
A.1<=A.2<=...<=A.n
------------------------------------------------------- */
Parse ARG occurs;
h = 1;
Do Until h > occurs;
h = 3 * h + 1;
End;
Do Until h = 1;
h = h % 3;
Do i=h+1 To occurs;
V = A.i;
j = i;
jmh = j - h;
Do While A.jmh > V;
A.j = A.jmh;
j = j - h;
If j <= h Then;
Leave;
jmh = j - h;
End;
A.j = V;
End;
End;
Return 0;
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to [email protected] with the message: INFO IBM-MAIN
