Sorting Arrays – Quick Sort

Quicksort in action on a list of random numbers. The horizontal lines are pivot values.Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare
that, on average, makes (big O notation) comparisons to sort n items.

However, in the worst case, it makes L(n2) comparisons. Typically, quicksort is significantly faster in practice than other algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time. The quicksort algorithm was developed by Hoare in 1960 while working for the small British scientific computer manufacturer Elliott Brothers.

The quick sort is by far the fastest of the common sorting algorithms. It’s possible to write a special-purpose sorting algorithm that can beat the quick sort for some data sets, but for general-case sorting there isn’t anything faster.
As soon as students figure this out, their immediate impulse is to use the quick sort for everything – after all, faster is better, right? It’s important to resist this urge – the quick sort isn’t always the best choice. As mentioned earlier, it’s massively recursive (which means that for very large sorts, you can run the system out of stack space pretty easily). It’s also a complex algorithm – a little too complex to make it practical for a one-time sort of 25 items, for example.
With that said, in most cases the quick sort is the best choice if speed is important (and it almost always is). Use it for repetitive sorting, sorting of medium to large lists, and as a default choice when you’re not really sure which sorting algorithm to use. Ironically, the quick sort has horrible efficiency when operating on lists that are mostly sorted in either forward or reverse order – avoid it in those situations.

Public Sub QuickSortArray( ByRef arr(), ByVal nLow, ByVal nHigh )

    Dim pivot, tmpSwap, tmpLow, tmpHigh

    tmpLow = nLow

    tmpHigh = nHigh

    pivot = arr( ( nLow + nHigh ) / 2 )

    Do While tmpLow <= tmpHigh

        Do While( arr( tmpLow ) < pivot And tmpLow < nHigh )

            tmpLow = tmpLow + 1

        Loop

        Do While( pivot < arr( tmpHigh ) And tmpHigh > nLow )

            tmpHigh = tmpHigh – 1

        Loop

        If tmpLow <= tmpHigh Then

            tmpSwap = arr( tmpLow )

            arr( tmpLow ) = arr( tmpHigh )

            arr( tmpHigh ) = tmpSwap

            tmpLow = tmpLow + 1

            tmpHigh = tmpHigh – 1

        End If

    Loop

    If nLow < tmpHigh Then Call QuickSortArray( arr, nLow, tmpHigh )

    If tmpLow < nHigh Then Call QuickSortArray( arr, tmpLow, nHigh )

End Sub