Tutorial 033 Quicksort 1000 numbers...

In Tutorial017 I gave a very simple home-made routine for sorting numbers, which sorts 1000 random numbers in 0.91sec (using my present machine).

Here is a more effiicient routine which uses the "Quicksort" algorithm, given by the mysterious "Simon" in "Quality Programs for the BBC Micro". As you will see, this uses a recursive routine in which PROCquicksort calls itself. With this routine 1000 random numbers are sorted in 0.03 seconds, which is 30 times faster.


      REM: Quicksort 1000 numbers
      REM: Richard Weston after "Simon"
      REM: 24th June 2003
      MODE8
      VDU14
      COLOUR9
      PRINTTAB(15)"1000 Random Numbers Sorted - using Quicksort..."'
      COLOUR7
      @%=4
      nums=1000
      DIM value(nums),rank(nums)
      FOR j=1 TO nums
        value(j)=RND(1000)
      NEXT j
      TIME=0
      PROCsort
      T=TIME/100
      COLOUR11
      PRINT"That took ";T;"secs - Press <SHIFT> to scroll down to see the rest"'
      COLOUR7
      FOR j=1 TO nums
        PRINTvalue(rank(j));
      NEXT j
      PRINT'" Press<SPACE> to go again..."
      G=GET
      RUN
      END
      :
      DEF PROCsort:LOCAL I
      FOR I = 1 TO nums
        rank(I)=I
      NEXT
      PROCquicksort(1,nums)
      ENDPROC
      :
      DEF PROCquicksort(low,high)
      LOCAL left,right,it,dummy
      left=low:right=high
      it=value(rank((low+high)DIV 2))
      REPEAT
        IF value(rank(left))>it THEN
          REPEAT left=left+1
          UNTIL value(rank(left))<=it
        ENDIF
        IF value(rank(right))<it THEN
          REPEAT right=right-1
          UNTIL value(rank(right))>=it
        ENDIF
        IF left<=right THEN
          dummy=rank(left)
          rank(left)=rank(right)
          rank(right)=dummy
          left=left+1
          right=right-1
        ENDIF
      UNTIL left>right
      IF right>low THEN PROCquicksort(low,right)
      IF left<high THEN PROCquicksort(left,high)
      ENDPROC

As "Simon" says, the routine involves picking a value somewhere in the middle, then swapping values to ensure all values on one side of the item are smaller than "it" and all values to the other side are larger than "it". By doing this recursively, keeping on dividing each section into smaller "halves", the sorting is actually done on sets of one or two numbers. (The items themselves are not actually reordered but an array of pointers, rank is used.

Next Tutorial

Richard Weston's Homepage