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>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:
(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)));
}
public static void QuickSort<T>The quickselect is basically the same thing, except that you don't quicksort both sides of pivot:
(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);
}
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)));
}
