--- title: "An Assortment of Sorts" type: "article" slug: "an-assortment-of-sorts" url: "http://localhost/article/an-assortment-of-sorts/" markdown_url: "http://localhost/article/an-assortment-of-sorts.md" published_at: "2020-10-27T17:18:27+00:00" modified_at: "2026-06-21T23:20:35+00:00" featured_image: url: "http://localhost/wp-content/uploads/2022/04/20230809-041332.jpg" excerpt: "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…" category: - name: "SYNC" slug: "sync" taxonomy: "category" url: "http://localhost/category/periodicals/sync/" post_tag: - name: "1984" slug: "year-1984" taxonomy: "post_tag" url: "http://localhost/tag/year-1984/" - name: "Downloadable" slug: "downloadable" taxonomy: "post_tag" url: "http://localhost/tag/downloadable/" - name: "Full Text" slug: "fulltext" taxonomy: "post_tag" url: "http://localhost/tag/fulltext/" - name: "TS 1000" slug: "ts1000" taxonomy: "post_tag" url: "http://localhost/tag/ts1000/" - name: "Type-in program" slug: "type-in-program" taxonomy: "post_tag" url: "http://localhost/tag/type-in-program/" - name: "ZX81" slug: "zx81" taxonomy: "post_tag" url: "http://localhost/tag/zx81/" model: - name: "Sinclair ZX81" slug: "zx81" taxonomy: "model" url: "http://localhost/model/zx81/" - name: "Timex/Sinclair 1000" slug: "ts-1000" taxonomy: "model" url: "http://localhost/model/ts-1000/" indiv: - name: "William Tracy" slug: "william-tracy" taxonomy: "indiv" url: "http://localhost/indiv/william-tracy/" publication: "Sync" publication_r: id: 10243 title: "SYNC" type: "periodical" url: "http://localhost/periodical/sync-magazine/" authors: "William F Tracy" authors_r: - name: "William Tracy" slug: "william-tracy" taxonomy: "indiv" url: "http://localhost/indiv/william-tracy/" volume: "4" issue: "2" issues_articles: - id: 26460 title: "SYNC v4 n2" type: "issue" url: "http://localhost/issue/sync-v4-n2/" pages: "20-25" pubdate: "March/April 1984" archive_link: false volumeissue: "v4n2" article_media: - id: 55168 title: "Sort Demo" type: "computer_media" url: "http://localhost/computer_media/sort-demo/" --- # An Assortment of Sorts 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: 1. “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 2. 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)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 I19 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 RETURN ``` ### Listing 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)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 I19 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 RETURN ``` ## Source Code: Sort Demo ``` 8000 BORDER 0: PAPER 0: CLS : INK 7 8010 REM NO. SORT 8030 INPUT "HOW MANY NUMBERS TO SORT? "; NUM 8050 DIM U(NUM) 8060 CLS 8070 GO SUB 9060 8080 LET A=NUM 8090 GO SUB 9100 8100 INPUT "Which sorting method ? ";W$ 8110 PRINT FLASH 1;AT 19,20;" COMPUTING " 8120 IF W$="1" THEN GO TO 8180 8130 IF W$="2" THEN GO TO 8310 8140 IF W$="3" THEN GO TO 8470 8150 IF W$="4" THEN GO TO 8670 8160 CLS 8170 GO TO 8090 8180 REM BUBBLE SORT -VERY GOOD 8190 FOR Q=1 TO NUM-1 8200 FOR R=1 TO NUM-Q 8210 LET H=U(R) 8220 LET I=U(R+1) 8230 IF H<=I THEN GO TO 8260 8240 LET U(R)=I 8250 LET U(R+1)=H 8260 NEXT R 8270 NEXT Q 8280 GO TO 8950 8290 REM END OF BUBBLE SORT 8300 REM 8310 REM FLOAT SORT 8320 LET Q=U(1) 8330 LET K=1 8340 FOR S=2 TO NUM 8350 IF U(S)1 THEN GO TO 8320 8440 GO TO 8950 8450 REM END OF FLOAT SORT 8460 REM 8470 REM SHELL SORT - BEST 8480 LET S=1 8490 LET S=S*2 8500 IF S<=NUM THEN GO TO 8490 8510 LET S=INT (S/2) 8520 IF S=0 THEN GO TO 8950 8530 FOR T=1 TO NUM-S 8540 LET Y=T 8550 LET W=Y+S 8560 IF U(Y)<=U(W) THEN GO TO 8620 8570 LET Z=U(Y) 8580 LET U(Y)=U(W) 8590 LET U(W)=Z 8600 LET Y=Y-S 8610 IF Y>0 THEN GO TO 8550 8620 NEXT T 8630 GO TO 8510 8640 REM END OF SHELL SORT 8650 REM 8670 REM QUICK SORT -FASTEST 8680 DIM S(NUM,2) 8690 LET P=0 8700 LET L=1 8710 LET R=NUM 8720 LET I=L 8730 LET J=R 8740 LET S=-1 8750 IF U(I)<=U(J) THEN GO TO 8800 8760 LET T=U(I) 8770 LET U(I)=U(J) 8780 LET U(J)=T 8790 LET S=-S 8800 IF S=1 THEN LET I=I+1 8810 IF S=-1 THEN LET J=J-1 8820 IF I=R THEN GO TO 8870 8840 LET P=P+1 8850 LET S(P,1)=I+1 8860 LET S(P,2)=R 8870 LET R=I-1 8880 IF L"Y" AND V$<>"y" THEN STOP 9030 CLS 9040 GO TO 8000 9050 REM *** GENERATES RANDOM NUMBERS AND FILLS ARRAY *** 9060 CLS 9063 PRINT "RANDOM NUMBERS:" 9068 FOR X=1 TO NUM 9070 LET U(X)=INT (RND*99) 9075 PRINT u(x) 9080 NEXT X 9090 RETURN 9100 PRINT AT 4,8;"SORTING METHODS";AT 5,8;"--------------";AT 7,8;"1. BUBBLE SORT";AT 9,8;"2. FLOAT SORT";AT 11,8;"3. SHELL SORT";AT 13,8;"4. QUICK SORT" 9110 RETURN 9120 REM FROM SYNC MAGAZINE NOV? 1983 ADAPTED BY D.J.CURRIE 9998 SAVE "# SORT" LINE 8000 ```