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