Of Sorts, On Sorts, Sort of

When programming a computer to handle large amounts of data, it is helpful to be able to put that data into some orderly form and then be able to retrieve it quickly. That process is called sorting and searching and if you’re like me, the whole process has been something of a mystery to you. How do you get a computer to put a data set, be it numeric or alphbetic, into order and how should you tell the computer to go look for it?

Sorting is the group of methods used to put that information into some logical order. I really don’t know how many different types of sorting routines there are available, but there are a bunch. About the fastest sort I have come across outside of machine code routines is the Shell-Metzner sort. It works by looking at pairs of data and performing a swap when necessary. It finds the pairs to look at by logarithmic calculations and so I won’t try to explain the method (especially because I can’t — you’ll just have to take my word for it; it is fast). I will reproduce the code though.

1470 REM * * * SORT * * *
1500 LET A = INT (LN N/LN 2):  LET F = 2^A-1
1510 LET F = INT (F/2):  IF F = 0 THEN RETURN
1520 LET D =N-F: LET B =1
    ( HERE N IS THE DIMENSION OF THE ARRAY A$  AS
       THIS VERSION IS FOR AN ALPHABETICAL SORT)
1530 LET A = B
1540 LET E = A + F: IF A$(A)<A$(E) THEN GOTO 1570
1550 LET B = B + 1: IF B>D THEN GOTO 1510
1560 GOTO 1530
1570 LET T$ = A$(A): LET A$(A) = A$(E)
1575 LET A$(E) = T$
    ( T$ IS A TEMPORARY STRING USED TO PERFORM THE SWAP)
1580 LET A = A - F: IF A<1 THEN GOTO 1550
1590 GOTO 1540

To test this module, enter as direct commands:

DIM A$(5)
LET A$(1)="B"
LET A$(2)="E"
LET A$(3)="A"
LET A$(4)="D"
LET A$(5)="C"
LET N=5:GOTO 1470

The way the module stands, the letters should be sorted in reverse order. To get them sorted in the correct order use “>” instead of “<” in line 1540. This module can be used with numeric data by using a numeric array with “N” items.

This sort is very close to the famous bubble sort in the way it operates except that the Shell-Metzner sort is faster. The Bubble sort is based on a swap in the same manner except the swaps are done sequentially instead of logaritmically.

To use a Bubble sort you would have an array dimensioned with N items and then use a loop to compare each item with the next one, swapping when necessary.

FOR I = 1 TO N-1
FOR J = 1 TO N-1
IF A$(I)>A$(I+1) THEN GOTO 2ND LINE DOWN
NEXT J
LET T$=A$(I)
LET A$(I)=A$(I+1)
LET A$(I+1)=A$(I)
NEXT J:NEXT I

Again T$ is just a temporary string to store the first string in while you swap. The Bubble sort can be used with numeric data just as easily.

All the sorts available can be modified to be even faster when you are working with large strings of information. To do this you create a seperate array and fill it with the numbers of the dimension of the string array. For instance, if you have a string array with 100 large items in it you fill the numeric array with the numbers 1 to 100 in order. Then you use the numbers to refer to the location of the information in the string array. So your comparison statement becomes:

IF S$(A(I))>S$(A(I+1)) THEN GOTO SECOND LINE DOWN
NEXT I

Then sort the numeric array:

LET T=A(I)
LET A(I)=A(I+1)
LET A(I+1)=A(I)
NEXT I

What you end up doing is to sort the reference to your string array which is much faster than moving large blocks of information. This method is called tag sorting because you tag each item in your string array with a number and then move the number around. Just as there are many kinds of sorts, there are also many different kinds of searches. Any time you want to get a particular piece of information out of your database you have to locate it first. The simplest way to do that is to look at each item until you come up with a match. This is known as a sequential search. That is fine for small amounts of information to search through but if the number of items ig fairly large you can be waiting quite awhile. The number of comparisons can be found by dividing the number of items to be searched by two. That is if you have 55,000 items, your routine will have to look at 27,000 of them on the average. Not good! The code for the sequential search is:

FOR I = 1 TO THE NUMBER OF ITEMS
IF A$(I)= TARGET THEN GOTO 2ND LINE
NEXT I
LET T$=TARGET
LET I=NUMBER OF ITEMS
NEXT I

By letting I equal the number of items you are able to jump out of the loop, or you could use a goto to jump out.

There is a faster searching method called the Binary search. It starts by looking for the middle of your data set and then asking if your target is greater than, less than, or equal to t[illegible]ddle item. If the target is greater than the middle then the search throws out (figuratively — not really!!) all the items that are smaller than the target. It then finds the middle of the remainder and asks again. The same thing happens in reverse if it is less than the middle. When the target is equal to the item looked at then you are done. If you have a data set of one million items, search has to only make 20 comparisons to find the target. Convinced? Well the proof is tough but that is what I’m told. The code runs like this:

510 LET L = 1
520 LET H = N
530 LET C = 0
540 LET M = INT((H+L)/2)
550 LET C = C + 1
560 IF X = A(M) THEN GOTO (JUMP OUT OF LOOP)
570 IF L>= H THEN JUMP OUT BECAUSE THE ITEM IS
   NOT TO BE FOUND
580 IF X>A(M) THEN GOTO 610
590 LET H = M -1
600 GOTO 540
610 LET L = M + 1
620 GOTO 540

In line 520 N is the number of items to be searched.

For more information on sorts and searches I strongly recommend a look at THE ESSENTIAL GUIDE TO TIMEX/SINCLAIR HOME COMPUTERS especially the section between pages 292-318. The authors provide a very strong discussion on the subject.