1000 ! SORT.BAS Sort testing program & ! & ! Idea from Creative Computing magazine Nov/Dec 76, Page 76 and & ! the RSTS Professional magazine, Volume 3, #4, December 1981, et. al. & ! & ! 17-Nov-76 *M & ! & ! 21-Dec-83 last edit *M & ! & ! Author: W. Franklin Mitchell, Jr. & ! Director of Computer Services & ! Erskine College, Due West, South Carolina & ! & ! *********************************************************************** & ! * This software is furnished without charge by Erskine College and * & ! * may be copied only with the inclusion of the author's name and * & ! * copyright notice. No title to or ownership of this software is * & ! * hereby transmitted. Neither Erskine College nor the author assumes * & ! * any responsibility for the use or reliability of this software. The * & ! * author welcomes comments and/or bug reports mailed to Franklin * & ! * Mitchell, Erskine College, Box 86L, Due West, South Carolina 29639. * & ! *********************************************************************** & 1020 PRINT "This program makes up equal groups of data and sorts each using" & \ PRINT "different methods. You pick the best method!" & 1040 PRINT & \ INPUT "Sort how many random numbers <200>"; QUANTITY% & \ QUANTITY% = 200% IF QUANTITY% <= 0% & \ PRINT & \ IF QUANTITY% <= 512% & THEN & PRINT NUM1$(QUANTITY%); " numbers to sort (Wait please.)" & ELSE & PRINT "Not set up to sort over 512 numbers." & \ GOTO 1040 & 1060 DIM BUBBLE%(512), SHELL.METZNER%(512), QUICK.SORT%(512), SELECTION%(512) & 1080 RANDOMIZE & 1100 W% = 28% & \ PRINT & \ PRINT & \ PRINT "Sort type"; & \ PRINT TAB(W%); "CPU seconds Switches Comparisons" & \ FORMAT$ = " #,###.# #,###,### #,###,###" & 1120 BUBBLE%(X%) = FIX(RND*32766.) FOR X% = 1% TO QUANTITY% & \ SHELL.METZNER%(X%) = BUBBLE%(X%) FOR X% = 1% TO QUANTITY% & \ QUICK.SORT%(X%) = BUBBLE%(X%) FOR X% = 1% TO QUANTITY% & \ SELECTION%(X%) = BUBBLE%(X%) FOR X% = 1% TO QUANTITY% & 1140 GOSUB 1280 ! Bubble Sort & 1160 GOSUB 1400 ! Shell - Metzner Sort & 1180 GOSUB 2000 ! Selection sort & 1190 GOSUB 1580 ! Quick sort & 1200 PRINT & \ PRINT "All sorted arrays "; 1220 FOR X% = 1% TO QUANTITY% & \ IF BUBBLE%(X%) <> SHELL.METZNER%(X%) & OR BUBBLE%(X%) <> QUICK.SORT%(X%) & OR BUBBLE%(X%) <> SELECTION%(X%) & THEN & PRINT "differ. ("; NUM1$(X%); ")" & \ GOTO 32767 1240 NEXT X% & \ PRINT "match." & \ GOTO 32767 & & 1260 ! Bubble Sort & 1280 CPU.TIME = TIME(1%) & \ PRINT & \ PRINT "Bubble sort:"; & \ SWITCHES, COMPARISONS = 0 & 1300 FOR A% = 1% TO QUANTITY% & \ FLAG% = - 1% 1320 FOR B% = 1% TO QUANTITY% - A% & \ COMPARISONS = COMPARISONS + 1 & \ IF BUBBLE%(B%) > BUBBLE%(B% + 1%) & THEN & SWITCHES = SWITCHES + 1 & \ FLAG% = 0% & \ TMP% = BUBBLE%(B%) & \ BUBBLE%(B%) = BUBBLE%(B% + 1%) & \ BUBBLE%(B% + 1%) = TMP% 1340 NEXT B% & \ GOTO 3000 IF FLAG% 1360 NEXT A% & \ GOTO 3000 & & 1380 ! Shell - Metzner Sort & 1400 CPU.TIME = TIME(1%) & \ PRINT & \ PRINT "Shell - Metzner sort:"; & \ SWITCHES, COMPARISONS = 0 & \ M6% = QUANTITY% & 1420 M6% = M6%/2% & \ GOTO 3000 IF M6% = 0% 1440 K6% = QUANTITY% - M6% & \ J6% = 1% 1460 I6% = J6% 1480 L6% = I6% + M6% & \ COMPARISONS = COMPARISONS + 1 & \ GOTO 1520 IF SHELL.METZNER%(I6%) <= SHELL.METZNER%(L6%) 1500 SWITCHES = SWITCHES + 1 & \ TMP% = SHELL.METZNER%(I6%) & \ SHELL.METZNER%(I6%) = SHELL.METZNER%(L6%) & \ SHELL.METZNER%(L6%) = TMP% & \ I6% = I6% - M6% & \ GOTO 1480 IF I6% >= 1% 1520 J6% = J6% + 1% & \ GOTO 1420 IF J6% > K6% 1540 GOTO 1460 & & 1560 ! Quick sort & 1580 CPU.TIME = TIME(1%) & \ SWITCHES, COMPARISONS = 0 & \ PRINT & \ PRINT "Quick sort:"; & \ A% = FNQUICK.SORT%(1%,QUANTITY%,0%,0%) & \ GOTO 3000 & 1600 DEF* FNQUICK.SORT%(Y1%,Y2%,X%,Y%) & \ X% = Y1% & \ Y% = Y2% & \ Z% = QUICK.SORT%((Y1% + Y2%)/2%) 1620 WHILE X% <= Y% & \ TEMP.X% = X% & \ TEMP.Y% = Y% & \ X% = X% + 1% WHILE QUICK.SORT%(X%) < Z% & \ Y% = Y% - 1% WHILE QUICK.SORT%(Y%) > Z% & \ COMPARISONS = COMPARISONS + (X% - TEMP.X%) + (TEMP.Y% - Y%) & \ IF X% <= Y% & THEN & TMP% = QUICK.SORT%(X%) & \ QUICK.SORT%(X%) = QUICK.SORT%(Y%) & \ QUICK.SORT%(Y%) = TMP% & \ X% = X% + 1% & \ Y% = Y% - 1% & \ SWITCHES = SWITCHES + 1 1640 NEXT & \ GOTO 1660 IF Y%-Y1% > Y2%-X% & \ TMP% = FNQUICK.SORT%(Y1%, Y%,0%,0%) IF Y1% < Y% & \ TMP% = FNQUICK.SORT%( X%,Y2%,0%,0%) IF X% < Y2% & \ GOTO 1680 1660 TMP% = FNQUICK.SORT%( X%,Y2%,0%,0%) IF X% < Y2% & \ TMP% = FNQUICK.SORT%(Y1%, Y%,0%,0%) IF Y1% < Y% 1680 FNEND & & 2000 ! Selection sort & 2020 CPU.TIME = TIME(1%) & \ PRINT & \ PRINT "Selection sort:"; & \ SWITCHES, COMPARISONS = 0 & 2040 FOR I% = 1% TO QUANTITY% - 1% & \ J% = I% 2060 FOR K% = J% + 1% TO QUANTITY% & \ COMPARISONS = COMPARISONS + 1 & \ J% = K% IF SELECTION%(K%) < SELECTION%(J%) 2080 NEXT K% 2100 SWITCHES = SWITCHES + 1 & \ TMP% = SELECTION%(I%) & \ SELECTION%(I%) = SELECTION%(J%) & \ SELECTION%(J%) = TMP% 2120 NEXT I% & \ GOTO 3000 & 3000 TOTAL.CPU.TIME = (TIME(1%) - CPU.TIME)/10. & \ PRINT TAB(W%); & \ PRINT USING FORMAT$, TOTAL.CPU.TIME, SWITCHES, COMPARISONS 3020 RETURN & 32767 END