TS1000 Visible Sort

This listing is a great way to get a handle on how sorting routines actually sort. Since the program has been designed to be friendly, it guarantees that the code is difficult to follow.

Lines 1 to 100 set up the arrays and provide instructions. Lines 101 to 196 plot the random points, both to the screen and to the postion array. Line 210 puts the computer in slow mode after the screen is built. Insert 105 SLOW and then you can watch the screen being built. Lines 300 – 480 do the bubble sort and 500 – 770 do the shell sort. You can insert your own routine at line 900 if you so desire.

This listing can be converted for the 2068 by changing UNPLOTs to PLOT and using OVER 1 to over plot old locations on the screen and blank them out.

The program shows the shell sort to be much more efficient than the bubble sort. This is not always the case. If you are merging two files, in which the data are already close to their final position, the shell sort will scramble the data before putting them in their final order!

The Variables

S(39)   Holds the sample array
X       Utility counter
D       Carries random value to S(X)
MO      Move counter
Y       Utility counter for nested loops
Q$      Query or tells if swap is made

Shell sort variables

M       Size of the swaps
X       Lower item to compare
Y       Upper item to compare
J       Inner loop counter

  10 FAST
  20 DIM S(39)
  25 LET B$="                                "
  30 PRINT ,,,,"THIS PROGRAM PROVIDES A SLOW    MOTION DISPLAY OF 2 COMMON SORT ALGORITHMS"
  40 PRINT ,,"PRESS A KEY TO CONT "
  50 PAUSE 4E4
  60 CLS
  70 PRINT "FIRST, POINTS WILL BE PLOTTED INA RANDOM ORDER.",,,,"THEY WILL THEN BE SORTED TO FORMA DIAGONAL LINE."
  80 PRINT ,,,,"PRESS A KEY TO CONT "
  90 PAUSE 4E4
 100 CLS
 110 LET Q$="010203040506070809101112131415161718192021222324252627282930313233343536373839"
 120 FOR X=1 TO 39
 130 LET D=1+INT (RND*LEN Q$/2)*2
 140 LET S(X)=VAL Q$(D TO D+1)
 150 LET Q$=Q$( TO D-1)+Q$(D+2 TO )
 160 PRINT AT 20,0;B$
 170 PRINT AT 20,0;"X AXIS = ";X;" Y AXIS = ";S(X)
 180 PLOT X,4+S(X)
 190 NEXT X
 200 PRINT AT 20,0;"CHOOSE SORT ROUTINE  (B) BUBBLE(S) SHELL    (Y) YOUR OWN"
 210 SLOW
 220 LET MO=0
 230 LET Q$=INKEY$
 240 IF Q$="B" THEN GOTO 300
 250 IF Q$="S" THEN GOTO 500
 260 IF Q$="Y" THEN GOTO 900
 270 GOTO 230
 300 PRINT AT 20,0;B$;B$
 305 PRINT AT 20,0;"BUBBLE SORT",,"MOVE ="
 310 FOR Y=39 TO 1 STEP -1
 320 LET Q$=""
 330 FOR X=1 TO Y-1
 340 PLOT X,4
 350 IF S(X)<S(X+1) THEN GOTO 440
 360 LET Q$="Y"
 370 LET MO=MO+1
 375 PRINT AT 21,7;MO
 380 UNPLOT X,4+S(X)
 390 UNPLOT X+1,4+S(X+1)
 400 LET T=S(X)
 410 LET S(X)=S(X+1)
 420 LET S(X+1)=T
 430 PLOT X,4+S(X)
 440 PLOT X+1,4+S(X+1)
 450 UNPLOT X,4
 460 NEXT X
 470 IF Q$="Y" THEN NEXT Y
 480 GOTO 780
 500 PRINT AT 20,0;B$;B$;AT 20,0;"SHELL SORT",,"MOVE = "
 510 LET M=39
 520 LET M=INT (M/2)
 530 IF M=0 THEN GOTO 780
 550 LET J=1
 560 LET X=J
 570 LET Y=X+M
 580 PLOT X,4
 590 PLOT Y,4
 600 IF S(X)<S(Y) THEN GOTO 730
 610 LET MO=MO+1
 615 PRINT AT 21,7;MO
 620 UNPLOT X,4+S(X)
 630 UNPLOT Y,4+S(X)
 640 LET T=S(X)
 650 LET S(X)=S(Y)
 660 LET S(Y)=T
 670 PLOT X,4+S(X)
 680 PLOT Y,4+S(Y)
 690 UNPLOT X,4
 695 UNPLOT Y,4
 700 UNPLOT Y,4+S(X)
 710 LET X=X-M
 720 IF X>=1 THEN GOTO 570
 730 UNPLOT X,4
 740 UNPLOT Y,4
 750 LET J=J+1
 760 IF J>39-M THEN GOTO 520
 770 GOTO 560
 780 PRINT AT 20,0;B$;B$
 790 PRINT AT 20,0;"COMPLETE ";MO;" MOVES REQUIRED"
 800 PAUSE 4E4
 810 FAST
 820 CLS
 830 RUN
 900 PRINT AT 20,0;"NO ROUTINE YET"
 910 PAUSE 150
 920 GOTO 200
1000 SAVE "SORT"
1010 RUN