Tutorial 017 Sorting

Tutorial 017- Sorting

The following simple routine illustrates how to sort a small set of numbers into descending order

      REM: Sort 10 Numbers
      MODE8
      DIM A(10)
      REPEAT
        PRINT"Ten random numbers <13"
        FOR n=1 TO 10
          A(n)=RND(12)
          PRINTA(n)
        NEXT n
        PRINT'"Press SPACE to sort :"'
        G=GET
        REM: Sort
        FOR n=1 TO 9
          FOR m=n+1 TO 10
            temp=A(n)
            IF A(m)>A(n) THEN
              A(n)=A(m)
              A(m)=temp
            ENDIF
          NEXT m
        NEXT n
        FOR n=1 TO 10
          PRINTA(n)
        NEXT n
        PRINT''"Press SPACE to Repeat"
        G=GET
        CLS
      UNTIL FALSE

Annotated Listing

      REM: Sort 10 Numbers
      MODE8
      DIM A(10) *** Reserves ten memory locations in an "array"which stores the numbers to be sorted - call it A,B... what you like ***
      REPEAT
        PRINT"Ten random numbers <13"
        FOR n=1 TO 10
          A(n)=RND(12) *** Put a random number from one to 12 into each memory slot ***
          PRINT A(n) *** See what we've got ***
        NEXT n
        PRINT'"Press SPACE to sort :"'
        G=GET *** Give the user something to do and avoid distraction by the result just yet ***
        REM: Sort
        FOR n=1 TO 9 *** Nested loops enable us to step down the array and compare each position with further ones ***
          FOR m=n+1 TO 10
            temp=A(n) *** temp(orary) is a variable to temporarily store the contents of A(n).... ***
            IF A(m)>A(n) THEN *** if the number in the next position is greater ..... ***
              A(n)=A(m) *** it is swapped with A(n) ....***
              A(m)=temp *** using temp to carry out the handover ***
            ENDIF *** Clever stuff, eh? ***
          NEXT m
        NEXT n
        FOR n=1 TO 10 *** Now print the new contents of the array to check that it has worked ***
          PRINTA(n)
        NEXT n
        PRINT''"Press SPACE to Repeat"
        G=GET
        CLS
      UNTIL FALSE

This "simple sort" is fine for sorting a relatively few numbers but there are more efficient (and intricate) routines for sorting very large arrays of numbers. But this will do for the present...

Here's a modification of the above to see how long this routine and your machine takes to sort out 1000 random numbers in the range 1 to 500. We might expect each number to appear twice on average....

      REM: Sort 1000 Numbers
      MODE8
      VDU14
      N=1000
      DIM A(N)
      REPEAT
        PRINT"Sort 1000 numbers"''
        PRINT"Press Shift key (above the control key) for subsequent pages of results"
        FOR n=1 TO N
          A(n)=RND(500)
          REM PRINTA(n)
        NEXT n
        OFF
        PRINT'"Press SPACE to sort :"'
        G=GET
        TIME=0
        REM: Sort
        FOR n=1 TO (N-1)
          FOR m=n+1 TO N
            temp=A(n)
            IF A(m)>A(n) THEN
              A(n)=A(m)
              A(m)=temp
            ENDIF
          NEXT m
        NEXT n
        PRINT"Time taken to sort ";N;" numbers = ";TIME/100;"secs"'
        FOR n=1 TO N
          PRINT;A(n);" ";
        NEXT n
        PRINT''"Press SPACE to Repeat"
        G=GET
        CLS
      UNTIL FALSE

Next Tutorial

Richard Weston's Homepage