[futurebasic] Re: [FB] Quick Sort for Numbers?

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : June 1999 : Group Archive : Group : All Groups

From: Robert Purves <robert.purves@...>
Date: Wed, 9 Jun 1999 18:11:43 +1200
>I need to be able to sort up to 250,000 values from smallest to largest.

>Anything that would work quickly for this high amount of numbers would be
>nice no matter what the setup though. I tried the FB Bubble sort, but it
>took about 6 years to do 250,000 points. Heck, it took 6 years to do just
>50,000 points.

Bubble sort is one of the worst methods known.
Insertion sort is better, but still hopeless for big tasks (n>100 or so).
Shell's method is vastly better for big tasks.
HeapSort and QuickSort are industrial-strength methods that you will
probably wish to explore eventually.

The demo below allows timing comparisons between Insertion and Shell,
showing a huge advantage to Shell for n greater than a few hundred.

Use an indexed sort when you are sorting large records that would be slow
to copy. An indexed sort swaps index values or pointers in an index array
(fast) instead of moving around the original records (slow). The demo below
includes an indexed Shell sort (which is of course a little _slower_ than
the plain version here, because we are only sorting a simple array whose
elements _can_ be copied quickly).

COMPILE ,_dimmedVarsOnly
DIM gArray&(100000), gIndex&(100000)
END GLOBALS

LOCAL FN InsertionSort(n&)
'Sort gArray&(1:n&) ascending
'On exit gArray&(1) is smallest, gArray&(n&) is largest
DIM i&,j&,v&
LONG IF n&>1
  FOR j&=2 TO n&
    v&=gArray&(j&)
    FOR i&=j&-1 TO 1 STEP -1
      IF gArray&(i&)<=v& THEN GOTO "insskip"
      gArray&(i&+1)=gArray&(i&)
    NEXT i&
    i&=0
    "insskip"
    gArray&(i&+1)=v&
  NEXT j&
END IF
END FN

LOCAL FN ShellSort(n&)
'Sort gArray&(1:n&) ascending
'On exit gArray&(1) is smallest, gArray&(n&) is largest
'The method for adjusting incr& is recommended by Knuth and Numerical Recipes
DIM i&,j&,n&,incr&,v&
LONG IF n&>1
  incr&=1
  DO
    incr&=3*incr&+1
  UNTIL incr&>n&
  DO
    incr&=incr&/3
    FOR i&=incr&+1 TO n&
      v&=gArray&(i&)
      j&=i&
      WHILE gArray&(j&-incr&)>v&
        gArray&(j&)=gArray&(j&-incr&)
        j&=j&-incr&
        IF j&<=incr& THEN GOTO "skip"
      WEND
      "skip"
      gArray&(j&)=v&
    NEXT i&
  UNTIL incr&<=1
END IF
END FN

LOCAL FN ShellSortIndex(n&)
DIM i&,j&,n&,incr&,v&,vIndx&
'Sort gArray&(gIndex&(1):gIndex&(n&)) ascending
'On exit gArray&(gIndex&(0)) is smallest, (gIndex&(n&)) is largest
  LONG IF n&>1
    incr&=1
    DO
      incr&=3*incr&+1
    UNTIL incr&>n&
    DO
      incr&=incr&/3
      FOR i&=incr&+1 TO n&
        vIndx&=gIndex&(i&)
        v&=gArray&(vIndx&)
        j&=i&
        WHILE gArray&(gIndex&(j&-incr&))>v&
          gIndex&(j&)=gIndex&(j&-incr&)
          j&=j&-incr&
          IF j&<=incr& THEN GOTO "iskip"
        WEND
        "iskip"
        gIndex&(j&)=vIndx&
      NEXT i&
    UNTIL incr&<=1
  END IF
END FN

LOCAL FN FillArrays(n&)
DIM i&
FOR i&=1 TO n&
  gArray&(i&)=RND(n&)
  gIndex&(i&)=i&
NEXT
END FN

LONG FN MicroSeconds&
  ` dc.w $A193
END FN

LOCAL FN PrintArray(n&,indx)
DIM i&
FOR i&=1 TO n&
  LONG IF indx
    PRINT gArray&(gIndex&(i&))
  XELSE
    PRINT gArray&(i&)
  END IF
NEXT
END FN

WINDOW 1,,(0,0)-(500,440)
DIM MS&,n&,indx
n&=15  ' try values up to 100000
FN FillArrays(n&)
MS&=FN MicroSeconds&

'FN ShellSortIndex(n&): indx=_zTrue  ' uncomment..
FN ShellSort(n&): indx=_false        '..one of these..
'FN InsertionSort(n&): indx=_false   '..three

MS&=FN MicroSeconds&-MS&
PRINT MS&" microseconds"
IF n&<=15 THEN FN PrintArray(n&,indx)
DO: UNTIL FN BUTTON

Robert Purves