# QuickSort with display

April 22 2006 at 6:32 PM
S

Response to Five (5) sorts comparison program

I used the working QuickSort algorithm from the above post and dressed it up. First the program assigns random values to an array which the user sizes, and displays the random values. If the array size is greater than 112, the user must press another key to continue the display so that it won't scroll out of sight. If the array size is 112 or less, the user is then given the option to monitor the QuickSort progress by pressing the M key with each recursive call to the sub. Any other key continues to the display of the completed sort. I also included a validation routine suggested by Mac which prints "Sorted OK" if there were no errors. In case a value happens to be out of order, it will print the array index and the value (but it never will because the algorithm works correctly every time).

DECLARE SUB QuickSort (intArray() AS INTEGER, start AS INTEGER, finish AS INTEGER, E AS STRING)
DECLARE SUB PrintArray (intArray() AS INTEGER, finish AS INTEGER, show AS INTEGER)
DIM start AS INTEGER, finish AS INTEGER, x AS INTEGER
DIM range AS LONG, bug AS INTEGER, E AS STRING
DIM SHARED count AS INTEGER
RANDOMIZE TIMER
CLS : INPUT ; "Enter size of array:  ", size\$
finish = INT(VAL(size\$))
IF finish > 32767 THEN finish = 32767
IF finish < 1 THEN finish = 19
DIM intArray(1 TO finish) AS INTEGER
start = 1
range = finish * 4
FOR x = 1 TO finish
intArray(x) = INT(RND * range) + 1
NEXT x
IF finish <= 112 THEN PRINT : PRINT
CALL PrintArray(intArray(), finish, 0)
PRINT "Press any key to display sorted array...";
IF finish <= 112 THEN PRINT "or M to monitor the Quicksort display...";
E\$ = INPUT\$(1)
IF finish <= 112 THEN PRINT : PRINT
CALL QuickSort(intArray(), start, finish, E\$)
CALL PrintArray(intArray(), finish, 2)
bug = 0
FOR x = 1 TO finish - 1     'validate correct sort
IF intArray(x) > intArray(x + 1) THEN
PRINT "Bug at "; x, intArray(x)
bug = 1
END IF
NEXT x
IF bug = 0 THEN PRINT "Sorted OK"; TAB(15); "Number of iterations:  "; count
END

SUB PrintArray (intArray() AS INTEGER, finish AS INTEGER, show AS INTEGER)
DIM x AS INTEGER, num AS INTEGER, U AS INTEGER, E AS STRING
IF finish > 112 THEN PRINT SPC(5); "Press any key to continue...": PRINT
num = 0
U = UBOUND(intArray)
FOR x = 1 TO finish 'UBOUND(intArray)
num = num + 1
IF show = 1 THEN COLOR 0, 7
IF show = 2 THEN COLOR 14, 0
PRINT intArray(x);
NEXT x
FOR x = finish + 1 TO U
IF intArray(x - 1) > intArray(x) THEN
COLOR 11, 0
ELSE
COLOR 7, 0
END IF
PRINT intArray(x);
IF num MOD 112 = 0 THEN E\$ = INPUT\$(1)
NEXT x
COLOR 7, 0
IF num = finish THEN
PRINT
PRINT STRING\$(80, "_")
PRINT
ELSE
E\$ = INPUT\$(1)
END IF
END SUB

SUB QuickSort (intArray() AS INTEGER, start AS INTEGER, finish AS INTEGER, E AS STRING)
DIM top AS INTEGER, bottom AS INTEGER, compare AS INTEGER
' ============================================================================
'  QuickSort works by picking a random pivot element ("compare") in intArray,
'  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 all the
'  elements have been moved, the array is sorted and the recursive calls end.
' ============================================================================
bottom = start
top = finish
compare = intArray((bottom + top) \ 2)
count = count + 1
DO
DO WHILE intArray(bottom) < compare
bottom = bottom + 1
LOOP
DO WHILE intArray(top) > compare
top = top - 1
LOOP
IF bottom <= top THEN
SWAP intArray(bottom), intArray(top)
bottom = bottom + 1
top = top - 1
END IF
LOOP UNTIL bottom > top
IF top > start THEN CALL QuickSort(intArray(), start, top, E\$)
IF bottom < finish THEN CALL QuickSort(intArray(), bottom, finish, E\$)
IF UCASE\$(E\$) = "M" THEN
CALL PrintArray(intArray(), finish, 1)
E\$ = INPUT\$(1)
END IF
END SUB

 This message has been edited by Solitaire1 on Apr 25, 2006 10:11 AMThis message has been edited by Solitaire1 on Apr 24, 2006 6:59 PMThis message has been edited by Solitaire1 on Apr 24, 2006 6:26 PMThis message has been edited by Solitaire1 on Apr 24, 2006 5:45 PMThis message has been edited by Solitaire1 on Apr 22, 2006 6:45 PM

 Respond to this message
Responses