Partition sort programming problem

Question

I need an algorithm to select the kth largest or smallest value. The values will be ints. My instructor told me to use a modified partition algorithm to find the kth largest or smallest value. Any thoughts?

Answer 1

The STL has a partial_sort function that will sort the first k items of a sequence, and allowing you to grab that item with a simple lookup.

In other words, look for std::partial_sort and the rest will be obvious.

There is also a nth_element function in the STL. I'm sure you can figure out how to use it.

Answer 2

The following is a description of the quickselect algorithm. I will assume that you want to find the kth smallest value.

1. Take the first element of your array. This will be your pivot. Keep track of its position.

2. Partition the array based on this pivot. Elements smaller than your pivot go before your pivot in the array; larger, after your pivot. (This step will move your pivot. Keep track of its position in your array.)

3. You now know that your pivot is larger than pivot_position number of elements. Therefore, your pivot is the (pivot_position + 1)th smallest element.

   • If k is equal to pivot_position + 1, then you've found your kth smallest value. Congratulations, return pivot_position as the position of that value in the array.

   • If k is less than pivot_position + 1, you want some value that's smaller than your pivot. Look in the part of the array before your pivot for the kth smallest value.

   • If k is greater than pivot_position + 1, you want some value that's larger than your pivot. Look in the part of the array after your pivot for the k - (pivot_position + 1)th smallest value (since that part of the array excludes the (pivot_position + 1) smallest values).

Since you're using C++, you should probably implement your functions as follows:

int select(int *array, int left, int right, int k);
int partition(int *array, int left, int right, int pivot_position);

select takes your array, left and right bounds, and your k. To clarify, array[left] will be the first element; array[right] will be the last; right - left + 1 will be the length of the array. select returns the position of the kth smallest element.

partition takes your array, left and right bounds, and the starting position of your pivot. It's safe to just pass 0 for pivot_position every time, meaning that you want to use the first element in the array as the pivot. (In a variation called randomized quickselect, you pick a random pivot_position.) partition returns the position of the pivot after you're done moving things around.