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;
    }
}

January 28, 2008 Posted by | Algorithms | 3 Comments