--- title: "Sort Demo" id: 55168 type: "computer_media" slug: "sort-demo" url: "http://localhost/computer_media/sort-demo/" markdown_url: "http://localhost/computer_media/sort-demo.md" published_at: "2024-06-17T01:24:22+00:00" modified_at: "2026-03-30T21:45:24+00:00" author: "David Anderson" featured_image: url: "http://localhost/wp-content/uploads/2019/02/20230809-041332.jpg" excerpt: "Four classic sorting algorithms — Bubble, Selection, Shell, and Quicksort — head-to-head in one program, letting you compare their performance on randomly generated arrays." category: - name: "Archived Media" slug: "archived-media" taxonomy: "category" url: "http://localhost/category/archived-media/" post_tag: - name: "Downloadable" slug: "downloadable" taxonomy: "post_tag" url: "http://localhost/tag/downloadable/" - name: "TS 2068" slug: "ts2068" taxonomy: "post_tag" url: "http://localhost/tag/ts2068/" model: - name: "Timex/Sinclair 2068" slug: "ts-2068" taxonomy: "model" url: "http://localhost/model/ts-2068/" indiv: - name: "D. J. Currie" slug: "d-j-currie" taxonomy: "indiv" url: "http://localhost/indiv/d-j-currie/" - name: "William Tracy" slug: "william-tracy" taxonomy: "indiv" url: "http://localhost/indiv/william-tracy/" genre: - name: "Demo" slug: "demo" taxonomy: "genre" url: "http://localhost/type/demo/" - name: "Programming" slug: "programming" taxonomy: "genre" url: "http://localhost/type/programming/" media_contents: - id: 54965 title: "ISTUG Public Domain Library 5" type: "computer_media" url: "http://localhost/computer_media/istug-public-domain-library-5/" media_type: "Program" programmers: - name: "William Tracy" slug: "william-tracy" taxonomy: "indiv" url: "http://localhost/indiv/william-tracy/" - name: "D. J. Currie" slug: "d-j-currie" taxonomy: "indiv" url: "http://localhost/indiv/d-j-currie/" mediadate: "1983" images: - url: "http://localhost/wp-content/uploads/2024/06/SCR-20240616-snqq.png" - url: "http://localhost/wp-content/uploads/2024/06/SCR-20240616-snpe.png" article_media: - id: 24155 title: "An Assortment of Sorts" type: "article" url: "http://localhost/article/an-assortment-of-sorts/" media_type_tags: "Demo, Programming" --- # Sort Demo This program demonstrates and compares four classic sorting algorithms — Bubble Sort, Float Sort (selection sort variant), Shell Sort, and Quicksort — operating on a user-defined array of random integers. The array is populated with random numbers in the range 0–98 using INT(RND*99), then the user selects a sorting method by number. The Quicksort implementation uses an explicit stack stored in a two-dimensional array S(NUM,2) to manage recursion iteratively, avoiding GOSUB nesting limits. After sorting, the full array is displayed and the user can choose to run again. The program is adapted from Sync magazine, November 1983. *** ## Program Analysis ### Program Structure The program is organized into a main control loop and four self-contained sorting routines, all sharing a single array `U(NUM)`. The flow is: 1. Lines 8000–8090: Initialization, array dimensioning, random number fill (via `GO SUB 9060`), and menu display (via `GO SUB 9100`). 2. Lines 8100–8170: Method selection input loop; invalid input clears and re-displays the menu. 3. Lines 8180–8290: Bubble Sort. 4. Lines 8310–8460: Float Sort (a selection sort variant). 5. Lines 8470–8650: Shell Sort. 6. Lines 8670–8940: Quicksort with iterative stack. 7. Lines 8950–9040: Results display and repeat prompt. 8. Lines 9060–9090: Subroutine — fills array with random numbers. 9. Lines 9100–9110: Subroutine — prints sorting method menu. ### Sorting Algorithms | Method | Lines | Algorithm | Comment in code | | --- | --- | --- | --- | | Bubble Sort | 8180–8290 | Standard nested-loop bubble sort | “VERY GOOD” | | Float Sort | 8310–8460 | Selection sort (finds maximum, swaps to end, reduces range) | (none) | | Shell Sort | 8470–8650 | Shell’s diminishing-increment sort | “BEST” | | Quick Sort | 8670–8940 | Iterative quicksort with explicit stack | “FASTEST” | ### Bubble Sort Implementation The Bubble Sort (lines 8190–8270) is a textbook two-loop implementation. The outer loop variable `Q` runs from 1 to `NUM-1` and the inner loop `R` runs from 1 to `NUM-Q`, correctly shrinking the unsorted portion each pass. Temporary variables `H` and `I` hold the pair being compared, and swapping is done by direct assignment. ### Float Sort Implementation The Float Sort (lines 8320–8440) is a descending selection sort. It scans from index 1 to `NUM` to find the largest element, then swaps it with the element at position `NUM`, then decrements `NUM` and repeats. This destructively modifies `NUM`, which is significant — after Float Sort completes, `NUM` equals 1, not the original array size. The original size is preserved in variable `A` (set at line 8080) specifically to allow correct display at line 8980. ### Shell Sort Implementation The Shell Sort (lines 8480–8630) uses a gap sequence that doubles up from 1 until it exceeds `NUM` (lines 8490–8500), then halves back (line 8510). This produces the sequence …, 4, 2, 1. The inner comparison-and-swap loop (lines 8540–8610) walks backward through the array in steps of `S` when an out-of-order pair is found, providing an insertion-style pass at each gap size. The termination condition at line 8520 checks for `S=0`, which correctly ends the sort after the gap-1 pass completes and `INT(1/2)=0`. ### Quicksort Implementation The Quicksort (lines 8680–8930) is the most technically complex routine. Because BASIC lacks recursive subroutines, the program simulates a call stack using a two-dimensional array `S(NUM,2)` allocated at line 8680, where each row stores a pending `(left, right)` subrange. The variable `P` is the stack pointer. The partitioning scheme (lines 8720–8820) uses a two-pointer approach with a direction flag `S` (confusingly reusing the same variable name as the Shell Sort gap — note these are in separate routines so there is no conflict). The flag alternates between `-1` and `1` to determine which pointer advances after a swap, implementing a variant of the Hoare partition scheme. ### Notable Techniques and Idioms - Variable `A` is assigned `NUM` at line 8080 before any sort can modify `NUM`, preserving the original array size for the display loop at line 8980. - The `FLASH 1` attribute at line 8110 provides a visual “computing” indicator during sorting. - The repeat-run check at line 9020 accepts both upper- and lower-case `Y`, a user-friendly touch uncommon in short BASIC programs of this era. - Random numbers are generated as `INT(RND*99)`, giving values 0–98 (99 values, not 0–99). - The menu subroutine at line 9100 uses a single `PRINT` statement with multiple `AT` clauses to lay out the entire menu in one call. ### Bugs and Anomalies - The Float Sort modifies `NUM` in-place (line 8420). If the user runs Float Sort and then chooses “Another Run,” `NUM` is reset at line 8000 by re-dimensioning `U(NUM)` — but only because the full restart at line 8000 re-inputs `NUM`. The preservation via `A` correctly handles display, so this is managed but fragile. - The Quicksort partition variable `S` (direction flag, line 8740) shadows the Shell Sort gap variable `S` (line 8480). This causes no runtime issue since the routines are mutually exclusive, but could cause confusion during maintenance. - The label comment at line 8180 calls Bubble Sort “VERY GOOD” while Shell Sort is labeled “BEST” and Quicksort “FASTEST” — an inconsistent ranking that is mildly misleading since Quicksort is generally considered superior to Shell Sort for most inputs. ## Source Code ``` 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 ```