CSC 213, Fall 2008 : Schedule : Lab 1

Lab 1: Review of C; Sorting and Order Statistics

Goals: This laboratory exercise provides practice with arrays, in the context of procedures. Details focus on a procedure to partition an array, with applications to sorting and order statistics.

Reading: There is no formal reading assignment for this lab. However, you may wish to refamiliarize yourself with C by spending a few minutes browsing some of your CSC 201 assignments, your favorite C reference manual, or Henry Walker's An Introduction to C Through Annotated Examples.

Partners: For this lab, you may work alone or with a partner of your choosing.

Problems: In this lab, you are to write solutions to the following three problems. In each case, turn in your solutions utilizing the format for submitting assignments; see also "Work to be Turned In" (below).

1. Partition
2. Quicksort
3. Order statistics

1. Partition: Write a procedure
   

   	void partition (int a[], int left, int right, int* middle)
   

   which rearranges those elements within the a array with indices between left and right, such that
   • left ≤ *middle ≤ right,
   • a[left] is moved to a[*middle],
   • each element a[left], a[left+1], ..., a[(*middle)-1] is less than or equal to a[*middle], and
   • each element a[(*middle)+1], ... a[right-1], a[right] is greater than or equal to a[*middle].

   In other words, the value at a[left] acts as a special value called the pivot. Here is a graphical representation of the array precondition:

   
   Once the partition function is called, the elements are rearranged to meet the following postcondition:
   
   where all the elements less than the pivot (shown in a lighter color) are to its left, and the elements greater than the pivot (shown in a darker color) are to the right.

   Thus, the array segment a[left] ... a[right] is rearranged as required, to give a new arrangement of values a[left] ... a[(*middle)] ... a[right], where all array elements before position *middle have values ≤ a[(*middle)] and where a[(*middle)] is less than or equal to all array elements after position *middle

   Include your partition procedure in an appropriate test program, so that you can adequately check the correctness of your code. 

   Discussion: Work within partition should be done with a single pass through the elements a[left] ... a[right], as follows.

   1. move backward in the array through a[right], a[right-1], ... until finding an element a[r_spot] where a[r_spot] < a[left], if such an element exists.

   2. move foward in the array through a[left], a[left+1], ... until finding an element a[l_spot] where a[l_spot] > a[left], if such an element exists.

   3. swap a[l_spot] and a[r_spot].

   4. continue steps 1, 2, and 3 until searching all elements in the array segment. (At this point, "small" values will have been moved early within the array segment, while "large" values will have been moved late.)

   5. place a[left] in its appropriate position a[*middle], where *middleis the index where l_spot and r_spot have come together.

2. Quicksort: The quicksort algorithm proceeds by applying partition recursively on the subintervals (left,middle-1) and (middle+1, right), until all subintervals have no more than a single element (and thus are already sorted).

   Write a procedure

   	void quicksort (int a[], int n)

   that uses the partition procedure and sorts the array a[0], ..., a[n-1] using the quicksort algorithm. Since this quicksort is to be a general sorting procedure for any array, the integer n is used to indicate the size of the array.

   As in the previous problem, you should include your quicksort procedure in an appropriate test program, so that you can adequately check the correctness of your code.

3. Order statistics: The partition procedure of problem 1 may be used to find the kth smallest element in an array segment a[left], ..., a[right], as follows:

   1. If there is only one element in a[left], ..., a[right], then one expects k = 1, and one can return that element.

   2. Use the partition procedure to rearrange a[left], ..., a[right] into a[left] ... a[(*middle)] ... a[right] as described in problem 1.

   3. If k = ((*middle)-left+1), then a[*middle] is the desired element, and stop.

   4. If k ≤ ((*middle)-left), then apply this algorithm recursively to find the kth smallest element in an array segment a[left], ..., a[(*middle)-1].

   5. If k ≥ ((*middle)-left), then apply this algorithm recursively to find the k-((*middle)-left)-1th smallest element in an array segment a[(*middle)+1], ...,a[right].

   Problems for part 3:

   1. Write a procedure
      

      	int selectk (int a[], int n, int k)
      

      that uses the above algorithm and procedure partition to find the kth smallest element in an array a, where a has n elements. (Note: 1 ≤ k ≤ n.)

   2. Write a procedure
      

      	int median (int a[], int n)
      

      that uses the above algorithm and procedure partition to find the median element in an array a, where n is the size of the array.

For each program, use the format for submitting assignments, which applies to all programming exercises in the course.

While you must use the same partition procedure in all parts of this laboratory exercise, you are free to organize the procedures for the various parts into one or more files as you wish. Also, your test runs may be included in a single main program or in several programs, as you wish.

When you finish testing, be sure to write up why your testing demonstrates that your code works correctly. (I.e., you might consider what cases might be encountered for arrays of data, and then note that your testing has covered those cases.)

Jerod Weinman

Based on http://www.cs.grinnell.edu/~davisjan/csc/213/2006F/labs/01.html
Last revised May 28, 2008
With thanks to Henry Walker and Janet Davis