# Re: Help!! (for someone e

``` BBS: Inland Empire Archive
Date: 03-04-93 (16:29)             Number: 313
From: VICTOR YIU                   Refer#: NONE
To: CASEY PEARSON                 Recvd: NO
Subj: Re: Help!! (for someone e      Conf: (2) Quik_Bas```
``` >>> Regurgitating CASEY PEARSON to ALL <<<

CP> am trying to implement the Quick Sort algorithm so I can test out how

Here's the fastest QuickSort I have seen (non-recursive).  It has already
been posted in this echo several times in the past 6 months....

-----------------snip here
DEFINT A-Z

DECLARE SUB Quicksort2 (sortarray%(), lower%, Upper%)
DECLARE FUNCTION RandInt% (lower%, Upper%)

TYPE stacktype 'for QuickSort2
Low AS INTEGER
hi AS INTEGER
END TYPE

COMMON SHARED Temp() AS INTEGER

'Quicksort2 Temp(), 1, count

SUB Quicksort2 (sortarray(), lower%, Upper%)

'QuickSort iterative (rather than recursive) by Cornel Huth
DIM lstack(1 TO 128) AS stacktype 'our stack
DIM sp AS INTEGER 'out stack pointer
sp = 1
'maxsp = sp
lstack(sp).Low = lower%
lstack(sp).hi = Upper%
sp = sp + 1
DO
sp = sp - 1
Low = lstack(sp).Low
hi = lstack(sp).hi
DO
I = Low
J = hi
mid = (Low + hi) \ 2
compare = sortarray(mid)
DO
DO WHILE sortarray(I) < compare
I = I + 1
LOOP
DO WHILE sortarray(J) > compare
J = J - 1
LOOP
IF I <= J THEN
SWAP sortarray(I), sortarray(J)
I = I + 1
J = J - 1
END IF
LOOP WHILE I <= J
IF J - Low < hi - I THEN
IF I < hi THEN
lstack(sp).Low = I
lstack(sp).hi = hi
sp = sp + 1
END IF
hi = J
ELSE
IF Low < J THEN
lstack(sp).Low = Low
lstack(sp).hi = J
sp = sp + 1
END IF
Low = I
END IF
LOOP WHILE Low < hi
'IF sp > maxsp THEN maxsp = sp
LOOP WHILE sp <> 1
'PRINT "MAX SP"; maxsp
END SUB

FUNCTION RandInt% (lower, Upper) STATIC

RandInt% = INT(RND * (Upper - lower + 1)) + lower

END FUNCTION
------------------ end

Victor

... Rhesus Pieces: Monkey in a blender.
--- Blue Wave/RA v2.10 [NR]
* Origin: Hard Disc Cafe / Houston Texas / (713) 589-2690 / (1:106/30.0)
```

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