Adaptive Sort

Quicksort

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(nlogn) 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 probability of requiring quadratic time.

Quicksort in action

Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.

The steps are:

  1. Pick an element, called a pivot, from the list.
  2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

 

The base case of the recursion are lists of size zero or one, which are always sorted.

For a more complete description, see the entry about Quicksort in Wikipedia (text and picture are borrowed from that site).

Source Code

An efficient implementation in C#.NET

In order to compare ASort to well known algorithms, I implemented an efficient version of Quicksort in C#.NET. You can see how this implementation compares to merge sort and ASort on the performance page.

Below is the C#.NET source code. Feel free to use it for whatever purpose you like (cut-and-paste or use this link to get source code).

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace QuickSort

{

    public class QuickSort<myType>

    {

        // Main method

        public void Sort(myType[] arr, Comparison<myType> comp)

        {

            quicksort(arr, 0, arr.Length - 1, comp);

        }

 

        // Recursive method

        void quicksort(myType[] a, int l, int r, Comparison<myType> comp)

        {

            // Use insertion sort at the end

            if (1 + r - l <= 10)

            {

                if (r > l)

                    InsertionSort(a, l, r, comp);

                return;

            }

 

            int i = l - 1, j = r;

            int pivoIndex = BestOf3Median(a, l, r, comp);

            myType v = a[pivoIndex], tmp;

 

            // Move pivo to back

            tmp = a[pivoIndex];

            a[pivoIndex] = a[r];

            a[r] = tmp;

 

            for (; ; )

            {

                while (comp(a[++i], v) == -1)

                    ;

                if (i >= j)

                    break;

                while (comp(v, a[--j]) == -1)

                    ;

                if (i >= j)

                    break;

                tmp = a[i];

                a[i] = a[j];

                a[j] = tmp;

            }

            tmp = a[i];

            a[i] = a[r];

            a[r] = tmp;

            quicksort(a, l, i - 1, comp);

            quicksort(a, i + 1, r, comp);

        }

 

        // Insertion sort which is fast for smaller lists

        public void InsertionSort(myType[] arr, int left, int right, Comparison<myType> comp)

        {

            int i, o;

            //  sorted on left of out

            for (o = left + 1; o <= right; o++)

            {

                myType temp = arr[o]; // remove marked item

                i = o; // start shifts at out

                // until one is smaller,

                while (i > left && comp(arr[i - 1], temp) != -1)

                {

                    arr[i] = arr[i - 1]; // shift item to right

                    --i; // go left one position

                }

                arr[i] = temp; // insert marked item

            }

        }

 

        // Select a good pivot

        // This one is better than the more common:

        //   if (a[l]>a[i]) swap(a,l,i); 

        //   if (a[l]>a[r]) swap(a,l,r);

        //   if (a[i]>a[r]) swap(a,i,r);

        private int BestOf3Median(myType[] arr, int lo, int hi, Comparison<myType> comp)

        {

            if (hi - lo < 10)

                return (hi + lo) / 2;  // just use middle if list is short

 

            int midLow = (int)((hi - lo) * 0.25) + lo;

            int mid = (int)((lo + hi) * 0.5);

            int midHigh = (int)((hi - lo) * 0.75) + lo;

 

            // Get middle value of 3 values as pivot

            if (comp(arr[midLow], arr[mid]) == -1) // x1 < x2   

            {

                if (comp(arr[mid], arr[midHigh]) != 1)  // x1 < x2 < x3

                    return mid;

                else

                    if (comp(arr[midLow], arr[midHigh]) == -1)  // x1 < x3 < x2

                        return midHigh;

                    else

                        return midLow;

            }

            else // x1 > x2

            {

                if (comp(arr[midLow], arr[midHigh]) != 1)  // x3 > x1 > x2

                    return midLow;

                else

                    if (comp(arr[mid], arr[midHigh]) == -1)  // x1 > x3 > x2

                        return midHigh;

                    else

                        return mid;

            }

        }

    }

}