Quicksort code

 BBS: Inland Empire Archive
Date: 02-24-94 (09:01)             Number: 191
From: BRIAN MCLAUGHLIN             Refer#: NONE
  To: JEFF COCHRAN                  Recvd: NO  
Subj: Quicksort code                 Conf: (2) Quik_Bas
Here's Cornel Huth's excellent code for a quicksort (slightly
rejiggered by me). You mentioned updating the screen within the sorting
loop as a possible source of slowdown...and you may be on to something
there. (A screen update every few seconds should be enough for anyone.)

If this code doesn't deliver the snap and speed you want, you may need
to rethink your whole approach -- maybe use some kind of hashing or
indexing on the fly. I am not a database expert and can't help much

'----------------------- START CODE ----------------------------

DECLARE SUB QuickSort (Lower%, Upper%, Array$())

TYPE QSortStackType  'for QuickSort

 SUB QuickSort (Lower%, Upper%, Array$())
  'QuickSort (iterative rather than recursive).
  'Public domain code, by Cornel Huth. (Slightly revamped.)

  'Lower% and Upper% bound the area to be sorted within Array$.
  'To change the array type, change the array specifier in every
  'instance of "Array$" and change the variable "Compare$", too.

  'To discover just how much of the "stack" array has been used,
  'unREM the lines containing references to MaxStackPtr%

  DIM LStack(1 TO 128) AS QSortStackType 'our "stack" array
  StackPtr% = 1                          'our "stack" pointer

  'MaxStackPtr% = StackPtr%
  LStack(StackPtr%).Low = Lower%
  LStack(StackPtr%).Hi = Upper%
  StackPtr% = StackPtr% + 1              'offset the subtraction, below

    StackPtr% = StackPtr% - 1
    Low% = LStack(StackPtr%).Low
    Hi% = LStack(StackPtr%).Hi

      Border1% = Low%
      Border2% = Hi%
      Mid% = (Low% + Hi%) \ 2
      Compare$ = Array$(Mid%)
        DO WHILE Array$(Border1%) < Compare$
          Border1% = Border1% + 1

        DO WHILE Array$(Border2%) > Compare$
          Border2% = Border2% - 1

        IF Border1% <= Border2% THEN
          SWAP Array$(Border1%), Array$(Border2%)
          Border1% = Border1% + 1
          Border2% = Border2% - 1
        END IF

      LOOP WHILE Border1% <= Border2%

      IF Border2% - Low% < Hi% - Border1% THEN
        IF Border1% < Hi% THEN
          LStack(StackPtr%).Low = Border1%
          LStack(StackPtr%).Hi = Hi%
          StackPtr% = StackPtr% + 1
        END IF
        Hi% = Border2%
        IF Low% < Border2% THEN
          LStack(StackPtr%).Low = Low%
          LStack(StackPtr%).Hi = Border2%
          StackPtr% = StackPtr% + 1
        END IF
        Low% = Border1%
      END IF

    'Perhaps do your screen updates here?

    LOOP WHILE Low% < Hi%
    'IF StackPtr% > MaxStackPtr% THEN MaxStackPtr% = StackPtr%

  LOOP WHILE StackPtr% <> 1

  'PRINT "MAX StackPtr%"; MaxStackPtr%


'-------------------------- END CODE ---------------------------

 * SLMR 2.1a * Dyslexics of the world, untie!
--- GEcho 1.00+
 * Origin: The Disk Box ][ Node 3 (313)790-6828 ZOOM 14.4K (1:2202/11)
Outer Court
Echo Basic Postings

Books at Amazon:

Back to BASIC: The History, Corruption, and Future of the Language

Hackers: Heroes of the Computer Revolution (including Tiny BASIC)

Go to: The Story of the Math Majors, Bridge Players, Engineers, Chess Wizards, Scientists and Iconoclasts who were the Hero Programmers of the Software Revolution

The Advent of the Algorithm: The Idea that Rules the World

Moths in the Machine: The Power and Perils of Programming

Mastering Visual Basic .NET