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.