When you must order and retrieve information, you can recall data in minimal time if the data has an orderly placement. In a program to store names and telephone numbers consider how you would locate someone if the data are in random order, e.g., Jones, Smith, Allen, Zimmerman, Travis. Location of a specific name could be made by starting at the first of the list and examining each entry until the correct one is located. Such a process is known as a linear search (see SYNC, 3:6, for a machine language linear search). Linear searches are easy to conduct, but time consuming to execute when the material being searched for is longer than a few items. The usual way for humans to order and search lists is either alphabetically for names or by order of magnitude for numbers.
Comparing Sorting Types
Any system of file handling will usually include routines for sorting (arranging the data in some sequential order) and searching. In this paper, four sorts will be examined: Bubble, Float, Shell, and Quick. There are others but these were chosen because they are popular and because they represent slow, intermediate, and fast, as well as simple and complex algorithms. Let’s look at how they work and the speed at which they order data.
The routines were run with numeric and alphanumeric data and timed with a stop watch. Three runs were then averaged. The first trials involved sorting numbers under two conditions:
- “worst case” situation in which the original order was from high to low and the order to be sorted into was from low to high; and
- a random order grouping. String timing consisted of sorting strings
Listing 1 gives the program for sorting numbers, and Listing 2 for words. To use the programs, type in the listing you want. Note that the line numbers are parallel so that the other listing can be entered with minimal editing.
After you have typed in the listing, press RUN and ENTER. The program will then ask how many items are to be sorted. If words are to be sorted, the program asks for word length. The program will then generate random data.
The menu will let you choose the sort type you want. If you are going to time the sort, enter the sort type number and start the timer simultaneously with pressing ENTER. The program will then display the sorted data. You can then modify the programs to accept your own data for sorting.
Bubble Sort
The Bubble Sort is perhaps the most widely known and used sort routine and one of the easiest to follow in its operation. It is comparable in time to other sorts when dealing with 15 or fewer items not in a worst case order before sorting. The Bubble Sort, as with other sorts can order data in any direction, from low to high, or high to low. The sorts, described order from smallest to largest in value.
In a sort of N numbers (the variable NUM in the listings) the Bubble Sort works by comparing adjacent numbers. If they are not out of order, it shifts their positions. The first elements nl and n2 are compared, then n2 and n3, n3 and n4, etc., until the end of the data. When N is reached, the largest value is in the nth position. The sequence is repeated until all comparisons have been made. With a random ordering of the distribution to be sorted, there will be (N(N*2-1))/2 comparisons. With data already ordered, exchanges = O. Interestingly, in other sorts, the final pass through the data is often a Bubble Sort. The Bubble Sort offers the advantage of being simple and easy to understand. As shown it occupies 236 bytes. Its disadvantage is slowness. Table 1 shows a walk through a Bubble Sort for 8 numbers arranged in random order.
Table 1. Bubble sort number flow
Order at end of pass.
| Data | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 90 | 28* | 01* | 01 | 01 | 01 | 01 | 01 |
| 28 | 01* | 28* | 28 | 28 | 28 | 28 | 28 |
| 01 | 47* | 47 | 47 | 47 | 32* | 32 | 32 |
| 47 | 90* | 88* | 56* | 32* | 47* | 47 | 47 |
| 93 | 88* | 56* | 32* | 56* | 56 | 56 | 56 |
| 88 | 56* | 32 | 88* | 88 | 88 | 88 | 88 |
| 56 | 32* | 90* | 90 | 90 | 90 | 90 | 90 |
| 32 | 93* | 93 | 93 | 93 | 93 | 93 | 93 |
*Indicates that a position swap occurred.
Float Sort
In Float Sort, we compare the first element with each succeeding element until a larger value is found. When found, the larger element is then compared to each of the remaining elements. If no larger value is found, that element becomes the last one in the array and the value previously in last position occupies the former position of the larger element. If, after a pass is completed, the first element is the greatest, the first and last elements are swapped.
An advantage of the Float Sort is that, on the average, it is about twice as fast as the Bubble Sort. The number of comparisons is N*(N+ 1)/2. The routine occupies 281 bytes. Table 1 shows the walk through. With the numbers given, the sort was completed with 28 comparisons, and 4 exchanges in 7 passes.
Table 2. Float sort number flow
Order at end of pass.
| Data | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 90 | 90 | 56* | 56 | 32* | 01* | 01 | 01 |
| 28 | 28 | 28 | 28 | 28 | 28 | 28 | 28 |
| 01 | 01 | 01 | 01 | 01 | 32* | 32 | 32 |
| 47 | 47 | 47 | 47 | 47 | 47 | 47 | 47 |
| 93 | 32* | 32 | 32 | 56* | 56 | 56 | 56 |
| 88 | 88 | 88 | 88 | 88 | 88 | 88 | 88 |
| 56 | 56 | 90* | 90 | 90 | 90 | 90 | 90 |
| 32 | 93* | 93 | 93 | 93 | 93 | 93 | 93 |
Shell Sort
Shell Sort involves an interchanging technique in which succeeding passes through the data place the data into a more nearly sorted list. The routine starts by comparing elements at least N/2 positions apart and swapping if the first element is greater than the second. This process is then repeated with successive pairs of elements, the same distance apart, until all elements have been compared. Then the comparison distance is halved for each successive pass through the data. This routine is, on the average, almost four times faster than the Bubble Sort on 50 item sorts. It occupies 353 bytes. Table 3 shows the Shell Sort example which made 18 comparisons and 4 exchanges in 4 passes.
Table 3. Shell sort number flow
Order at end of pass.
| Data | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 90 | 32* | 32 | 01* | 01 |
| 28 | 28 | 28 | 28 | 28 |
| 01 | 01 | 01 | 32* | 32 |
| 47 | 47 | 47 | 47 | 47 |
| 93 | 93 | 93 | 56 | 56 |
| 88 | 88 | 88 | 88 | 88 |
| 56 | 56 | 56 | 93* | 90* |
| 32 | 90* | 90 | 90 | 93* |
Quick Sort
Quick Sort works on the premise that it is faster to sort two small arrays rather than one large array. This sort is reported to be among the fastest of the sorts for disordered data. When data is not disordered but in inverse or nearly sorted order, this routine can be slow. As listed, the algorithm occupies 543 bytes. It is reproduced through the kind permission of Simon & Schuster Publishers and is taken from The Essential Guide to Timex/Sinclair Home Computers by Morse, Adamson, Anrep, and Hancock.
The routine operates by dividing the data into two groups about an Index value. The Index is such that the values above it are smaller, and those below are larger. Each group is sorted in turn.
Sorting is accomplished by an upper pointer (I) and a lower pointer (J). The upper pointer starts at U(1) and the lower at U(NUM). If the value indicated by I is greater than J, the values are exchanged and I is advanced one position. If J is greater, I is moved one position down and no exchange occurs. This process continues until the pointers coincide (I=J) and this value, U(I=J), then becomes the Index. One group is set aside and the other group sorted by the above procedure until ordered. The reserved group is retrieved and sorted, and the array is ordered.
With the data shown in Table 4, the quick sort ordered the array with 4 exchanges and 13 comparisons in 6 passes.
Table 4. Quick sort number flow
Order at end of pass.
| Data | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 90-I | 32* | 32 | 32-I | 01 | 01 | |
| 28 | 28 | 28 | 28 | 28-Index | 28 | |
| 01 | 01 | 01 | 01-J | 32 | 32 | |
| 47 | 47 | 47 | 47 | 47 | 47 | |
| 93 | 93-I | 56 | 56 | 56 | 56 | |
| 88 | 88 | 88-Index | 88 | |||
| 56 | 56-J | 93 | 93 | 93-I | 90 | |
| 32-J | 90 | 90 | 90-J | 93 | ||
| I=1 | I=5 | I=J | I=1 | I=J | I=7 | Pointer |
| J=8 | J=7 | J=3 | J=8 | Positions |
Conclusions
Which sort is best? The answer depends on the number of items being sorted and their order. From Table 5, it is clear that for sorting large numbers of items, likely to be in random order, the Quick Sort is by far the fastest. If the data is almost sorted or inverse ordered, then the Quick Sort can be slower than the Bubble Sort. When dealing with 20 items or fewer, time factors are not a major consideration and the programmer considers memory requirements and/or complexity of the algorithm in sort choices. My choice for the “best” all around sort would be the Shell Sort. It is fast, easy to understand, considerate of memory, and relatively free from ordering effects.
Table 5. Sort comparison-time/number sorts
| Numbers | Strings | ||||||
|---|---|---|---|---|---|---|---|
| Size Order | 20 RND | Inv | 50 RND | 20 RND | 50 RND | 100 RND | 400 RND |
| Bubble | 6 | 40 | 34 | 7 | 43 | 176 | waiting |
| Float | 4 | 22 | 21 | 4 | 23 | 86 | 1306 |
| Shell | 3 | 9 | 11 | 4 | 15 | 62 | 720 |
| Quick | 3 | 41 | 10 | 3 | 14 | 33 | 162 |
Listing 1
10 REM "SORTS"
20 FAST
30 PRINT ,, "INPUT TOTAL NUMBERS TO SORT"
40 INPUT NUM
50 DIM U(NUM)
60 CLS
70 GOSUB 1060
80 LET A=NUM
90 GOSUB 1110
100 INPUT W$
110 REM TIME FROM THIS POINT
120 IF W$="1" THEN GOTO 180
130 IF W$="2" THEN GOTO 310
140 IF W$="3" THEN GOTO 470
150 IF W$="4" THEN GOTO 670
160 CLS
170 GOTO 90
180 REM *** BUBBLE WD SORT ***
190 FOR Q=1 TO NUM-1
200 FOR R=1 TO NUM-Q
210 LET H=U(R)
220 LET I=U(R+1)
230 IF H<=I THEN GOTO 260
240 LET U(R)=I
250 LET U(R+1)=H
260 NEXT R
270 NEXT Q
280 GOTO 950
290 REM END OF BUBBLE
300 REM
310 REM *** FLOAT WD SORT ***
320 LET Q=U(1)
330 LET K=1
340 FOR S=2 TO NUM
350 IF U(S)<Q THEN GOTO 380
360 LET Q=U(S)
370 LET K=S
380 NEXT S
390 LET Z=U(NUM)
4100 LET U(NUM)=U(K)
410 LET U(K)=Z
420 LET NUM=NUM-1
430 IF NUM>1 THEN GOTO 320
440 GOTO 950
450 REM END OF FLOAT
460 REM
470 REM *** SHELL WD SORT ***
480 LET S=1
490 LET S=S*2
500 IF S<=NUM THEN GOTO 490
510 LET S=INT (S/2)
520 IF S=0 THEN GOTO 950
530 FOR T=1 TO NUM-S
540 LET Y=T
550 LET W=Y+S
560 IF U(Y)<=U(W) THEN GOTO 620
570 LET Z=U(Y)
580 LET U(Y)=U(W)
590 LET U(W)=Z
600 LET Y=Y-S
610 IF Y>0 THEN GOTO 550
620 NEXT T
630 GOTO 510
640 REM END OF SHELL
650 REM
660 REM
670 REM *** QUICK WD SORT ***
680 DIM S(NUM,2)
690 LET P=0
700 LET L=1
710 LET R=NUM
720 LET I=L
730 LET J=R
740 LET S=-1
750 IF U(I)<=U(J) THEN GOTO 800
760 LET T=U(I)
770 LET U(I)=U(J)
780 LET U(J)=T
790 LET S=-S
800 IF S=1 THEN LET I=I+1
810 IF S=-1 THEN LET J=J-1
820 IF I<J THEN GOTO 870
840 LET P=P+1
850 LET S(P,1)=I+1
860 LET S(P,2)=R
870 LET R=I-1
880 IF L<R THEN GOTO 720
890 IF P=0 THEN GOTO 950
900 LET L=S(P,1)
910 LET R=S(P,2)
920 LET P=P-1
930 GOTO 720
940 REM END OF QUICK
950 CLS
960 PRINT "ARRAY SORTED"
960 SLOW
980 FOR X=1 TO A
990 PRINT U(X)
1000 IF X>19 THEN SCROLL
1010 NEXT X
1020 PAUSE 600
1030 CLS
1040 GOTO 30
1050 REM GENERATES RANDOM NUMBERS AND FILLS ARRAY
1060 FOR X=1 TO NUM
1070 LET U(X)=INT (RND*99)
1080 NEXT X
1090 RETURN
1100 PRINT AT 5,15;"PICK SORT";AT 7,15;"1. BUBBLE";AT 9,15;"2. FLOAT";AT 11,15;"3. SHELL";AT 13,15;"4. QUICK"
1110 RETURNListing 2
10 REM "SORTWD"
20 FAST
30 PRINT ,, "INPUT TOTAL WORDS TO SORT"
40 INPUT NUM
50 LET A=NUM
70 GOSUB 1190
70 GOSUB 1110
80 GOSUB 1000
90 GOSUB 1250
100 INPUT W$
110 REM TIME FROM THIS POINT
120 IF W$="1" THEN GOTO 180
130 IF W$="2" THEN GOTO 310
140 IF W$="3" THEN GOTO 470
150 IF W$="4" THEN GOTO 670
160 CLS
170 GOTO 90
180 REM *** BUBBLE WD SORT ***
190 FOR Q=1 TO NUM-1
200 FOR R=1 TO NUM-Q
210 LET H$=U$(R)
220 LET I$=U$(R+1)
230 IF H$<=I$ THEN GOTO 260
240 LET U$(R)=I$
250 LET U$(R+1)=H$
260 NEXT R
270 NEXT Q
280 GOTO 950
290 REM END OF BUBBLE
300 REM
310 REM *** FLOAT WD SORT ***
320 LET Q$=U$(1)
330 LET K=1
340 FOR S=2 TO NUM
350 IF U$(S)<Q$ THEN GOTO 380
360 LET Q$=U$(S)
370 LET K=S
380 NEXT S
390 LET Z$=U$(NUM)
400 LET U$(NUM)=U$(K)
410 LET U$(K)=Z$
420 LET NUM=NUM-1
430 IF NUM>1 THEN GOTO 320
440 GOTO 950
450 REM END OF FLOAT
460 REM
470 REM *** SHELL WD SORT ***
480 LET S=1
490 LET S=S*2
500 IF S<=NUM THEN GOTO 490
510 LET S=INT (S/2)
520 IF S=0 THEN GOTO 950
530 FOR T=1 TO NUM-S
540 LET Y=T
550 LET W=Y+S
560 IF U$(Y)<=U$(W) THEN GOTO 620
570 LET Z$=U$(Y)
580 LET U$(Y)=U$(W)
590 LET U$(W)=Z$
600 LET Y=Y-S
610 IF Y>0 THEN GOTO 550
620 NEXT T
630 GOTO 510
640 REM END OF SHELL
650 REM
660 REM
670 REM *** QUICK WD SORT ***
680 DIM S(NUM,2)
690 LET P=0
700 LET L=1
710 LET R=NUM
720 LET I=L
730 LET J=R
740 LET S=-1
750 IF U$(I)<=U$(J) THEN GOTO 800
760 LET T$=U$(I)
770 LET U$(I)=U$(J)
780 LET U$(J)=T$
790 LET S=-S
800 IF S=1 THEN LET I=I+1
810 IF S=-1 THEN LET J=J-1
820 IF I<J THEN GOTO 870
840 LET P=P+1
850 LET S(P,1)=I+1
860 LET S(P,2)=R
870 LET R=I-1
880 IF L<R THEN GOTO 720
890 IF P=0 THEN GOTO 950
900 LET L=S(P,1)
910 LET R=S(P,2)
920 LET P=P-1
930 GOTO 720
940 REM END OF QUICK
950 REM STOP TIME HERE
960 CLS
970 LET SW=0
980 PRINT "ARRAY SORTED"
990 PRINT
1000 SLOW
1010 FOR Z=1 TO A
1020 PRINT U$(Z)
1030 IF Z>19 THEN SCROLL
1040 NEXT Z
1050 PAUSE 600
1060 CLS
1070 FAST
1080 IF SW THEN RETURN
1090 GOTO 10
1100 REM RANDOM WORD GENERATOR
1110 FOR Z=1 TO NUM
1120 FOR X=1 TO WD
1130 LET U$(Z,X)=CHR$ INT (38+RND*26)
1140 NEXT X
1150 NEXT Z
1160 CLS
1170 LET ST=1
1180 RETURN
1190 CLS
1200 PRINT ,,"INPUT WORD LENGTH"
1210 INPUT WD
1220 DIM U$(NUM,WD)
1230 FAST
1240 RETURN
1250 PRINT AT 5,7;"SELECT SORT"
1260 PRINT AT 7,7;"1. BUBBLE";AT 9,7;"2. FLOAT";AT 11,7;"3. SHELL";AT 13,7;"4. QUICK"
1270 RETURNProducts
Downloadable Media
Image Gallery
Note: Type-in program listings on this website use ZMAKEBAS notation for graphics characters.