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 T¢ 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 20 (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 elemt)=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 T¢ 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 = element 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¢ liness: 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 switch¢ 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¢ NUMBERS = 10":?¢ 80 FOR N=1 TO K*10 STEP 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¢ beginning 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¢ ¢ ADDENDUM¢ --------¢¢ 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¢¢ In line 60 X*21-20,X*21. This¢ will create the element length that¢ we previously used a FOR-NEXT-STEP¢ LOOP for. In all other respects the¢ program remains the same. For¢ example, when X=1 the elements will¢ be (1*21)21-20 or 1 the other number¢ will be (1*21)or 21. Thus the element¢ length will be 1 to 21 on the first¢ pass of the loop. In a similar manner¢ all the other element numbers will be¢ generated.¢¢ >>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<¢¢
