[futurebasic] Quick Sort For Numbers (Answers & Code)

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

From: DesignInc@...
Date: Wed, 9 Jun 1999 10:35:23 EDT
I looked over the sorting routines and added one I found a few years ago, 
simply called "SORT".  I like "SORT" because it is small and fast.

My analysis of the four sort routines:

With 5000 items ( on a 233MHz G3 )
- Sort 25K ms
- ShellShortIndex  28K ms
- ShellSort  20K ms
- InsertSort  901K ms

With 50,000 items
- Sort 339K ms
- ShellShortIndex 490K ms
- ShellSort  336K ms



'====== The SORT code ==========


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

CLEAR LOCAL
LOCAL FN Sort(n&)
  
  DIM size&                                       '-- size of array
  DIM gap&
  DIM count&
  DIM theItem&
  
  '---------------- do the sorting -----------------------------
  size&=n&
  gap&=size&
  DO
    gap&=INT(gap&\1.3)
    FOR count&=1 TO size&-gap&
      theItem&=count&+gap&
      IF gArray&(count&)>gArray&(theItem&) THEN SWAP gArray&(count&), 
gArray&(theItem&)
    NEXT count&
  UNTIL gap&=0
END FN


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, a$
n&=50000                                          ' 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                 '..these…
FN Sort(n&): indx=_false                          '…four.

MS&=FN MicroSeconds&-MS&
a$=USING"###,###,###,###";MS&
PRINT %(100,50) a$" microseconds    (click to continue)"
FN PrintArray(20,indx)
DO: UNTIL FN BUTTON