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(n^{2}) 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; } }3 Comments »
Leave a Reply

Archives
 May 2008 (1)
 February 2008 (3)
 January 2008 (6)

Categories

RSS
Entries RSS
Comments RSS
what will be the complexity of this program?
Comment by anum  December 5, 2010 
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 
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/fastsorts.html
Comment by Louis Dartez  November 10, 2011 