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

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
Asked:
skeid21
1 Solution
 
xassetsCommented:
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
 
sktripuraneniCommented:
0
 
skeid21Author 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
 
CleanupPingCommented:
skeid21:
This old question needs to be finalized -- accept an answer, split points, or get a refund.  For information on your options, please click here-> http:/help/closing.jsp#1 
EXPERTS:
Post your closing recommendations!  No comment means you don't care.
0

Featured Post

Become an Android App Developer

Ready to kick start your career in 2018? Learn how to build an Android app in January’s Course of the Month and open the door to new opportunities.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now