NOTICE: This article originally appeared in the October, '88 issue of Michigan
Atari Magazine and may be freely distributed or reprinted in non-profit User
Group publications as long as the article's author and Michigan Atari Magazine
are credited AND this notice is reprinted with the article.  All other
publications must obtain written permission from Unicorn Publications, 3487
Braeburn Circle, Ann Arbor, MI 48108, Phone: (313) 973-8825 before using this
article.

The Sport of Sorts
by Clinton Pierce (GAG)

In this installment we're going to look at one of the most fundamental
problems in computers, sorting.  Human beings, as a rule, have an amazing
sense of geometric perception.  They will sort index cards with names on them
by placing the names in relative order on the table (A is a lot farther away
from P, than M is), and doing fine adjustments as they go along.

Computers aren't human.  They must sort using absolutes.  You must tell them
what is to be sorted (records), how it is to be sorted (keys), and where it is
to go to (output).  And they can only compare (again, as a rule) two things at
a time.

The first sort is the standard Hey-I-learned-that-in-BASIC sort: the bubble
sort.  The bubble sort compares two elements in an array, and if they are in
the wrong order, swiches them around.  It is finished when either n^2
repetitions have occured, or when no more switches are made in an entire
pass.

The next sort is Shell's sort (named after a man, not the method).  A
Pseudo-BASIC program follows for an array a, N elements long: 1.M=N 2.M=
Intger part of M/2, If m=0 then the sort is done else: J=1, K=N-M 3. I=J 4.
L=I+M, If a(i)<a(l) then goto step 6, else: T=a(i), a(i)=a(l), a(l)=T, I=I-M,
if I<1 Then goto step 6 5. Goto Step 4 6. J=J+1, if J<=K then goto step 3 7.
Go To step #1.

This sort is fairly fast, and is fairly uncomplex.  However, it has its
problems.  Two identical elements will be switched (always).  Because of that,
if the list has many similar elements, find another sort.  (About line #2, a
one element array, by definition, is sorted).

Next, we have the Selection sort (which, as we will see in the future lends
itself to recursion).  Take the same array A with N elements, and set a
pointer Q equal to the number of elements.  Algorythm: If q=1 then the array
is sorted, else : Find the largest element in the subset (1..Q-1) and switch
it with the Qth element, decrease Q by one, go back and repeat it again.  This
sort is fast, but does not deal well with an already sorted list.

The Insertion sort can be done one of two ways, with one array, or two.  For
simplicity, I'll present the two-array version.  Clear the second array Z, and
set the pointers Q & X to 0. #1 Move the first element of A into Z, and
increase the pointers.  #2 Take the Xth element in A, Find out where it goes
in Z, and move everything in Z > a(x) down one element, make z(q)=a(x),
Increase X and Q. #3 Go to step 2 until q=N.  This sort is moderately fast.

Next, Quicksort, is the fastest sort I've dealt with.  A complete algorythm
will not be given until the unit on Recursion.  But here's how it works: Given
an array 1..N, arrange the array so that all values < a pivot value, are
first, and > pivot are last.  Then, the pivot is in its proper place.  It is
then done again, and again, using each smaller region until the array is
sorted.  The sort is incredibly fast.  The number of passes needed is only N
times the Base-2 log of N. (Where bubblesort would use 4096 repetitions,
quicksort uses 384).

Until next time....Hasta Luego.