CSE 143 Summer 1998
Quiz 0: Review of C

The following is a short quiz designed to review some of the concepts you learned in CSE 142. If you have trouble with any aspect of this quiz, make sure to go back and look over your notes.

Problem 1: Selection Sort

For the following problem, assume that you have an array x, declared as follows:

    int x[] = { 5, 7, 3, 9, 6, 4, 0 };

1. Write a function swapArray that takes an array of integers and two indices, and swaps the array elements at those indices. For example, swapArray( x, 3, 5 ) modifies x so that it contains { 5, 7, 3, 4, 6, 9, 0 }, by swapping the 4 and the 9, which were in positions 3 and 5.

           void swapArray( int x[], int a, int b )
           {
               int t;
               
               if( a != b ) {
                   t = x[ a ];
                   x[ a ] = x[ b ];
                   x[ b ] = t;
               }
           }
   

2. Write a function minIndex that returns the index of the minimum element of a range in an array. minIndex takes an array x, a start index a and an end index b, and returns the index i such that x[i] is the minimum of x[a],x[a+1],...,x[b-1].

           int minIndex( int x[], int a, int b ) 
           {
               int idx;
               int mi = a;
   
               for( idx = a + 1; idx < b; ++idx ) { 
                   if( x[ idx ] < x[ mi ] ) {
                       mi = idx; 
                   }
               }
   
               return mi;
           }
   

3. Write a function minToFront that takes an array x, a start index a and an end index b, and swaps the array element at position a with the element in the range from a to b-1 which is smallest. minToFront( x, 2, 6 ), for example, will transform x into { 5, 7, 0, 9, 6, 4, 3 }, by swapping the 3 (at position 2) with 0 (the smallest in positions 2-5). This function can be expressed simply in terms of swapArray and minIndex.

           void minToFront( int x[], int a, int b )
           {
               swapArray( x, a, minIndex( x, a, b ) );
           }
   

4. Selection sort is a sorting algorithm that works by finding the minimum of an array, moving it to the front of the array, finding the minimum of the remaining elements and moving it to the second position, and so on. For example, if you ran selection sort on x, it would go through a sequence of steps like this:

   {5, 7, 3, 9, 6, 4, 0 }
   {0, 7, 3, 9, 6, 4, 5 }	(swap 0 into the first position, 5 out)
   {0, 3, 7, 9, 6, 4, 5 }	(3 to second position, 7 out)
   {0, 3, 4, 9, 6, 7, 5 }
   {0, 3, 4, 5, 6, 7, 9 }	(no more swaps after here...)

   Write a function selectionSort that takes an array x and an integer n (the length of x) and sorts the array using selection sort. Hint: it turns out that you’ve got everything you need to write selectionSort in the subproblems (a)-(c) above. In fact, it’s just a for loop that repeatedly calls to minToFront!

           /* Note that the last iteration of the loop is n - 2.
              We don’t need to call minToFront( x, n - 1, n ) because
              by the time we get to the end of the array, it will
              implicitly contain the largest element. */
            
           void selectionSort( int x[], int n )
           {
               int i;
               for( i = 0; i < n - 1; ++i ) {
                   minToFront( x, i, n );
               }
           }
   

Problem 2: Student Database

To keep track of students this quarter, we need a database that stores your name, student ID, year, and GPA.

1. Declare a struct Student that stores this information. Student names are at most 64 characters in length.

           struct Student {     /* maybe use typdef here */
               char name[ 65 ];
               int id;
               int year;
               float gpa;
           }
   

2. Now, using the declaration in part (a), write a function that declares a variable of type struct Student, and fills in the fields for you (or some imaginary student). If you want to, you can also then print out the contents of the struct using printf (but beware: printf won’t be allowed for the rest of the course!)

           void fillStudent( void ) 
           {
               struct Student craig;
   
               strcpy( craig.name, "Craig S. Kaplan" );
               craig.id = 9699999;
               craig.year = 2;
               craig.gpa = 1.8;
   
               /* One potential format.  Many others are possible... */
               printf( "name: %s (ID# %7d)\n", craig.name, craig.id );
               printf( "year: %d, gpa: %1.1f\n", craig.year, craig.gpa );
           }