A Recursive Sort Routine in Classic BASIC

Sorry, this browser is not Java(tm) enabled.

It either cannot run Java(tm) applets, or the running of applets is currently disabled in your browser.

 BASIC 

 EDIT               	F1
 CAPS LOCK          	F2
 LEFT               	F5, SHIFT+LEFT
 DOWN               	F6, SHIFT+DOWN
 UP                 	F7, SHIFT+UP
 RIGHT              	F8, SHIFT+RIGHT
 GRAPHICS MODE      	F9

  Click on the Screen  and enter 'run' for another go.    
 


  Click here to continue the tour of ZX BASIC programs.

The Jasper ZX Spectrum emulator running a BASIC Sort Demonstration

ZX Spectrum Emulator by Adam Davidson and Andrew Pollard

The same technique used in the Chess problems is demostrated here in Quicksort by Sir Charles Antony Richard Hoare who, in 2000, became the second computer scientist to be knighted by the Queen.
Originally written in ALGOL to sort Russian text, this version is written in Sinclair BASIC using recursion and a divide and conquer strategy.

The Sinclair BASIC program below will sort random numbers using recursion.

HOARE'S QUICKSORT - an example of recursion in BASIC.

  10 PRINT "QUICKSORT - devised by CAR HOARE": LET max=200: GO TO 9000

1000 REM   Recursive subroutine
1010 LET s=s+1: LET lower=l(s): LET upper=r(s)
1020 LET value=a(lower): LET i=lower: LET j=upper
1030 REM   Divide
1040 IF (a(i)<=value AND i<upper) THEN LET i=i+1: GO TO 1040
1050 IF a(j)>value THEN LET j=j-1: GO TO 1050
1060 IF i<j THEN LET t=a(i): LET a(i)=a(j): LET a(j)=t: GO TO 1040
1070 LET a(lower)=a(j): LET a(j)=value: LET m(s)=j
1080 REM   Conquer
1090 IF m(s)-1>l(s) THEN LET l(s+1)=l(s): LET r(s+1)=m(s)-1: GO SUB 1000
1100 IF r(s)>m(s)+1 THEN LET l(s+1)=m(s)+1: LET r(s+1)=r(s): GO SUB 1000
1110 LET s=s-1: RETURN

2000 REM   Display array contents
2010 CLS : FOR n=1 TO 10: PRINT n,a(n): NEXT n : PRINT "..."
2020 FOR n=max-9 TO max : PRINT n,a(n): NEXT n : RETURN

9000 REM   Initialize and run
9010 LET i=0: LET j=0 : LET s=0 : RANDOMIZE 
9020 DIM a(max): FOR n=1 TO max: LET a(n)=RND : NEXT n
9030 DIM l(100): DIM r(100): DIM m(100) : LET l(1)=1: LET r(1)=max
9040 GO SUB 2000: PRINT AT 21,5;"UNSORTED"
9050 GO SUB 1000: REM   Recursive subroutine
9060 GO SUB 2000: PRINT AT 21,5;"SORTED"