To find the k-th smallest element in an array, you can sort the array, but that takes at least O(n log(n)) time. You can do better than that.

Use the partition function to rearrange the array elements so that all elements in the first portion are less than all the elements in the second portion.

Suppose there are j elements in the first portion.

If k j, then the k-th smallest element must be the k-th smallest element in the first portion. Recursively look there.

Otherwise, the k-th smallest element must be in the second portion. It's not the k-th elementyou need to adjust by the size of the discarded first portion.

For example, suppose the array is partitioned like this:

4 8 6 7 9 2 | 11 15 19 13 

To find the 5th smallest value, you look in the first portion.

To find the 8th smallest value, you look for the 2nd smallest value in the second portion.

Complete the ........ in the if else statements.

/** Swaps two integers. @param x the first integer to swap @param y the second integer to swap */ void swap(int& x, int& y) { int temp = x; x = y; y = temp; }

/** Partitions a portion of an array. @param a the array to partition @param from the first index of the portion to be partitioned @param to the last index of the portion to be partitioned @return the last index j of the first partition so that all values in a[from]...a[j] are <= all values in a[j+1]...a[to]. */ int partition(int a[], int from, int to) { int pivot = a[from]; int i = from - 1; int j = to + 1; while (i < j) { i++; while (a[i] < pivot) { i++; } j--; while (a[j] > pivot) { j--; } if (i < j) { swap(a[i], a[j]); } } return j; }

/** Selects the k-th smallest element in an array segment. @param a an array (whose elements can be rearranged) @param from the first index of the segment @param to the last index of the segment @param k the rank to find (1 = smallest, 2 = second smallest, ...) @return the k-th smallest element in a[from]...a[to] where from <= to and 0 < k <= to - from + 1 */ int select(int a[], int from, int to, int k) { int first = a[from]; int j = partition(a, from, to); if (from == to) {

........

} else if (k <= j - from + 1) {

.......

} else {

........

}

}

int select(int a[], int from, int to, int k); int main() { int a[] = { 4, 9, 2, 8, 7, 5, 3, 2, 11, 6 }; cout << select(a, 0, 9, 1) << endl; cout << "Expected: 2" << endl; cout << select(a, 0, 9, 5) << endl; cout << "Expected: 5" << endl; cout << select(a, 0, 9, 10) << endl; cout << "Expected: 11" << endl; return 0; }