/* * Quicksort */ #include  #include  #define SEED 2 #define LENGTH1 20 #define LENGTH2 15 int rand_int(int first, int last); int partition(int a[], int first, int last); void quicksort(int a[], int first, int last); void swap(int a[], int i, int j); int * create_rand_int_array(int length); void display_array(int a[], int first, int last); int kth_smallest(int a[], int first, int last, int k); void main() { srand48(SEED); int * a = create_rand_int_array(LENGTH1); printf("Unsorted array: "); display_array(a, 0, LENGTH1-1); quicksort(a, 0, LENGTH1-1); printf("Sorted array: "); display_array(a, 0, LENGTH1-1); free(a); a = create_rand_int_array(LENGTH1); printf(" Unsorted array: "); display_array(a, 0, LENGTH1-1); int k = kth_smallest(a, 0, LENGTH1-1, 15); printf("15th smallest = %d ",k); free(a); a = create_rand_int_array(LENGTH2); printf(" Unsorted array: "); display_array(a, 0, LENGTH2-1); k = kth_smallest(a, 0, LENGTH2-2, 6); printf("6th smallest = %d ",k); free(a); return; } /* * This returns the kth smallest value in the array a[], where the * smallest is the 0th, the next smallest is the 1st, and so on. * The average time complextiy should be O(n). */ int kth_smallest(int a[], int first, int last, int k) { return a[first]; } /* * Partitions array[first...last] using a "pivot" = a[first] * Returns a value k such that a[first...k] have values less * than or equal to the pivot, and a[k+1...last] have values * greater than pivot. */ int partition(int a[], int first, int last) { swap(a, first, rand_int(first,last)); /* Choose random pivot */ int pivot = a[first]; int less = first+1; for (int scan=first+1; scan= last) { return first; } int size = last-first+1; double randval = drand48(); int delta = (int) (randval*((double) size)); return first + delta; } 

Problem 1 ( 2 pts). Attached is a program quicksort.c. It has a function quicksort that implements Quicksort. There is another function int kth_smallest(int a[ ], int first, int last, int k) that returns the kth smallest value in the integer array (a[first], a[first +1],.,a[ last]) but it doesn't work. We assume that there is a 0th smallest value, which is the smallest value in the array; and so k can equal 0 . Rewrite kth_smallest so it does work using the same ideas in quicksort. Its average time complexity should be O(n), where n is the size of the array. You don't have to prove the time complexity. But to convince yourself that this is true, assume that each call to the function will lead to a pivot that divides the array exactly in half. Then the first call scans the array of length n, then the next call will scan an array with length n/2, etc. Note that CLRS discusses kth-smallest number problem in Chapter 9 Median and Order Statistics (pp. 213227). More specifically it's discussed in Section 9.2 (pp. 213-219) and the algorithm is RANDOMIZED-SELECT. Hint: Suppose you wanted to return the kth smallest value in an array a [ ]. Let's suppose the pivot occurs at location m, so that (a[0], a[1],,a[m1]) is in the left subarray and (a[m+1],a[m+],,a[n1]) is in the right subarray. Note that if k=m then a[m] is the k th smallest value. If km then the kth smallest value is in the right subarray. Note that if k=m+1 then the k th smallest value is the smallest value (0th smallest value) in the right subarray. Thus, the kth smallest value is the k - (m+1) th smallest value in the right subarray. The output should look like this: Unsorted array: 15658114142448613512872163373051931497965121100107 Sorted array: 30374451586572798693100107114121128135142149156163 Unsorted array: 11437121100149163142128156517944135726510793863058 15th smallest =135 Unsorted array: 10058793712872121441078665114309351 6th smallest =72