©
janosch r.kowalczyk@newsgroup
10 Programmierer, 12 Lösungen. Das trifft natürlich für alles zu. In Seminaren ist oft unverständlich,
wie Teilnehmer reagieren, wenn man Ihnen eine andere Lösung empfiehlt. Nicht alles was funktioniert ist gut.
Am Beispiel einer SORT-Routine soll einmal gezeigt werden, wie unterschiedlich (gerade was die Performance angeht) die einzelnen
Variationen sind. Beim Test mit 1000 Datensätzen lagen die schnellste und die langsamste Variante im Verhältnis 1:42.
Viel Spaß beim Ausprobieren.
/* REXX
Test Rexx-algorithms from the file
1. Bubble sort
2. Insertion sort
3. Quick sort
4. Quick sort indirect
5. Quick sort nonrecursive
6. Quick sort nonrecursive indirect
7. Shell sort
8. Shell sort Knuth
9. Shell sort Knuth indirect
Author.....: Janosch R. Kowalczyk
Compuserve: 101572,2160
Create date: 26 May 1996
*/
number = 300
Call RandomStem number
call stem_save /* save test-stem for next usage */
/*-----------------(Bubble Sort)-----------------*/
say;Say 'Test Bubble Sort.'
start = Time(r)
Call BubSort
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*--------------(Duration: 15.250000 for 300 numbers)-*/
/*-----------------(Insert Sort)-----------------*/
call stem_restore /* Restore unsorted stem for next usage */
say;Say 'Test Insert Sort.'
start = Time(r)
Call InsSort
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*-------------(Duration: 17.250000 for 300 numbers)-*/
/*-----------------(Quick Sort)------------------*/
Call stem_restore /* Restore unsorted stem for next usage */
say;Say 'Test Quick Sort.'
start = Time(r)
Call QSort
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*-------------(Duration: 1.190000 for 300 numbers)-*/
/*-----------------(Quick Sort Indirect)------------------*/
call stem_restore /* Restore unsorted stem for next usage */
say;Say 'Test Quick Sort indirect'
start = Time(r)
sort_stem = 'stem.'
Call QSorti
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*-------------(Duration: 1.340000 for 300 numbers)-*/
/*-----------------(Quick Sort nonrecursive)------------------*/
call stem_restore /* Restore unsorted stem for next usage */
say;Say 'Test Quick Sort nonrecursive.'
start = Time(r)
Call QSortn
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*-------------(Duration: 0.750000 for 300 numbers)-*/
/*-----------------(Quick Sort nonrecursive indirect)------------------*/
call stem_restore /* Restore unsorted stem for next usage */
say;Say 'Test Quick Sort nonrecursive indirect.'
start = Time(r)
sort_stem = 'stem.'
Call QSortni
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*-------------(Duration: 0.940000 for 300 numbers)-*/
/*-----------------(Shell Sort)------------------*/
call stem_restore /* Restore unsorted stem for next usage */
say;Say 'Test Shell Sort.'
start = Time(r)
Call ShlSort
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*-------------(Duration: 7.250000 for 300 numbers)-*/
/*-----------------(Shellk Sort)------------------*/
call stem_restore /* Restore unsorted stem for next usage */
say;Say 'Test Knuth Shell Sort.'
start = Time(r)
Call ShlkSort
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*-------------(Duration: 1.160000 for 300 numbers)-*/
/*-----------------(Shellki Sort)------------------*/
call stem_restore /* Restore unsorted stem for next usage */
say;say 'Test Knuth Shell Sort indirect.'
start = Time(r)
sort_stem = 'stem.'
Call ShlkiSort
endTime = Time(r)
Say 'Sort duration:' endTime
call seq_check
/*-------------(Duration: 2.810000 for 300 numbers)-*/
EXIT
/*===================(Bubble sort)===================*/
/* :-I */
/* Name.......: BubSort */
/* */
/* Function...: Bubble Sort for a stem variable */
/* Call parm..: No */
/* Returns....: nothing (NULL string) */
/* */
/* Sample call: Call BubSort */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
BubSort: Procedure Expose stem.
/*------------(Bubble Sort for the Stem)-------------*/
Do i = stem.0 To 1 By -1 Until flip_flop = 1
flip_flop = 1
Do j = 2 To i
m = j - 1
If stem.m > stem.j Then Do
xchg = stem.m
stem.m = stem.j
stem.j = xchg
flip_flop = 0
End /* If stem.m ... */
End /* Do j = 2 ... */
End /* Do i = stem.0 ... */
Return ''
/*=================(Insertion sort)==================*/
/* :-! */
/* Name.......: InsSort */
/* */
/* Function...: Insertion Sort for a stem variable */
/* Call parm..: No */
/* Returns....: nothing (NULL string) */
/* */
/* Sample call: Call InsSort */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
InsSort: Procedure Expose stem.
/*------------(Insertion Sort for Stem)--------------*/
Do x = 2 To stem.0
xchg = stem.x
Do y = x - 1 By -1 To 1 While stem.y > xchg
xchg = stem.x
stem.x = stem.y
stem.y = xchg
x = y
End /* Do y = x... */
stem.x = xchg
End /* Do x = 2 ... */
Return ''
/*====================(Quick sort)===================*/
/* :-)) */
/* Name.......: QSort */
/* */
/* Function...: Quick Sort for a stem variable */
/* Call parm..: No */
/* Returns....: Left-Right span */
/* */
/* Sample call: Call QSort */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
QSort: Procedure Expose stem.
/*--------------(Quick Sort for Stem)----------------*/
Arg left, right
If left = '' Then left = 1
If right = '' Then right = stem.0
If right > left Then Do
i = left
j = right
k = (left+right)%2
x = stem.k
Do Until i > j
Do While stem.i < x; i = i + 1; End
Do While stem.j > x; j = j - 1; End
If i <= j Then Do
xchg = stem.i
stem.i = stem.j
stem.j = xchg
i = i + 1
j = j - 1
End
End
y = QSort(left,j)
y = QSort(i,right)
End
Return right - left
/*====================(Quick sort indirect )===================*/
/* :-)) */
/* Name.......: QSorti */
/* */
/* Function...: Quick Sort for a stem variable */
/* Call parm..: No */
/* Returns....: Left-Right span */
/* */
/* Sample call: Call QSorti */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
QSorti: Procedure Expose (sort_stem) sort_stem
/*--------------(Quick Sort for Stem)----------------*/
Arg left, right
/* Strip trailing Point */
stem_name=left(sort_stem,length(sort_stem)-1)
If left = '' Then left = 1
If right = '' Then right = value(stem_name'.0')
If right > left Then Do
i = left
j = right
k = (left+right)%2
x = value(stem_name'.k')
Do Until i > j
Do While value(stem_name'.i') < x; i = i + 1; End
Do While value(stem_name'.j') > x; j = j - 1; End
If i <= j Then Do
xchg = value(stem_name'.i',value(stem_name'.j'))
dummy = value(stem_name'.j',xchg)
i = i + 1
j = j - 1
End
End
y = QSorti(left,j)
y = QSorti(i,right)
End
Return right - left
/*====================(Quick sort nonrecursive )===================*/
/* :-)) */
/* Name.......: QSortn */
/* */
/* Function...: Quick Sort for a stem variable */
/* Call parm..: No */
/* Returns....: Left-Right span */
/* */
/* Sample call: Call QSortn */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
QSortn: Procedure Expose stem.
/* Stack initialization */
s = 1; stackl.1 = 1; stackr.1 = stem.0;
Do While s <> 0
l = stackl.s; r = stackr.s; s = s - 1;
Do Until l>=r
i = l; j = r; mid = (l + r) % 2;
x = stem.mid
Do Until i > j
Do While stem.i < x
i = i + 1
End;
Do While x < stem.j
j = j - 1
End;
If i <= j then do
w = stem.i; stem.i = stem.j; stem.j = w;
i = i + 1;j = j - 1;
End;
End /* i > j */
If i < r then do
s = s + 1; stackl.s = i; stackr.s = r;
End;
r = j
End /* l >=r */
End /* s <> 0 */
Return
/*====================(Quick sort nonrecursive indirect )===================*/
/* :-)) */
/* Name.......: QSortni */
/* */
/* Function...: Quick Sort for a stem variable */
/* Call parm..: No */
/* Returns....: */
/* */
/* Sample call: Call QSortni */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
QSortni: Procedure Expose (sort_stem) sort_stem
stem_name=left(sort_stem,length(sort_stem)-1)
/* Stack initialization */
s = 1; stackl.1 = 1; stackr.1 = value(stem_name'.0')
Do While s <> 0
l = stackl.s; r = stackr.s; s = s - 1;
Do Until l>=r
i = l; j = r; mid = (l + r) % 2;
x = VALUE(stem_name'.mid')
Do Until i > j
Do While VALUE(stem_name'.i') < x
i = i + 1
End;
Do While x < VALUE(stem_name'.j')
j = j - 1
End;
If i <= j then do
xchg = VALUE(stem_name'.i', VALUE(stem_name'.j'))
dummy = VALUE(stem_name'.j', xchg)
i = i + 1;j = j - 1;
End;
End /* i > j */
If i < r then do
s = s + 1; stackl.s = i; stackr.s = r;
End;
r = j
End /* l >=r */
End /* s <> 0 */
Return
/*====================(Shell sort)===================*/
/* :-) */
/* Name.......: ShlSort */
/* */
/* Function...: Shell Sort for a stem variable */
/* Call parm..: No */
/* Returns....: nothing (NULL string) */
/* */
/* Sample call: Call ShlSort */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
ShlSort: Procedure Expose stem.
/*---------------(Shell Sort for Stem)---------------*/
parts = 3 /* adjust to your necessities ( >1 ) */
Do n = 1 To parts
incr = 2**n - 1
Do j = incr + 1 To stem.0
i = j - incr
xchg = stem.j
Do While xchg < stem.i & i > 0
m = i + incr
stem.m = stem.i
i = i - incr
End /* Do While xchg ... */
m = i + incr
stem.m = xchg
End /* Do j = incr ... */
End /* Do n = 1 ... */
Return ''
/*====================(Shellk sort)===================*/
/* :-) */
/* Name.......: ShlKSort */
/* */
/* Function...: Shell Sort for a stem variable Knuth variante */
/* Call parm..: No */
/* Returns....: nothing (NULL string) */
/* */
/* Sample call: Call ShlkSort */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
ShlkSort: Procedure Expose stem.
/* define M for passes */
M = 1
DO WHILE (9 * M + 4) < stem.0
M = M * 3 + 1
END
/* sort stem */
DO WHILE M > 0
K = stem.0 - M
DO J = 1 TO K
Q = J
DO WHILE Q > 0
L = Q + M
IF stem.Q <= stem.L THEN LEAVE
/* switch elements */
tmp = stem.Q
stem.Q = stem.L
stem.L = tmp
Q = Q - M
END
END
M = M % 3
END
RETURN
/*====================(Shellki sort)===================*/
/* :-) */
/* Name.......: ShlKiSort */
/* */
/* Function...: Shell Sort for a stem variable Knuth-variante indirect */
/* Call parm..: No */
/* Returns....: nothing (NULL string) */
/* */
/* Sample call: Call ShlkSort */
/* */
/* Notes......: The elements to sort for must be */
/* saved in the stem named so as the */
/* stem in this Procedure (in this case */
/* "STEM.") */
/* stem.0 must contain the number of */
/* elements in stem. */
/* */
/* Changes....: No */
/* */
/*===================================================*/
ShlkiSort: PROCEDURE EXPOSE (sort_stem) sort_stem
/* Strip trailing Point */
stem_name=left(sort_stem,length(sort_stem)-1)
/* define M for passes */
M = 1
DO WHILE (9 * M + 4) < value(stem_name'.0')
M = M * 3 + 1
END
/* sort stem */
DO WHILE M > 0
K = value(stem_name'.0') - M
DO J = 1 TO K
Q = J
while_leave=0
DO WHILE Q > 0
L = Q + M
IF value(stem_name'.Q') <= value(stem_name'.L') THEN LEAVE
/* switch elements */
tmp = value(stem_name'.Q',value(stem_name'.L'))
x = value(stem_name'.L',tmp)
Q = Q - M
END
END
M = M % 3
END
RETURN
/*===================(Test routines)=================*/
/* */
/* Name.......: RandomStem */
/* */
/* Function...: Fills the stem with random numbers */
/* */
/* Call parm..: Number of items (default = 10) */
/* Returns....: Nothing (NULL string) */
/* */
/* Syntax.....: Call RandomStem number */
/* */
/* Changes....: No */
/* */
/*===================================================*/
RandomStem: Procedure Expose stem.
Arg number
If Datatype(number) <> 'NUM' Then number = 10
stem.0 = number
Do i = 1 To number
stem.i = Random( )
/* Following statement can be comment out */
/*
Say stem.i
*/
End
Return ''
seq_check: Procedure Expose stem.
/* Following 3 statements can be comment out */
Do i = 1 To stem.0-1
j=i+1
if stem.i > stem.j then do
say 'sequence error: Recordnr.' i '>' j
trace ?a
end
End
return
stem_save:
do i = 1 while stem.i <> "STEM."i
save.i = stem.i
end
return
stem_restore:
do i = 1 while save.i <> "SAVE."i
stem.i = save.i
end
return
zurück zu Hilfen im Alltag