SORTING NUMBERS›           ===============››            by Ron Fetzer››           The Bubble Sort››     We will use a bubble sort›because it is the easiest to›understand. We first load the numbers›into a number array. In this sort 2›elements of the array are examined›during each pass of the loops. They›are switched if they are not in the›right order - low to high. If they›are in the right order the loop keeps›on going. A bubble sort is slow but›it is fine if you don't have too many›numbers.›     This sort uses nested loops. The›outer loop is the same as the number›of elements of the array. The inner›loop is ONE LESS than the elements of›the array. The switching is done›between these 2 loops. In our program›it is lines # 140 to 170.›     Lets enter these 4 numbers into›the bubble sort and see how they are›processed. The numbers are: 3,2,7,1›     Between the outer loop(4) and›the inner loop(3) we have (4x3=12) 12›passes of the loops. The bubble sort›arranges the 2 elements from low to›high. If these 2 elements are out of›order, it switches them. The array›starts out as: 3,2,1,7››PASS NUMBERS  ACTION  ELEMENT ORDER›---- -------  ------  -------------››1  [3,2],7,1  SWITCH 2,3  2,3,7,1›2  2,[3,7],1  OK          2,3,7,1›3  2,3,[7,1]  SWITCH 1,7  2,3,1,7›4  [2,3],1,7  OK          2,3,1,7›5  2,[3,1],7  SWITCH 1,3  2,1,3,7›6  2,1,[3,7]  OK          2,1,3,7›7  [2,1],3,7  SWITCH 1,2  1,2,3,7›8  1,[2,3],7  OK          1,2,3,7›9-12          OK          1,2,3,7››     If we want to sort in reverse›order from HIGH to LOW than we can›change the greater sign(>) in line›140 to less(<).›     Please key in this short demo›program to see how it works.››     10 --›     20 REM PUT NUMBERS INTO ARRAY›     30 CLS:?:?›     40 INPUT "HOW MANY NUMBERS TO›        SORT";K›     50 DIM A(K):?›     60 FOR X = 1 TO K›     70 INPUT "GIVE ME A NUMBER";N›     80 A(X)=N:REM<--ARRAY›     90 NEXT X›     100 --›     110 REM BUBBLE SORT›     120 FOR T = 1 TO K›     130 FOR Y = 1 TO K-1›     140 IF A(Y+1)>=A(Y) THEN 180›     150 TEMP = A(Y)›     160 A(Y) = A(Y+1)›     170 A(Y+1) = TEMP›     180 NEXT Y›     190 NEXT X›     200 --›     210 REM PRINT SORTED NUMBERS›     220 ?:? "SORTED NUMBERS":?›     230 FOR L = 1 TO K›     240 ? A(L);" ";:REM<--ARRAY›     250 NEXT L›     260 --››              MINI SORT››     The MINI sort is faster than the›bubble sort. This sort finds the›minimum valued element and places it›in the first position of the array.›It keeps on doing this until all›elements are arranged from LOW to›HIGH. In our program in line 50 we›use E=K. K is the number of elements›we have. The sort reduces K to 1. We›need the value of K to print out the›array, therefore we make it equal to›E.›     Please key in this short demo›program to see how it works.››     10 --›     20 REM PUT NUMBERS IN THE ARRAY›     30 CLS:?:?:K=0›     40 INPUT "HOW MANY NUMBERS TO›        SORT";K›     50 DIM A(K):E=K›     60 FOR X = 1 TO K›     70 INPUT "GIVE ME A NUMBER";N›     80 A(X)=N:REM<--ARRAY›     90 NEXT X›     100 --›     110 REM MINI SORT›     120 Y=A(1):Z=1›     130 FOR R = 2 TO K›     140 IF A(R)>=Y THEN Y=A(R):›         Z=R›     150 NEXT R›     160 SS=A(K):A(K)=A(Z):A(Z)=SS›     170 K=K-1:IF K>1 THEN 120›     180 --›     190 REM PRINT SORTED NUMBERS›     200 ?:? "SORTED NUMBERS"›     210 FOR T = 1 TO E›     220 ? A(T);" ";›     230 NEXT T›     240 --››        SORTING STRING ARRAYS›        =====================››       THE STRING BUBBLE SORT››     For a full understanding of a›STRING BUBBLE SORT please read the›section on PSEUDO STRING ARRAYS and›BUBBLE SORT first.›     First we set up a PSEUDO STRING›ARRAY. Without a string array you›cannot sort strings. We are going to›enter 4 words:››     ZERO›     ALL›     HOUSE›     COMPUTER››     A String Bubble Sort works the›same way as a number Bubble Sort,›except each element is longer. We›switch elements if they are not in›the right order - small to large. The›elements or substrings in this›demonstration are:››     1 to 10 (ZERO------)›    11 to 10 (ALL-------)›    21 to 30 (HOUSE-----)›    31 to 40 (COMPUTER--)››     The confusion comes when we have›to specify the substrings or elements›for switching. In order to clarify›this we use line 180 to assign›variables to these values.››     B(beginning)=Y›     E(ending)=Y+9›    BB(begin next higher elemt)=Y+10›    EE(end higher elmet)=Y+(10+9)››     Please type in this short demo›program to see how it works.››     10 --›     20 REM INPUT WORDS INTO ARRAY›     30 CLS:?›     40 INPUT "HOW MANY WORDS TO›        SORT";K›     50 DIM A$(K*10),SUB$(10),›        PAD$(10),TEMP$(10)›     60 PAD$="          ":REM 10›        SPACES›     70 ?:? "MAX. LETTERS = 10":?›     80 FOR N=1 TO K*10 STEP 10›     90 INPUT "GIVE ME A WORD";SUB$›    100 SL=LEN(SUB$)›    110 IF SL<10 THEN SUB$(SL+1)=›        PAD$›    120 A$(N,N+9)=SUB$›    130 NEXT N›    140 --›    150 REM STRING BUBBLE SORT›    160 FOR T=1 TO K*10 STEP 10›    170 FOR Y=1 TO (K*10)-10›        STEP 10›    180 B=Y:E=Y+9:BB=Y+10:›        EE=Y+(10+9)›    190 IF A$(BB,EE)>=A$(B,E)›        THEN 230›    200 TEMP$=A$(B,E)›    210 A$(B,E)=A$(BB,EE)›    220 A$(BB,EE)=TEMP$›    230 NEXT Y›    240 NEXT X›    250 --›    260 REM PRINT SORTED WORDS›    270 ?:? "SORTED WORDS:":?›    280 FOR L=1 TO K*10 STEP 10›    290 ? A$(L,L+9)›    300 NEXT L›    310 --››     A line by line explanation of›this program is as follows:››10-140 See the section on PSEUDO›    STRING ARRAYS›150 REM explanation›160 Outer Bubble Sort loop.›    K=number of words X the element›    length. STEP = elemnt length›170 Inner loop must be 1 element ›    less than the outer loop. That›    is why we have (K*10)-10›180-220 We examine each element. If›    the 2nd element is larger than›    the first element then it is OK.›    (small to large) - no switching.›    If it is not in the right order›    then we do the switching, just›    as we did with the number›    bubble sort.›230 End of inner loop›240 End of outer loop›250 30 dashes›260 REM explanation›270 Print›280 Loop to display sorted words›290 Print sorted words›300 End of loop›310 30 dashes››    If you want to sort larger›strings lets say 20 characters long›then change every reference from 10›to 20. They are in lines 50, 60, 70,›80, 110,      120(N,N+19), 160, 170›(E=Y+19, BB=Y+20, EE=Y+(20+19), 180,›280 (A$=L,L+19)›    If you want to sort from Z to A›then change the (>) in line 190 to›(<)›››        THE SHELL STRING SORT›        ---------------------››     The SHELL SORT is much faster›than the BUBBLE SORT. The reason it›is faster is that the number of›comparisons to be made is reduced. ›     If you try to sort 2 words or›less than you will get an error›because in line 90 the FOR-NEXT loop›becomes an illegal reverse loop (FOR›T=1 TO 0)›     In line 210 we assign variables›to the element beginning and›endings.››     B(beginning of element)=Y*10-9›     E(ending of element)=Y*10›    BB(Next higher elmt)=Z*10-9›    EE(Ending element)=Z*10››     Please key in this short demo›program to see how it works.››     10 --›     20 REM INPUT STRING ARRAY›     30 CLS:?›     40 INPUT "HOW MANY WORDS TO ›        SORT";K›     50 DIM A$(K*10),SUB$(10),›        PAD$(10),TEMP$(10)›     60 PAD$="          ":REM 10›        SPACES›     70 ?:? "MAX. NUMBER OF LETTERS›        = 10":?›     80 FOR N=1 TO K*10 STEP 10›     90 INPUT "GIVE ME A WORD";›        SUB$›    100 SL=LEN(SUB$)›    110 IF SL<10 THEN SUB$(SL+1)=›        PAD$›    120 A$(N,N+9)=SUB$›    130 NEXT N›    140 --›    150 REM SHELL SORT›    160 X=1›    170 X=2*X:IF X<=K THEN 170›    180 X=INT(X/2):IF X=0 THEN 300›    190 FOR T=1 TO K-X:Y=T›    200 Z=Y+X›    210 B=Y*10-9:E=Y*10:BB=Z*10-9:›        EE=Z*10›    220 IF A$(B,E)<=A$(BB,EE) THEN ›        270›    230 TEMP$=A$(B,E)›    240 A$(B,E)=A$(BB,EE)›    250 A$(BB,EE)=TEMP$›    260 Y=Y-X:IF Y>0 THEN 200›    270 NEXT T:GOTO 180›    280 --›    290 REM PRINT SORTED WORDS›    300 ?:? "SORTED WORDS:":?›    310 FOR L=1 TO K*10 STEP 10›    320 ? A$(L,L+9)›    330 NEXT L›    340 --››    If you want to sort larger›strings, lets say you want 20›characters, please change every›reference from 10 to 20. They are in›lines:›    50, 60, 70, 80, 110, 120(N,N+19),›210(B=Y*20-19, E=Y*20) and the same›for BB and EE, 310, 320(L,L+19).›››       RELATIONAL BUBBLE SORT›       ----------------------››     A relational sort is if you have›2 arrays and they are related to each›other in some way and the›relationship has to be maintained.›For instance, we want to write a›telephone directory program. In one›array we store the names and in the›other we store the phone numbers. We›are going to sort the names but the›phone numbers always have to be›switched with the name so the proper›relationship is maintained.›     When we sort with the Bubble›Sort the switching is done in lines›240, 250, and 260. It is done as›follows:››     240 TEMP$=A$(B,E):TEMP1$=›         B$(B,E)›     250 A$(B,E)=A$(BB,EE):B$(B,E)=›         B$(BB,EE)›     260 A$(BB,EE)=TEMP$:B$(BB,EE)=›         TEMP1$››     A$ is the name array and B$ is›the phone number string array. TEMP$›is in the name array and TEMP1$ is in›the phone number array. As we swtich›each name during a sort so we also›switch the phone number array so it›maintains its proper relationship.›     We use a string array for the›numbers because many people use a '-'›in their phone numbers and a number›array would not accept it. A second›reason is that if a number becomes›too large it is expressed in›scientific notation. ›     In our demo program we DIM each›element of the name and phone number›array to 10 to make it simpler to›understand.›     Please key in this short demo›program to see how it works.››     10 --›     20 REM INPUT NAMES AND NUMBERS›        INTO THE STRING ARRAYS›     30 CLS:?›     40 INPUT "HOW MANY PHONE›        NUMBERS TO SORT";K›     50 DIM A$(K*10),B$(K*10),›        SUB$(10),SUB1$(10),PAD$(10)›        TEMP$(10),TEMP1$(10)›     60 PAD$="          ":REM 10 ›        SPACES›     70 ?:? "MAX. LETTERS OR›        OR NUMBERS = 10":?›     90 INPUT "GIVE ME THE NAME";›        SUB$›    100 INPUT "GIVE ME THE NUMBER";›        SUB1$›    110 ?:SL=LEN(SUB$)›    120 SL1=LEN(SUB1$)›    130 IF SL<10 THEN SUB$(SL+1)=›        PAD$›    140 IF SL1<10 THEN SUB1$(SL1+1)=›        PAD$›    150 A$(N,N+9)=SUB$›    160 B$(N,N+9)=SUB1$›    170 NEXT N›    180 --›    190 REM RELATIONAL BUBBLE SORT›    200 FOR T=1 TO K*10 STEP 10›    210 FOR Y=1 TO (K*10)-10 STEP 10›    220 B=Y:E=Y+9:BB=Y+10:›        EE=Y+(10+9)›    230 IF A$(BB,EE)>=A$(B,E) THEN›        270›    240 TEMP$=A$(B,E):TEMP1$=›        B$(B,E)›    250 A$(B,E)=A$(BB,EE):B$(B,E)=›        B$(BB,EE)›    260 A$(BB,EE)=TEMP$:B$(BB,EE)=›        TEMP1$›    270 NEXT Y›    280 NEXT T›    290 --›    300 CLS›    310 REM PRINT OUT SORTED PHONE›        LIST›    320 ?:? "    TELEPHONE LIST":?›    330 FOR L=1 TO K*10 STEP 10›    340 ? A$(L,L+9);B$(L,L+9)›    350 NEXT L›    360 --››    The two arrays can use the same›PAD$ (ln #60) because they are the›same size. They can use the same›begining and ending element numbers›because they are the same size (ln›#220)›    If you want a printed list please›change lines 320 and 340 from PRINT›to LPRINT.›    In a similar manner you could›have a relational sort between a›number array and a string array. For›example you want to sort by score a›bowling league. The sort would be›done on the scores(number sort) and›the names would have to maintain›their relationship to the score.›    To get a clear understanding of›relational sorts, please read the›section on ARRAYS, PSEUDO STRING›ARRAYS, NUMBER BUBBLE SORT and STRING›BUBBLE SORT.››            LOADING SORTS›            -------------›     You are urged to key in each›sort yourself because you will learn›a great deal from this. If you do not›want to do this you can load the›sorts into your computer. The file›names are as follows:››     1)BUBBLE.NUM›     2)BUBBLE.STR›     3)BUBBLE.REL›     4)MINISRT.NUM›     5)SHELLSRT.STR››     If you have any comments or›suggestions about these tutorials,›they are welcome. Please write to:››             RON. FETZER›            22 MONACO AVE›          ELMONT, NY. 11003››              ADDENDUM›              --------››     If you want to compile a program›you CANNOT use the command 'END'. It›does not compile. On page 26 and page›29 of the EXPANDED DOCUEMTATION on›PROC - ENDPROC and ERROR 27 I said›you should have an END statement›somewhere in your program. This is›not necessary - the only thing you›need is ANOTHER executable line after›the EXEC command››             **********››     Sometimes it is necessary to›construct a string array in a›different manner than I have shown.›For example we want a string array›with 21 letters. This is an alternate›way of doing it.››     10 DIM ARRAY$(5*21),B$(21),›        PAD$(21)›     20 FOR X=1 TO 5›     30 PAD$="                     "›     40 INPUT "GIVE ME A NAME";B$›     50 BL=LEN(B$):IF BL<21 THEN›        B$(BL+1)=PAD$›     60 ARRAY$(X*21-20,X*21)=›        B$:REM ARRAY›     70 NEXT X››             **********››     Please load the program›"CATALOG.BAS" into your computer. It›is written in TURBO-BASIC and it will›give you some help in using TURBO-›BASIC. This program reads your disk›directory of all your disks and makes›ONE ALPHABETICAL or NUMBERIC list of›all your disk files.››             **********››