|
November 16, 2026
|
Many years ago, my dad brought a computer home, and with it, a book about GW-BASIC by B. Vanryb and R. Politis, which I used to learn how to use that programming language.
Today, for no reason at all, I remembered that this book had (what it claimed to be) an implementation of Quicksort, so I wanted to check it out. However, I don’t seem to be able to find the book online, and my physical copy (if it still exists) is a literal ocean away, so I can’t go and look for it.
So the next best option is to try and write it myself.
If I remember correctly, this program came up in the discussion of the SWAP instruction, which exchanges the contents of two variables of the same type. The first program used to illustrate the instruction was, of course, a Bubblesort implementation that maybe looked like this:
10 REM Bubblesort
20 RANDOMIZE TIMER
30 REM Number of elements
40 N% = 100
50 REM The array to sort
60 DIM ARR%(N%)
70 FOR I% = 1 TO N% : ARR%(I%) = INT(RND * 1000) : NEXT I%
80 START = TIMER
90 FOR I% = 1 TO N%
100 FOR J% = I% + 1 TO N%
110 IF ARR%(I%) > ARR%(J%) THEN SWAP ARR%(I%), ARR%(J%)
120 NEXT J%
130 NEXT I%
140 PRINT "Elapsed:", TIMER - START
150 FOR I% = 2 TO N%
160 IF ARR%(I% - 1) > ARR%(I%) THEN PRINT "Error in index"; I% : STOP
170 NEXT I%
180 END
Now I could type RUN in GW-BASIC and, on my computer back then, this would have taken some 36 or 37 seconds to sort a 100-element array. It’s a simple algorithm, but it executes in O(n²) time, which, as we all know, Is No Good.
(Strictly speaking, the above is not Bubblesort, but I am pretty sure that’s how it appeared in the book because… well, because its workings make more sense to me than real Bubblesort’s, and that’s the kind of thing you internalize when you are reading coding books at the age of 10.)
Quicksort runs in O(n log n) time, which is Better, but it is a recursive algorithm, and while in other programming languages we can just call the sorting function recursively and hope for the best (which usually works out), we can’t do that in GW-BASIC: it has subroutine calls, but it doesn’t have local variables, and definitely no stack for recursion.
So we need to implement our recursion manually, with a couple of arrays to use as the call stack (one array for the start indices and another for the end indices) and a stack pointer:
1010 REM Quicksort
1020 RANDOMIZE TIMER
1030 REM Number of elements
1040 N% = 100
1050 REM The array to sort
1060 DIM ARR%(N%)
1070 FOR I% = 1 TO N% : ARR%(I%) = INT(RND * 1000) : NEXT I%
1080 REM Stack pointer and start/end pointer stacks
1090 SP% = 0 : DIM SS%(N%), ES%(N%)
1100 SS%(0) = 1 : ES%(0) = N% : SP% = 1
1110 START = TIMER
1120 WHILE SP% > 0
1130 SP% = SP% - 1 : S% = SS%(SP%) : E% = ES%(SP%)
1140 P = ARR%(INT((S% + E%) / 2))
1150 I% = S% : J% = E%
1160 WHILE I% <= J%
1170 WHILE ARR%(I%) < P : I% = I% + 1 : WEND
1180 WHILE ARR%(J%) > P : J% = J% - 1 : WEND
1190 IF I% <= J% THEN SWAP ARR%(I%), ARR%(J%) : I% = I% + 1 : J% = J% - 1
1200 WEND
1210 IF S% < J% THEN SS%(SP%) = S% : ES%(SP%) = J% : SP% = SP% + 1
1220 IF I% < E% THEN SS%(SP%) = I% : ES%(SP%) = E% : SP% = SP% + 1
1230 WEND
1240 PRINT "Elapsed:", TIMER - START
1250 FOR I% = 2 TO N%
1260 IF ARR%(I% - 1) > ARR%(I%) THEN PRINT "Error in index"; I% : STOP
1270 NEXT I%
1280 END
This takes some 9 or 10 seconds, which is clearly much faster than Bubblesort, but… it’s so much more complicated! And it certainly looked longer in the book than Bubblesort (and that’s probably why I never paid that much attention to it when I was 10–12 years old), but I’m not sure it was this long.
So now I’m wondering if, perhaps, it might have been a Mergesort implementation. It has the advantage over Quicksort that it doesn’t need extra storage for a stack, and the code for merging the two subarrays is a little hard, but perhaps not that hard?
2010 REM Mergesort
2020 RANDOMIZE TIMER
2030 REM Number of elements
2040 N% = 100
2050 REM The array to sort
2060 DIM ARR%(N%)
2070 FOR I% = 1 TO N% : ARR%(I%) = INT(RND * 1000) : NEXT I%
2080 START = TIMER
2090 SZ% = 1
2100 WHILE SZ% < N%
2110 FOR S% = 1 TO N% STEP 2 * SZ%
2120 I% = S% : J% = S% + SZ% : E% = J% + SZ% - 1
2130 IF E% > N% THEN E% = N%
2140 WHILE I% < J% AND J% <= E%
2150 IF ARR%(I%) <= ARR%(J%) GOTO 2210
2160 TMP% = ARR%(J%)
2170 FOR X% = J% TO I% + 1 STEP -1
2180 ARR%(X%) = ARR%(X% - 1)
2190 NEXT X%
2200 ARR%(I%) = TMP% : J% = J% + 1
2210 I% = I% + 1
2220 WEND
2230 NEXT S%
2240 SZ% = SZ% * 2
2250 WEND
2260 PRINT "Elapsed:", TIMER - START
2270 FOR I% = 2 TO N%
2280 IF ARR%(I% - 1) > ARR%(I%) THEN PRINT "Error in index"; I% : STOP
2290 NEXT I%
2300 END
Nope! I was wrong! This one takes 24 seconds to sort a 100-element array!
It turns out that, yes, Mergesort lets us avoid the stack because we are always splitting the array into subarrays of known sizes, but then we have to merge two contiguous subarrays in place, and to do that, we need to shift a whole block of elements every time we find that one of the elements is in the wrong subarray. This makes our algorithm run in O(n²) time, which is theoretically Not Better Than Bubblesort.
So I guess, after all, that the Quicksort implementation in Vanryb and Politis’s book looked a little bit like my second program. Hopefully, I’ll remember to look for the book next time I visit my parents. Or, if someone who has a copy reads this, please let me know!
Special thanks to martypc.net for the clock-accurate IBM PC emulator I used to write and run these programs. If you want to try running them, go to martypc.net and click on “Start IBM PC 5150”. Then, type CD BASIC to go to the BASIC directory.
Here you have two options: you can type the programs yourself in BASICA (which is essentially the same thing as GW-BASIC), or you can save them to a file on your computer, upload them to the emulator, and then execute them from there.
If you want to type the programs, run BASICA and then start typing away. Any lines that start with a number are added to the program in the order of the line numbers, not in the order you type them. If you make a mistake, you don’t need to retype the whole line: just move the cursor back to where you made the mistake, fix it, and then press Return. To remove a line, type the line number by itself with no code accompanying it. To see the program, type LIST. You can see a particular line (say, line 150) with LIST 150, or a range of lines (say, lines 1050–1110) with LIST 1050-1110. To run the program, type RUN. To run the program starting at a particular line number (for example, line 1010), type RUN 1010. To exit, type SYSTEM.
If you prefer to copy the programs from your computer, type MRECV QSORT.BAS at the DOS prompt. You’ll be prompted to select the file to upload. (If you use Linux or Mac, ensure that the file has DOS newlines, not Unix newlines). When the upload finishes, run BASICA and then type LOAD "QSORT" to load your program. You can use LIST to see the program, and then RUN, RUN 1010, or RUN 2010 to execute one of the subprograms in it. When you are done, exit by typing SYSTEM.
| Previous: “To all employees” | Table of contents | |
| Other stories about “programming”. | ||