• Status: Solved
• Priority: Medium
• Security: Public
• Views: 264

# Qsort by van emden, good references on how it works

I was rescently presented with a paper describing qsort in pascal. First, Pascal is very confusing to me second the code has no comments.  I am to interpret this paper, write the code, find a running time, and compare it to a traditional quicksort.  If anyone knows of any good references on the web that would better help me to understand qsort then this jumble of code that i have please post, and I will continue to look. Thanks all
0
skeid21
1 Solution

Commented:
This is a bog standard VB qsort which sorts a string array. Equally uncommented and probably of no use at all to you!

Public Sub QSortArray(sList() As String)

QSort sList, 0, UBound(sList)

End Sub

Private Sub QSort(sList() As String, L As Long, R As Long)
Dim i As Long
Dim j As Long
Dim m As String
Dim sWork As String
m = sList((L + R) / 2)
i = L
j = R
While i <= j
While sList(i) < m And i <= j
i = i + 1
Wend
While m < sList(j) And i <= j
j = j - 1
Wend
If i <= j Then
sWork = sList(j)
sList(j) = sList(i)
sList(i) = sWork
i = i + 1
j = j - 1
End If
Wend
If (i < R) Then QSort sList, i, R
If (j > L) Then QSort sList, L, j
End Sub
0

Commented:
0

Author Commented:
Thanks for your help guys, but i ended up staying up all night and figureing out qsort for myself.

works very similer to quicksort, but when the partition is made insted of there being one pivot value which that everything above is greater and below is less, It has two radix wich are sorted among themselves and everything above them is greater, below them is less.  This is acomplished by how the comparison are made the end be effectivly have these two pivots in their position like quicksort.  So effectively it can sort n elemants in about half the time.
sor worst case (1/2n)^2, average (1/2n)log(base 2)(1/2n).  That was my best guess on how this algorithm by van Emden incresses the running times.
again thanks for the effert guys
0

Commented:
skeid21: