Sorting Arrays

[Moneo]

Aga,

I added the following sort algorithm of yours
DECLARE SUB qsort.byte.lowstart (array1() AS LONGINT, a.max%)
to a copy of the SORTDEMO.BAS program. Granted, this is a very simplistic test, but you can get a rough feeling for a sort algorithm's performance against others.

You will be pleased to know that your algorithm, with one exception, was faster than all the other algorithms in the SortDemo including the original QuickSort.

The one exception was Ethan Winer's version of QuickSort, which runs about 15% faster than yours. It's a non recursive QuickSort that accomplishes the same idea by using a stack. Here's his code:

Code:

'********* QSORT.BAS - Quick Sort algorithm
'Copyright (c) 1992 Ethan Winer

SUB QSort (Array(), StartEl, NumEls) STATIC

REDIM QStack(NumEls \ 5 + 10) 'create a stack

First = StartEl               'initialize work variables
Last = StartEl + NumEls - 1
StackPtr = 0

DO
  DO
    Temp = Array((Last + First) \ 2)  'seek midpoint
    I = First
    J = Last

    DO     'reverse both < and > below to sort descending
      WHILE Array(I) < Temp
        I = I + 1
      WEND
      WHILE Array(J) > Temp
        J = J - 1
      WEND
      IF I > J THEN EXIT DO
      IF I < J THEN SWAP Array(I), Array(J)
      I = I + 1
      J = J - 1
    LOOP WHILE I <= J

    IF I < Last THEN                    'Done
      QStack(StackPtr) = I              'Push I
      QStack(StackPtr + 1) = Last       'Push Last
      StackPtr = StackPtr + 2
    END IF

    Last = J
  LOOP WHILE First < Last

  IF StackPtr = 0 THEN EXIT DO
  StackPtr = StackPtr - 2
  First = QStack(StackPtr)              'Pop First
  Last = QStack(StackPtr + 1)           'Pop Last
LOOP

ERASE QStack               'delete the stack array

END SUB

*****