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.
-
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:
-
Do you understand how and why bubble sort works?
Draw out a picture and work through it by hand.
-
Do you understand how the code given above implements bubble
sort?
-
Do you understand the trick about quitting early?
-
Can you modify the function given above to implement this trick?