Pointing Outside of Yourself

Since an expression which is just the name of an array is a pointer to its first element, if we try to pass an array to a function as in foo( a ), we'd really be passing a pointer to the first element in the array. With that in mind, we can write a routine to print out the elements in an integer array like this.

void print_array( int a[], int num )
{
   int i ;

   for( i = 0; i < num; ++i )
      printf( "%d\n", a[i] ) ;
}

where the first argument is the array and the second is the number of elements that need to be printed. Notice that in declaring the array argument, we don't need to specify how many elements the array contains. The function doesn't care since as far as it's concerned, a is a pointer. Hence we could have equivalently declared print_array() as

void print_array( int *a; int num )

Another thing to notice about "passing arrays" is that since we're passing a pointer, changes made to the array in the function are seen by the caller unlike when we pass basic types like integers. This is why, when calling scanf() or gets(), we just give the name of the character array instead of using the & operator as we do for integers in scanf(). This feature allows us to easily implement something like a sorting routine. One of the simplest techniques for sorting is called a bubble sort and is based on the following observations:

First we'll be making passes through the array comparing each pair of consecutive elements, i.e. compare elements 0 and 1, then elements 1 and 2, then 2 and 3, and so on.
If we compare elements j and j+1, and element j is bigger than element j+1 we'll swap them. (This is if we're sorting in ascending order; if we're sorting in descending order, reverse the comparison.)
For each pass through the array, the biggest element will "bubble" up to the top of the array. \item So if we have n elements to sort, we need only do n passes through the data each one going up to, but not including, the biggest element sorted in the last pass.
We can write a function to sort an array using a bubble sort this way:

void bubble_sort( int a[], int num )
{
   int i, j ;

   for( i = num; i > 1; --i )
      for( j = 0; j < i - 1; ++j )
         if( a[j] > a[j+1] )
            swap( &a[j], &a[j+1] ) ;
}

Bubble sort is, by far, not the most efficient sort, but it is one of the simplest. In fact, it is almost the worst of the major sorts in terms of efficiency. However, bubble sort is smart enough to be able to stop the passes if along the way the list becomes sorted. The basic idea is that if we make a pass through the array without making any swaps, then we're done and we can stop. You should take some time and make sure you can answer "yes" to the following questions:
  1. Do you understand how and why bubble sort works? Draw out a picture and work through it by hand.
  2. Do you understand how the code given above implements bubble sort?
  3. Do you understand the trick about quitting early?
  4. Can you modify the function given above to implement this trick?

Write the prototype for a function that is called f1() that takes a character array and an integer as arguments and returns an integer. The string parameter should be called s and the integer parameter called n.