# Qsort 1/2

``` BBS: Inland Empire Archive
Date: 03-22-93 (23:08)             Number: 291
From: TOM HAMMOND                  Refer#: NONE
To: RICH TIETJENS                 Recvd: NO
Subj: Qsort                 1/2      Conf: (2) Quik_Bas```
```RT>Does anyone have a "canned" quicksort routine I can look at?  I hate
reinventing the wheel..

Maybe this'll help ya out:

'===========================================================================
'Date: 11-07-92 (13:59)             Number: 5280
'From: ZACK JONES                   Refer#: 4772
'Subj: Fast Sorting Algorithm.        Conf: (5) Quickbasic
'
'QuickSort2 - QuickSort iterative (rather than recursive) by Cornel Huth.

DEFINT A-Z
DECLARE SUB Fastsorti (inarray%(), lower%, upper%)
DECLARE SUB QuickSort2 (sortarray%(), lower%, upper%)

TYPE stacktype 'for QuickSort2
low AS INTEGER
hi AS INTEGER
END TYPE
CLS
FOR a = 1 TO 12
count = 2 ^ a
REDIM temp(1 TO count) AS INTEGER
' Generate a random array to test the sort.

RANDOMIZE a
FOR b = 1 TO count
temp(b) = RND * 32766 + 1
NEXT b

s1# = TIMER
DO
start# = TIMER 'Wait for the beginning of a clock cycle.
LOOP WHILE s1# = start#
Fastsorti temp(), 1, count
e1# = TIMER

'Make the original arrays identical (no cheating! ;^)

RANDOMIZE a
FOR b = 1 TO count
temp(b) = RND * 32766 + 1
NEXT b

s2# = TIMER
DO
start# = TIMER
LOOP WHILE s2# = start#
QuickSort2 temp(), 1, count
e2# = TIMER

' A test to make sure it sorted it correctly.
'
'FOR chk = 1 TO Count
'  PRINT Temp(chk);
'NEXT chk
'PRINT

PRINT "FastSort: took"; e1# - s1#;
PRINT TAB(30); "seconds to sort"; count; "entries."
PRINT "MiscSort: took"; e2# - s2#;
PRINT TAB(30); "seconds to sort"; count; "entries."
NEXT a

SUB Fastsorti (inarray%(), lower%, upper%)

' This routine was writen by Ryan Wellman.
' Released as Freeware October 22, 1992.
' You may freely use, copy & modify this code as you see
' fit. Under the condition that I am given credit for
' the original sort routine, and partial credit for modified
' versions of the routine.

' Thanks to Richard Vannoy who gave me the idea to compare
' entries further than 1 entry away.

increment = (upper + lower)
l2 = lower - 1

DO
increment = increment \ 2
i2 = increment + l2
FOR index = lower TO upper - increment
IF inarray(index) > inarray(index + increment) THEN
SWAP inarray(index), inarray(index + increment)
IF index > i2 THEN
cutpoint = index
stopnow = 0
DO
index = index - increment
IF inarray(index) > inarray(index + increment) THEN
SWAP inarray(index), inarray(index + increment)
ELSE
stopnow = -1
index = cutpoint
END IF
LOOP UNTIL stopnow
END IF
END IF
NEXT index
LOOP UNTIL increment <= 1
END SUB

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
>>> Continued to next message
---
* Origin: Night Shift BBS (314)635-7588 HST 14.4 (1:289/15)
```

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