Q46850: Increasing the Efficiency of QuickBASIC 4.50’s QuickSort Demo
Article: Q46850 Product(s): See article Version(s): 4.50 Operating System(s): MS-DOS Keyword(s): ENDUSER | SR# S890628-48 | mspl13_basic Last Modified: 12-JAN-1990 The SORTDEMO.BAS QuickSort program's speed can be increased by moving in toward the pivot point after each iteration. The speed increase is more noticeable as the array gets larger. This information applies to the SORTDEMO.BAS sample program provided with Microsoft QuickBASIC Version 4.50 for MS-DOS. In the QuickSort SUBprogram, you must move the "end elements", "I" and "J", inward after each iteration of the pivot loop. Currently, "I" and "J" are reset after after each loop iteration back to their initial values. The following is a portion of the QuickSort SUBprogram outlining the change that can be made. The code currently reads as follows: . . . 'Pick a pivot element at random. Then move it to the end. RandIndex = RandInt%(Low,High) SWAP SortArray(High),SortArray(RandIndex) Swapvars High, RandIndex Partition = SortArray(High),Length DO '***** THE NEXT TWO LINES ARE THE ONES ***** '***** THAT YOU WILL BE MOVING UPWARDS ***** 'Move in from both sides toward the pivot element I = Low: J = High DO WHILE (I<J) AND SortArray(I).Length <= Partition The code should read as follows: . . . 'Pick a pivot element at random. Then move it to the end. RandIndex = RandInt%(Low,High) SWAP SortArray(High),SortArray(RandIndex) Swapvars High, RandIndex Partition = SortArray(High),Length '***** THE FOLLOWING TWO LINES HAVE BEEN MOVED UPWARDS ***** 'Move in from both sides toward the pivot element I= Low: J = High DO DO WHILE (I < J) AND SortArray(I).Length <= Partition
THE INFORMATION PROVIDED IN THE MICROSOFT KNOWLEDGE BASE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND. MICROSOFT DISCLAIMS ALL WARRANTIES, EITHER EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL MICROSOFT CORPORATION OR ITS SUPPLIERS BE LIABLE FOR ANY DAMAGES WHATSOEVER INCLUDING DIRECT, INDIRECT, INCIDENTAL, CONSEQUENTIAL, LOSS OF BUSINESS PROFITS OR SPECIAL DAMAGES, EVEN IF MICROSOFT CORPORATION OR ITS SUPPLIERS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. SOME STATES DO NOT ALLOW THE EXCLUSION OR LIMITATION OF LIABILITY FOR CONSEQUENTIAL OR INCIDENTAL DAMAGES SO THE FOREGOING LIMITATION MAY NOT APPLY.
Copyright Microsoft Corporation 1986-2002.