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

}

I really appreciate comments so please feel free to comment on my posts. Whether you agree or disagree, I'd love to hear from you. Also, feel free to link back to your own blog in your comments. You can even subscribe to an RSS feed of the comments on this thread.

© 2008 — , D. Patrick Caldwell, President, Autopilot Consulting, LLC

© 2008 — , D. Patrick Caldwell, President, Autopilot Consulting, LLC

## No comments:

## Post a Comment