Introduction to Algorithms - The Reading Notes: Part 7, The Quick Sort

Now comes our famous QuickSort. It's famous because it's quick, so how quick it is? The answer from the theoretical analysis is Θ(n ln n) in average. OK, you may argue that the MergeSort and HeapSort we talked before also run in O(n ln n) , why this one is quicker? The answer is hidden in the big O notation, we usually don't write the constant factor in the function. In fact, QuickSort has a smaller hidden factor than others which distinguishes in practice QuickSort from the others. However, QuickSort can run, in the worst case, in O(n²) time. Now let's see how to write some code to do QuickSort.

As a starting point, we write our unit tests. As usual, we only need to add test cases in SortingTest.h and implement them in SortingTest.cpp.

    CPPUNIT_TEST( testQuickSort_0 );
    CPPUNIT_TEST( testQuickSort_1 );
    CPPUNIT_TEST( testQuickSort_Dec_0 );
    CPPUNIT_TEST( testQuickSort_Dec_1 );
...
    void testQuickSort_0();
    void testQuickSort_1();
    void testQuickSort_Dec_0();
    void testQuickSort_Dec_1();

The implementation of the tests which is quite straightforward, actually, same as tests for other sorting algorithms except the method used to sort, here we use QuickSort::Sort(v):

    // Setup Array.
...
    QuickSort::Sort(v);
...
    // Test Assertions.

Now if we try to compile, we will get some compiling errors, of course. We do not have our QuickSort class created. So now it's the time to create it.

    class QuickSort 
    {
        public:
            static void Sort(std::vector &v, bool bNonDecreasing = true);
        protected:
            static int  Partition(std::vector &v, int p, int r, bool bNonDecreasing);
            static void DoSort(std::vector &v, int p, int r, bool bNonDecreasing);
    };

The QuickSort provides exactly the same interface as other sorting algorithms which is the Sort method. As usual, we allow to sort in both non-decreasing and decreasing orders.

The DoSort method will recursively call itself to sort two sub-arrays partitioned by the method Partition.

Write the QuickSort class, compile it with scons, then run the unit tests. Failed!! Double check the code, then fix all the bugs until all unit tests pass. Below is the resulting code.

void QuickSort::Sort(std::vector &v, bool bNonDecreasing) 
{
    if (v.size() <= 1 )
    {
        return;
    }

    DoSort(v, 0, v.size()-1, bNonDecreasing);
}

int QuickSort::Partition(std::vector &v, int p, int r, bool bNonDecreasing)
{
    int pivot = v[r];
    int i = p-1; // i marks the end of the left partition.

    // j markes the end of the right partition
    for (int j = p; j <= r-1;  j++)
    {
        if ((v[j] < pivot &&  bNonDecreasing) ||
            (v[j] > pivot && !bNonDecreasing))
        {
            i++;
            int t = v[i];
            v[i]  = v[j];
            v[j]  = t;
        }
    }
    v[r] = v[i+1];
    v[i+1] = pivot;

    return i+1;
}

void QuickSort::DoSort(std::vector &v, int p, int r, bool bNonDecreasing)
{
    std::cout << "Sorting sub array: " << p << ":" << r << std::endl;
    if (p < r)
    {
        int q = Partition(v, p, r, bNonDecreasing);
        DoSort(v, p, q-1, bNonDecreasing);
        DoSort(v, q+1, r, bNonDecreasing);
    }
}

About this document ...

ITA Reading Notes This document was generated using the LaTeX2HTML translator Version 2008 (1.71)
Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -html_version 4.0,math -no_navigation -scalable_fonts -split 0 -no_auto_link ITAReadingNotes-Main
The translation was initiated by Bing Han on 2011-11-25