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 <<<<<<<<<<<<<<<››