QuickSort (2)

Sub Quicksort (List() As Long, min As Integer, max As Integer)
    Dim med_value As Long
    Dim hi As Integer
    Dim lo As Integer
    Dim i As Integer
    ' If the list has no more than 1 element, it's sorted.
    If min >= max Then Exit Sub
    ' Pick a dividing item.
    i = Int((max - min + 1) * Rnd + min)
    med_value = List(i)
    ' Swap it to the front so we can find it easily.
    List(i) = List(min)
    ' Move the items smaller than this into the left
    ' half of the list. Move the others into the right.
    lo = min
    hi = max
    Do
    ' Look down from hi for a value < med_value.
    Do While List(hi) >= med_value
        hi = hi - 1
        If hi <= lo Then Exit Do
    Loop
    If hi <= lo Then
        List(lo) = med_value
        Exit Do
    End If
    ' Swap the lo and hi values.
    List(lo) = List(hi)
    
    ' Look up from lo for a value >= med_value.
    lo = lo + 1
    Do While List(lo) < med_value
        lo = lo + 1
        If lo >= hi Then Exit Do
    Loop
    If lo >= hi Then
        lo = hi
        List(hi) = med_value
        Exit Do
    End If
    ' Swap the lo and hi values.
    List(hi) = List(lo)
Loop
' Sort the two sublists
Quicksort List(), min, lo - 1
Quicksort List(), lo + 1, max
End Sub
 Quicksort is a recursive algorithm that uses a 
divide-and-conquer technique. While the list of items to be 
sorted contains at least two items, quicksort divides it into 
two sublists and recursively calls itself to sort the sublists.
The quicksort routine first checks to see if the list it is 
sorting contains fewer than two items. If so, it simply returns.
Otherwise the subroutine picks an item from the list to use as 
a dividing point. It then places all of the items that belong 
before this dividing point in the left part of the list. 
It places all of the other items in right part of the list. 
The subroutine then recursively calls itself to sort two 
smaller sublists.
There are several ways in which the quicksort routine might 
pick the dividing item. One of the easiest is to simply use 
the first item in the sublist being sorted. If the list is 
initially arranged randomly, that item will be a reasonable 
choice. Chances are good that the item will belong somewhere
in the middle of the list and the two sublists the algorithm
creates will be reasonably equal in size.
If the numbers are initially sorted or almost sorted, or if 
they are initially sorted in reverse order, then this method
fails miserably. In that case the first item in the list will
divide the list into one sublist that contains almost every 
item and another that will contain almost no items. 
Since the larger sublist does not shrink much, the algorithm
makes little headway. In this case the algorithm will require
on the order of N2 steps. This is the same order of 
performance given by selectionsort, only this algorithm is 
much more complicated.
A better method for selecting the dividing item is to choose
one randomly. Then no matter how the items in the list are 
arranged, chances are the item you select will belong near 
the middle of the list and the sublists will be fairly 
evenly sized.
As long as the sublists are fairly equal in size, the 
algorithm will require on the order of N * log(N) steps. 
It can be proven that this is the fastest time possible for 
a sorting algorithm that sorts using comparisons. By using a
little randomness, this algorithm avoids the possibility of 
its worst case N2 behavior and gives an expected case 
performance of N * log(N). Quicksort is very fast in 
practice as well as theory, so it is the favorite sorting 
algorithm of many programmers.
Listing 1 shows the VB code for the quicksort routine.

Sub Quicksort (List() As Long, min As Integer, max As Integer)
Dim med_value As Long
Dim hi As Integer
Dim lo As Integer
Dim i As Integer
' If the list has no more than 1 element, it's sorted.

If min >= max Then Exit Sub
' Pick a dividing item.

i = Int((max - min + 1) * Rnd + min)
med_value = List(i)
' Swap it to the front so we can find it easily.

List(i) = List(min)
' Move the items smaller than this into the left

' half of the list. Move the others into the right.

lo = min
hi = max
Do
' Look down from hi for a value < med_value.

Do While List(hi) >= med_value
hi = hi - 1
If hi <= lo Then Exit Do
Loop
If hi <= lo Then
List(lo) = med_value
Exit Do
End If
' Swap the lo and hi values.

List(lo) = List(hi)

' Look up from lo for a value >= med_value.

lo = lo + 1
Do While List(lo) < med_value
lo = lo + 1
If lo >= hi Then Exit Do
Loop
If lo >= hi Then
lo = hi
List(hi) = med_value
Exit Do
End If
' Swap the lo and hi values.

List(hi) = List(lo)
Loop
' Sort the two sublists

Quicksort List(), min, lo - 1
Quicksort List(), lo + 1, max
End Sub
Quicksort is a recursive algorithm that uses a
divide-and-conquer technique. While the list of items to be
sorted contains at least two items, quicksort divides it into
two sublists and recursively calls itself to sort the sublists.
The quicksort routine first checks to see if the list it is
sorting contains fewer than two items. If so, it simply returns.
Otherwise the subroutine picks an item from the list to use as
a dividing point. It then places all of the items that belong
before this dividing point in the left part of the list.
It places all of the other items in right part of the list.
The subroutine then recursively calls itself to sort two
smaller sublists.
There are several ways in which the quicksort routine might
pick the dividing item. One of the easiest is to simply use
the first item in the sublist being sorted. If the list is
initially arranged randomly, that item will be a reasonable
choice. Chances are good that the item will belong somewhere
in the middle of the list and the two sublists the algorithm
creates will be reasonably equal in size.
If the numbers are initially sorted or almost sorted, or if
they are initially sorted in reverse order, then this method
fails miserably. In that case the first item in the list will
divide the list into one sublist that contains almost every
item and another that will contain almost no items.
Since the larger sublist does not shrink much, the algorithm
makes little headway. In this case the algorithm will require
on the order of N2 steps. This is the same order of
performance given by selectionsort, only this algorithm is
much more complicated.
A better method for selecting the dividing item is to choose
one randomly. Then no matter how the items in the list are
arranged, chances are the item you select will belong near
the middle of the list and the sublists will be fairly
evenly sized.
As long as the sublists are fairly equal in size, the
algorithm will require on the order of N * log(N) steps.
It can be proven that this is the fastest time possible for
a sorting algorithm that sorts using comparisons. By using a
little randomness, this algorithm avoids the possibility of
its worst case N2 behavior and gives an expected case
performance of N * log(N). Quicksort is very fast in
practice as well as theory, so it is the favorite sorting
algorithm of many programmers.
Listing 1 shows the VB code for the quicksort routine.