' ************************************************************************
' Quick Sort (from QB 4.5 demo, slightly modified)
' ************************************************************************
' QuickSort works by picking a random "pivot" element in SortArray, then
' moving every element that is bigger to one side of the pivot, and every
' element that is smaller to the other side.  QuickSort is then called
' recursively with the two subdivisions created by the pivot. Once the
' number of elements in a subdivision reaches two, the recursive calls end
' and the array is sorted.
' ************************************************************************

SUB QuickSort (SortArray() AS DOUBLE, Low AS INTEGER, High AS INTEGER)

   DIM AS INTEGER I, J, RandIndex
   DIM AS DOUBLE  Partition
   
   IF Low < High THEN

      ' Only two elements in this subdivision; swap them if they are out of
      ' order, then end recursive calls:
      IF High - Low = 1 THEN
         IF SortArray(Low) > SortArray(High) THEN
            SWAP SortArray(Low), SortArray(High)
         END IF
      ELSE

         ' Pick a pivot element at random, then move it to the end:
         RandIndex = INT(RND * (High - Low + 1)) + Low
         SWAP SortArray(High), SortArray(RandIndex)
         Partition = SortArray(High)
         DO

            ' Move in from both sides towards the pivot element:
            I = Low: J = High
            DO WHILE (I < J) AND (SortArray(I) <= Partition)
               I = I + 1
            LOOP
            DO WHILE (J > I) AND (SortArray(J) >= Partition)
               J = J - 1
            LOOP

            ' If we haven't reached the pivot element, it means that two
            ' elements on either side are out of order, so swap them:
            IF I < J THEN
               SWAP SortArray(I), SortArray(J)
            END IF
         LOOP WHILE I < J

         ' Move the pivot element back to its proper place in the array:
         SWAP SortArray(I), SortArray(High)

         ' Recursively call the QuickSort procedure (pass the smaller
         ' subdivision first to use less stack space):
         IF (I - Low) < (High - I) THEN
            QuickSort SortArray(), Low, I - 1
            QuickSort SortArray(), I + 1, High
         ELSE
            QuickSort SortArray(), I + 1, High
            QuickSort SortArray(), Low, I - 1
         END IF
      END IF
   END IF
END SUB
