Article ID: 46850
Article Last Modified on 11/21/2006
This article was previously published under Q46850
SUMMARY
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.
MORE INFORMATION
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:
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
Additional query words: QuickBas
Keywords: KB46850
