Coding Notes

Ideas and thoughts from Seth Long

Quicksort / Insertion Sort Combo

My blog is now located at http://www.WhoIsSethLong.com

The Quicksort is one of the fastest sorting algorithms for sorting large lists of data.  The Insertion sort is a fast sorting algorithms for sorting very small lists that are already somewhat sorted.  We combine these two algorithms to come up with a very simple and effective method for sorting large lists.

We start our sort by using a Quicksort.  The Quicksort on average runs in O(n log(n)) time but can be as slow as O(n2) if we try to sort a list that is already sorted and use the left most element as our pivot.  If you are unfamiliar with the quicksort here is a Wikipedia article describing the algorithm: http://en.wikipedia.org/wiki/Quicksort

As the Quicksort works, it breaks down our list into smaller and smaller lists.  Once the lists become small enough that an Insertion sort becomes more efficient then the Quicksort we will switch to the Insertion sort to finish off the job.  Think of it as grinding away with the Quicksort then polishing it off with the Insertion sort once most of the work has been done.

Here is a code sample of a combined Quicksort and Insertion sort algorithm in C#.

class Quicksort
{
    public void Sort(int[] list, int start, int end)
    {
        if (start < end)
        {
            // This is where we switch to Insertion Sort!
            if ((end – start) < 9)
            {
                this.InsertionSort(list, start, end + 1);
            }
            else
            {
                int part = this.partition(list, start, end);
                this.Sort(list, start, part – 1);
                this.Sort(list, part + 1, end);
            }
        }
    }
    public void InsertionSort(int[] list, int start, int end)
    {
        for (int x = start + 1; x < end; x++)
        {
            int val = list[x];
            int j = x – 1;
            while (j >= 0 && val < list[j])
            {
                list[j + 1] = list[j];
                j–;
            }
            list[j + 1] = val;
        }
    }
    private int partition(int[] list, int leftIndex, int rightIndex)
    {
        int left = leftIndex;
        int right = rightIndex;
        int pivot = list[leftIndex];
        while (left < right)
        {
            if (list[left] < pivot)
            {
                left++;
                continue;
            }
            if (list[right] > pivot)
            {
                right–;
                continue;
            }
            int tmp = list[left];
            list[left] = list[right];
            list[right] = tmp;
            left++;
        }
        return left;
    }
}
Advertisements

January 28, 2008 - Posted by | Algorithms

3 Comments »

  1. what will be the complexity of this program?

    Comment by anum | December 5, 2010 | Reply

  2. Hey Seth,
    I was wondering – how did you decide on the following condition: ((end – start) < 9)
    I mean – how do you decide that the array is small enough and that the insertion sort function should kick in action?

    thanks,
    Jim

    Comment by Jim | May 18, 2011 | Reply

  3. Hello Jim,

    for hybrid programs such as this, studies have shown that the threshold point for when the running time is significantly better in insertion sort than that of quicksort is around 9.

    http://www.cs.wcupa.edu/~rkline/DS/fast-sorts.html

    Comment by Louis Dartez | November 10, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: