Skip to content

Instantly share code, notes, and snippets.

@sjmeverett

sjmeverett/ListQuickSelectExtensions.cs

Created July 23, 2013 00:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sjmeverett/6058812 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sjmeverett/6058812 to your computer and use it in GitHub Desktop.
Download ZIP
A handful of extension methods implementing the "quick select" algorithm for lists. This algorithm will find the k-th smallest value in a list in expected O(n) time, so long as it doesn't pick consistently bad pivots. This is useful for quickly finding the median of an unsorted list, among other things. The algorithm is based on the one described …
Raw
ListQuickSelectExtensions.cs
public static class ListQuickSelectExtensions
{
private static Random random = new Random();
/// <summary>
/// Swaps the values at the two indexes in the list.
/// </summary>
/// <typeparam name="T">The list element type.</typeparam>
/// <param name="xs">The list.</param>
/// <param name="a">The index of an element to swap.</param>
/// <param name="b">The index of the other element to swap.</param>
public static void Swap<T>(this IList<T> xs, int a, int b)
{
T t = xs[a];
xs[a] = xs[b];
xs[b] = t;
}
/// <summary>
/// Picks a random element (pivot) in the list and arranges the list such that all the elements
/// less than the pivot come before it in the list, and all the elements greater than the pivot come
/// after it.
/// </summary>
/// <typeparam name="T">The list element type.</typeparam>
/// <param name="xs">The list.</param>
/// <param name="start">The index of the start of the portion to partition.</param>
/// <param name="end">The index of the end of the portion to partition.</param>
/// <param name="comparer">The object to use to make comparisons between elements.</param>
/// <returns>The index of the pivot.</returns>
public static int Partition<T>(this IList<T> xs, int start, int end, IComparer<T> comparer)
{
int pivotIndex = random.Next(start, end);
T pivot = xs[pivotIndex];
xs.Swap(pivotIndex, end);
int storeIndex = start;
for (int i = start; i < end; i++)
{
if (comparer.Compare(xs[i], pivot) < 0)
{
xs.Swap(storeIndex, i);
storeIndex++;
}
}
xs.Swap(end, storeIndex);
return storeIndex;
}
/// <summary>
/// Picks a random element (pivot) in the list and arranges the list such that all the elements
/// less than the pivot come before it in the list, and all the elements greater than the pivot come
/// after it.
/// </summary>
/// <typeparam name="T">The list element type.</typeparam>
/// <param name="xs">The list.</param>
/// <param name="start">The index of the start of the portion to partition.</param>
/// <param name="end">The index of the end of the portion to partition.</param>
/// <returns>The index of the pivot.</returns>
public static int Partition<T>(this IList<T> xs, int start, int end)
{
return xs.Partition(start, end, Comparer<T>.Default);
}
/// <summary>
/// Gets the k-th largest element in the list, where k is zero based.
/// </summary>
/// <typeparam name="T">The list element type.</typeparam>
/// <param name="xs">The list.</param>
/// <param name="start">The index of the start of the portion to sort.</param>
/// <param name="end">The index of the end of the portion to sort.</param>
/// <param name="k">The index of the element in the sorted list whos value is sought.</param>
/// <param name="comparer">The object to use to make comparisons between elements.</param>
/// <returns>The value of the k-th largest element in the list.</returns>
public static T QuickSelect<T>(this IList<T> xs, int start, int end, int k, IComparer<T> comparer)
{
if (start == end)
return xs[start];
int pivotIndex = xs.Partition(start, end);
if (pivotIndex == k)
return xs[pivotIndex];
else if (k < pivotIndex)
return QuickSelect(xs, start, pivotIndex - 1, k, comparer);
else
return QuickSelect(xs, pivotIndex + 1, end, k, comparer);
}
/// <summary>
/// Gets the k-th largest element in the list, where k is zero based.
/// </summary>
/// <typeparam name="T">The list element type.</typeparam>
/// <param name="xs">The list.</param>
/// <param name="k">The index of the element in the sorted list whos value is sought.</param>
/// <param name="comparer">The object to use to make comparisons between elements.</param>
/// <returns>The value of the k-th largest element in the list.</returns>
public static T QuickSelect<T>(this IList<T> xs, int k, IComparer<T> comparer)
{
return xs.QuickSelect(0, xs.Count, k, comparer);
}
/// <summary>
/// Gets the k-th largest element in the list, where k is zero based.
/// </summary>
/// <typeparam name="T">The list element type.</typeparam>
/// <param name="xs">The list.</param>
/// <returns>The value of the k-th largest element in the list.</returns>
public static T QuickSelect<T>(this IList<T> xs, int k)
{
return xs.QuickSelect(0, xs.Count, k, Comparer<T>.Default);
}
/// <summary>
/// Gets the median value of the list. If the list has an even number of elements, the value to the
/// left of the median is returned.
/// </summary>
/// <typeparam name="T">The list element type.</typeparam>
/// <param name="xs">The list.</param>
/// <param name="comparer">The object to use to compare elements.</param>
/// <returns>The median value of the list.</returns>
public static T Median<T>(this IList<T> xs, IComparer<T> comparer)
{
return xs.QuickSelect(xs.Count / 2, comparer);
}
/// <summary>
/// Gets the median value of the list. If the list has an even number of elements, the value to the
/// left of the median is returned.
/// </summary>
/// <typeparam name="T">The list element type.</typeparam>
/// <param name="xs">The list.</param>
/// <returns>The median value of the list.</returns>
public static T Median<T>(this List<T> xs)
{
return xs.QuickSelect(xs.Count / 2);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment