another SHELL-Sortroutine
Captured from a message from Ian Collier (see EMail
Addresses) in a public Internet news group (see Internet
- Newsgroups)
"That algorithm is a weird variation on Shell sort that I've never seen before. A shell sort is a bit like a glorified bubble sort but it usually performs better, and it can be written as follows. Notice that the last pass, with d=1, is equivalent to a bubble sort; we expect the list to be mostly in order by this time so that the bubble sort finishes quicky. The earlier passes are like bubble sorts that make elements travel more quickly when they are further out of place. [A quick test on 300 lines of news articles showed that the above program performed 10428 comparisons. A bubble sort did 33374 comparisons.]"
/* ------------------------------------------------------------------ */
/* function: variation of Shell sort */
/* */
/* call: ShellSort */
/* */
/* returns: nothing */
/* */
/* notes: You must save the elements to sort in the stem "STEM." */
/* stem.0 must contain the number of elements in the stem. */
/* */
ShellSort: PROCEDURE expose stem.
d = stem.0 % 2 /* d is a distance measurement */
do while d > 0
do until finished /* start of mini-bubblesort loop */
finished = 1
do i=1 to stem.0-d
j = i+d /* we now compare and swap items i and i+d */
if stem.i >> stem.j then do /* v2.80 */
temp = stem.i
stem.i = stem.j
stem.j = temp
finished = 0
end
end i
end /* end of mini-bubblesort loop */
d = d%2
end
RETURN