How to get progress percentage in quicksort?

[stephenc]

I would like to indicate the progress of my quicksort. I understand that, per
iteration, progress can be calculated by using something like this:

myRange = iUpper - iLower + 1
Progress = Round((myRange * Log(myRange))/3) + (myRange/3)

....but I can't get any sensible values from it, I am sure I am missing
something major, and I confess my mathematical abilities are not up to the
task.

Can anyone help me to understand what I should be doing?

My quicksort takes a public 2 dimensional (x,y) array and sorts just on the
y part. The array is called FA, and varies in size, but here is how to call
my code assuming FA has 1000 records (0-999):

Call QuickSortFA(0, 999)

Here is my quicksort code:

Public Sub QuickSortFA(Optional iLower As Integer, Optional iUpper As Integer)
Dim iLowerValue As Integer
Dim iUpperValue As Integer
Dim vTest As String
Dim iMidValue As Integer
Dim vTemp As Variant
If iLower < iUpper Then
iMidValue = Int((iLower + iUpper) / 2)
vTest = LCase(FA(1, iMidValue))
iLowerValue = iLower
iUpperValue = iUpper
Do
Do While LCase(FA(1, iLowerValue)) < vTest
iLowerValue = iLowerValue + 1
Loop
Do While LCase(FA(1, iUpperValue)) > vTest
iUpperValue = iUpperValue - 1
Loop
If iLowerValue <= iUpperValue Then
vTemp = FA(0, iUpperValue)
FA(0, iUpperValue) = FA(0, iLowerValue)
FA(0, iLowerValue) = vTemp
vTemp = FA(1, iUpperValue)
FA(1, iUpperValue) = FA(1, iLowerValue)
FA(1, iLowerValue) = vTemp
iLowerValue = iLowerValue + 1
iUpperValue = iUpperValue - 1
End If
Loop Until iLowerValue > iUpperValue
If iUpperValue <= iMidValue Then
Call QuickSortFA(iLower, iUpperValue)
Call QuickSortFA(iLowerValue, iUpper)
Else
Call QuickSortFA(iLowerValue, iUpper)
Call QuickSortFA(iLower, iUpperValue)
End If
End If
End Sub

 

[Helmut Weber]

Hi Stephen,

I confess my mathematical abilities are not up to the task.

Neither are mine, by no means. But as far as I understand this,
you can't know how many steps sorting will need, before you did it.

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm


Greetings from Bavaria, Germany

Helmut Weber

Win XP, Office 2003
"red.sys" & Chr$(64) & "t-online.de"

 

[stephenc]

Hello Mr Weber, and thanks for replying. Certainly, it is difficult to
calculate because at the start we do not know how much work is required to
sort the data, but then I found a quicksort sub (in VBS) which includes
progress percentage (written by Loren Eslinger at the Win32Scripting website):

http://cwashington.netreach.net/depo/view.asp?Index=1016&ScriptType=vbscript

I have figured out roughly how it does it, but my attempts to extract the
progress-related code and apply it to my software have failed.

Can you see how it works?

 

[Jay Freedman]

Hi Stephen,

How it works is "approximately". <g>

One of the major concepts in the mathematical study of sorting is the
"order" of a sort method, which is the number of operations (typically, the
number of swaps of position) used for a completed sort as a function of the
number of items to be sorted.

The actual order for a particular input data set depends both on the method
used and the amount of disorder present in the data. The quicksort method
performs best with very random data, and quite poorly with data that is
already almost sorted (or almost in reverse order).

On average, though, the order of the sort is a logarithmic function.
Eslinger expressed it in his code as the variable lngBigO:

'In a QuickSort BigO=(n*Log(n))
'In pratical testing BigO appears to be BigO=((n*Log(n))/3) + (n/3)
If IsEmpty(lngBigO) Then
lngEls = hiBound - loBound + 1
lngBigO = Round((lngEls * Log(lngEls))/3) + (lngEls/3)
blnFirst = True
End If 'IsEmpty(lngBigO)

That is, lngBigO is the *expected* number of swaps for the given data. The
actual number required may be more or less than that, so the progress report
may not behave smoothly near the end of the run.

The other part of the progress mechanism is to count the number of swaps as
they happen, for which Eslinger uses the variable lngProgress. This is the
code at the beginning of the loop that does the swaps:

Do
If blnProgress Then
lngProgress = lngProgress + 1
End If 'blnProgress

Then the approximate percentage progress is reported just before the
recursive calls by

If Round((lngProgress/lngBigO),2) * 100 > lngPrevious Then
Wscript.Echo Cstr(Round((lngProgress/lngBigO),2) * 100) & "%"
lngPrevious = Round((lngProgress/lngBigO),2) * 100
End If 'Round((lngProgress/lngBigO),2) * 100 > intPrevious

Depending on how accurate the estimate of lngBigO is, the sort may finish
before the progress percentage reaches 100%, or it may go on to 200% or
more.

 

[Howard Kaikow]

Hello Mr Weber, and thanks for replying. Certainly, it is difficult to
calculate because at the start we do not know how much work is required to
sort the data, but then I found a quicksort sub (in VBS) which includes
progress percentage (written by Loren Eslinger at the Win32Scripting

website):

In general, for quicksort, you cannot rely on a progress meter.
quicksort depends very much on the type of data, the range of values, the
particular quicksort algorithm, AND the method of implementing the
algorithm.

See http://www.standards.com/index.html?Sorting

 

[stephenc]

Thanks very much Jay for looking into how the code works, and for explaining
it so completely. I've learned a good deal from it.

I had guessed that Eslinger was doing some kind of estimation, but could not
see exactly how she was doing it, or how accurate/inaccurate it was. I'm now
having a go at including the calculations in my code.

(Sorry I did not reply sooner but I was on vacation for a week.)

Thanks again.
Stephenc

 

[stephenc]

Oops! forgot my manners. Thanks for helping out, Howard. Much appreciated.
I have now got a percentage calc/estimate working.
Stephenc