Qsort  by van emden, good references on how it works

Posted on 2003-03-20
Medium Priority
Last Modified: 2010-04-17
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
Question by:skeid21
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions

Expert Comment

ID: 8179165
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
        While m < sList(j) And i <= j
        j = j - 1
        If i <= j Then
            sWork = sList(j)
            sList(j) = sList(i)
            sList(i) = sWork
            i = i + 1
            j = j - 1
        End If
    If (i < R) Then QSort sList, i, R
    If (j > L) Then QSort sList, L, j
End Sub

Expert Comment

ID: 8206280

Accepted Solution

skeid21 earned 0 total points
ID: 8229183
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

Expert Comment

ID: 9446935
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 
Post your closing recommendations!  No comment means you don't care.

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
Q&A with Course Creator, Mark Lassoff, on the importance of HTML5 in the career of a modern-day developer.
Simple Linear Regression
Suggested Courses
Course of the Month7 days, 21 hours left to enroll

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question