Monday, March 16, 2009

More IList Extension Methods: Quickselect-ing from an Unsorted List

Continuing my extension method kick and inspired by my extension method to select an item from an unsorted list that bets fits comparison criteria, I decided I wanted to try to implement an extension method to select from the list the kth best fit rather than just the best fit.

I left the best fit methods intact because they achieve worst case O(n) time, but the kth select worst case is O(n log n) because the worst case would quicksort the entire array. I later discovered that the method I implemented is called a quickselect. It's a divide an conquer algorithm based on the partitioning scheme of the quicksort.

Basically, with the quicksort, you pick an item (called the pivot) from the list and then put everything smaller than the pivot on the left and everything larger on the right. Then, you recursively quicksort each side of the pivot.

The quickselect uses the same technique, but rather than quicksorting both sides of the pivot, you quicksort only the side which contains the element you're looking for. Id est, if your pivot ends up at index 5 and you're looking for index 7, then you partition the right side. If the next pivot is index 8, then you partition the left side. You keep doing that until your pivot ends up being the index you're looking for.

Here's what the partition methods look like. There's really not a great reason to make them public, but there's also not a good reason to leave them private.
`public static int Partition<T>    (this IList<T> list, Comparison<T> comparison, int left, int right){    int i = left;    int j = right;    // pick the pivot point and save it    T pivot = list[left];    // until the indices cross    while (i < j)    {        // move the right pointer left until value < pivot        while (comparison(list[j], pivot) > 0 && i < j) j--;        // move the right value to the left position        // increment left pointer        if (i != j) list[i++] = list[j];        // move the left pointer to the right until value > pivot        while (comparison(list[i], pivot) < 0 && i < j) i++;        // move the left value to the right position        // decrement right pointer        if (i != j) list[j--] = list[i];    }    // put the pivot holder in the left spot    list[i] = pivot;    // return pivot location    return i;}public static int Partition<T>(this IList<T> list, Comparison<T> comparison){    return list.Partition(comparison, 0, list.Count - 1);}public static int Partition<T>(this IList<T> list, IComparer<T> comparer){    return list.Partition(new Comparison<T>((x, y) => comparer.Compare(x, y)));}public static int Partition<T>(this IList<T> list)    where T : IComparable<T>{    return list.Partition(new Comparison<T>((x, y) => x.CompareTo(y)));}`
Isolating the partition logic makes it really easy to implement both the quicksort logic and the quickselect logic. In fact, in case you're interested, here's what the quicksort logic looks like:
`public static void QuickSort<T>    (this IList<T> list, Comparison<T> comparison, int left, int right){    // pivot and get pivot location    int pivot = list.Partition(comparison, left, right);    // if the left index is less than the pivot, sort left side    if (left < pivot) list.QuickSort(comparison, left, pivot - 1);    // if right index is greated than pivot, sort right side    if (right > pivot) list.QuickSort(comparison, pivot + 1, right);}`
The quickselect is basically the same thing, except that you don't quicksort both sides of pivot:
`public static T QuickSelect<T>    (this IList<T> list, int k, Comparison<T> comparison, int left, int right){    // get pivot position    int pivot = list.Partition(comparison, left, right);    // if pivot is less that k, select from the right part    if (pivot < k) return list.QuickSelect(k, comparison, pivot + 1, right);    // if pivot is greater than k, select from the left side    else if (pivot > k) return list.QuickSelect(k, comparison, left, pivot - 1);    // if equal, return the value    else return list[pivot];}public static T QuickSelect<T>(this IList<T> list, int k, Comparison<T> comparison){    return list.QuickSelect(k, comparison, 0, list.Count - 1);}public static T QuickSelect<T>(this IList<T> list, int k, IComparer<T> comparer){    return list.QuickSelect(k, new Comparison<T>((x, y) => comparer.Compare(x, y)));}public static T QuickSelect<T>(this IList<T> list, int k)    where T : IComparable<T>{    return list.QuickSelect(k, new Comparison<T>((x, y) => x.CompareTo(y)));}`