'===========================================================================
' Subject: BUBBLE SORT VS. QUICK SORT        Date: 05-30-98 (11:50)       
' Author:  Steve Gomez                       Code: QB, QBasic, PDS        
' Origin:  alt.lang.basic                  Packet: ALGOR.ABC
'===========================================================================
'From: cowboy@nwlink.com (Steve Gomez-Fox)

'> bigger the number of number/letters, the slower and slower it goes!
'> The code's pathetic over 1000 numbers! The question posed is, where is
'> a faster way to sort then just a N ^ 2 (I think that's what it appears

'Below find a program I put together to compare sorting speeds using
'the Bubble Sort algorithm and the Quick Sort algorithm.  You will be
'amazed by the difference.  The downside to Quick Sort is that the code
'is longer, it must be in a SUB because it is recursive, and being
'recursive, it uses up stack space.  But, if you are sorting more than
'a handful of elements, you will find it is well worth it. 

'Results on my P166

'Elements    Bubble Sort  Quick Sort
'-----------------------------------
'  1000        1.81 sec    0.05 sec
'  5000       45.09 sec    0.28 sec
' 10000      182.24 sec    0.50 sec
' 15000      407.43 sec    0.83 sec


'  QSORT.BAS
'=============
DECLARE SUB BubbleSort ()
DECLARE SUB QuickSort (qsLeft AS INTEGER, qsRight AS INTEGER)

DIM Elements AS LONG

CLS

DO UNTIL Elements > 1 AND Elements < 32768
  INPUT "Number of elements (2 to 16383)"; Elements
  IF Elements < 2 OR Elements > 16383 THEN PRINT "Out of range"
LOOP
Elements = Elements - 1

DIM qsArray(Elements) AS INTEGER
DIM bsArray(Elements) AS INTEGER
DIM qsTime AS SINGLE
DIM bsTime AS SINGLE
DIM RandInt AS INTEGER
DIM Index AS INTEGER

FOR Index = 0 TO Elements
  RandInt = RND * 32768
  qsArray(Index) = RandInt
  bsArray(Index) = RandInt
NEXT Index

CLS
PRINT "Sorting"; Elements + 1; "elements"
PRINT

bsTime = TIMER
PRINT "Executing the Bubble Sort"
BubbleSort
bsTime = TIMER - bsTime
PRINT "Sort completed in "; bsTime; " seconds"
FOR Index = LBOUND(bsArray) TO UBOUND(bsArray) - 1
  IF bsArray(Index) > bsArray(Index + 1) THEN PRINT "Error": END
NEXT Index
PRINT "Sort verified correct"
PRINT

PRINT "Executing the Quick Sort"
qsTime = TIMER
'Call QuickSort initially with the lowest and highest
'bounds of the array
QuickSort LBOUND(qsArray), UBOUND(qsArray)
qsTime = TIMER - qsTime
PRINT "Sort completed in "; qsTime; " seconds"
FOR Index = LBOUND(qsArray) TO UBOUND(qsArray) - 1
  IF qsArray(Index) > qsArray(Index + 1) THEN PRINT "Error": END
NEXT Index
PRINT "Sort verified correct"
PRINT

SUB BubbleSort
  SHARED bsArray() AS INTEGER

  DIM Index1 AS INTEGER
  DIM Index2 AS INTEGER

  FOR Index1 = LBOUND(bsArray) TO UBOUND(bsArray)
    FOR Index2 = LBOUND(bsArray) TO UBOUND(bsArray) - Index1 - 1
      IF bsArray(Index2) > bsArray(Index2 + 1) THEN
        SWAP bsArray(Index2), bsArray(Index2 + 1)
      END IF
    NEXT Index2
  NEXT Index1
END SUB

SUB QuickSort (qsLeft AS INTEGER, qsRight AS INTEGER)
  SHARED qsArray() AS INTEGER   'DataType of array being sorted

  DIM NewLeft AS INTEGER
  DIM NewRight AS INTEGER
  DIM Center AS INTEGER
  DIM CtrVal AS INTEGER  'DataType of array being sorted

  IF qsLeft < qsRight THEN
    'Select the element halfway between qsLeft and qsRight
    'for comparison
    Center = (qsLeft + qsRight) / 2
    CtrVal = qsArray(Center)

    'Move this center element out of the way
    SWAP qsArray(qsRight), qsArray(Center)
      NewLeft = qsLeft
      NewRight = qsRight

    DO
      'Look for an element to the left of center that should
      'be to the right
      DO WHILE NewLeft < NewRight AND qsArray(NewLeft) <= CtrVal
        NewLeft = NewLeft + 1
      LOOP

      'Look for an element to the right of center that should be
      'to the left
      DO WHILE NewRight > NewLeft AND qsArray(NewRight) >= CtrVal
        NewRight = NewRight - 1
      LOOP

      ' If NewLeft < NewRight, we found two elements to swap
      IF NewLeft < NewRight THEN
        SWAP qsArray(NewLeft), qsArray(NewRight)
      END IF
    LOOP WHILE NewLeft < NewRight

    'Move the center element back into place
    SWAP qsArray(NewLeft), qsArray(qsRight)

    ' Sort the two sections that the above code has left out
    IF (NewLeft - qsLeft) < (qsRight - NewLeft) THEN
      QuickSort qsLeft, NewLeft - 1
      QuickSort NewLeft + 1, qsRight
    ELSE
      QuickSort NewLeft + 1, qsRight
      QuickSort qsLeft, NewLeft - 1
      END IF
  END IF
END SUB