Description
The following recursive C++ function select() selects the k-th smallest item from an unsorted array of integers. Your assignment is to create a C++ program “select.cpp” with an equivalent version of the select() function that uses iteration rather than recursion.
Hint: the two recursive calls in select() can easily be rewritten so that the function is tail recursive.
You must use the techniques shown in class, and you must explain how you applied the techniques to the transformation. Do not just find an iterative version and turn it in. Do not modify the swap() or partition() functions. You must also develop and include CUnit tests to validate your function for several key input arrays.
/**
* A utility function to swap two values.
* @param v1 the first value
* @param v2 the second index
*/
void swap (int &v1, int& v2 ) {
int t = v1;
v1 = v2;
v2 = t;
}
/**
* This function places the last element as pivot at
* its correct position in sorted array ‘a’
* array, and places all smaller (smaller than pivot)
* to left of pivot and all greater elements to right
* of pivot.
* @param a the array to be partitioned
* @param lo starting index
* @param hi ending index
* @return the partitioning index
*/
int partition (int a[], int lo, int hi) {
int &pv = a[hi];
int i = lo-1;
for (int j = lo; j < hi; j++) { if (a[j] <= pv) { swap(a[++i], a[j]); } } swap(a[++i], pv); return i; } /** * This function selects the kth smallest itmem from the * input array 'a' between the lower index 'lo' and the * higher index 'hi'. * * @param a array to be selected, * @param lo lower index * @param hi higher index * @param k kth smallest item index * @return the kth smallest item */ int select(int a[], int lo, int hi, int k) { if (lo == hi) { return a[lo]; } // Partitioning index int p = partition(a, lo, hi); if (k == p) { return a[k]; } else if (k < p) { return select(a, lo, p-1, k); } else { return select(a, p+1, hi, k); } } /** * This function selects the kth smallest itmem from the * input array 'a'. * * @param a array to be selected, * @param n number of items in array * @param k kth smallest item index * @return the kth smallest item */ int select(int a[], int n, int k) { return select(a, 0, n-1, k); }
