QB / QB64 Discussion Forum      Other Subforums, Links and Downloads
 

 Return to Index  

QuickSort with display

April 22 2006 at 6:32 PM
Solitaire  (Login Solitaire1)
R


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 AM


 
 Respond to this message   
Responses

 Copyright © 1999-2014 Network54. All rights reserved.   Terms of Use   Privacy Statement  

Newbies usually go to www.qbasic.com and click on The QBasic Forum
Forum regulars have their own ways, which include The QBasic Community Forums