Section 7.3 of Problem Solving with C++.
Lecture
Often with arrays it's more powerful to return the index of an element
with a certain property, rather than the value
of the element. For example, if string *name is an array of names of contest participants, and int *score is an array of
scores, such that participant name[i] has score score[i], then knowing the value of the largest
element in score won't tell me who
the winner is, but knowing the index
(i) of the largest element in score will.
So, with this in mind, let's consider writing a function maxIndex that will return
the index of the element with the maximum value in array arrayIn of sizeIn objects of type int.
int maxIndex(int *arrayIn, int sizeIn)
{ int iMax = 0; for(int i = 1; i < sizeIn; i++) if (arrayIn[iMax] < arrayIn[i]) iMax = i; return iMax;}
Very simple function! Now, using our above example, the winner
of our contest is NAME[maxindex(SCORE,N)].
Consider the following function that uses our maxIndex function:
void mystery(int *arrayIn, int sizeIn)
{ for(int size = sizeIn; size > 1; size--) { int k = maxIndex(arrayIn,size); int temp = arrayIn[size-1]; arrayIn[size-1] = arrayIn[k]; arrayIn[k] = temp; }}
What does the mystery function do? Well, it starts by swapping the largest element in
the array with the last element of the array, and then pretends the last array
slot isn't there any more. Hopefully, you see that
this puts the largest at the back of the array, the next largest in the second
to last spot, etc. until the array is in sorted order! This sorting
algorithm is known as Selection
Sort, because it selects
the largest of the remaining elements and puts it in its proper spot in the
sorted array. If you define the swap function (as in Class 18), you can write a particularly succinct version of this
function:
void selectionSort(int *arrayIn, int sizeIn)
{ for(int size = sizeIn; size > 1; size--) swap(arrayIn[maxindex(arrayIn,size)],arrayIn[size-1]);}
This is actually a subtle and important function for the way it uses pass-by-reference on array elements. Make sure you understand how it works!
Searching for values in arrays is another fundamental operation.
The basic format is search(A,N,x), where we search for value x in the array A of N elements, and return the index of an
element of A that matches the
value x. If no such element
is found, an index of N may be returned
and, since it is not a valid index, the caller of the function can determine
that no match was found. For example, to search in an array of objects of type string, I'd define the
following function:
int search(string *arrayIn, int sizeIn, string target)
{ int i = 0; while(i < sizeIn && arrayIn[i] != target) i++; return i;}
1. Write a program that reads in a list of 10 names (first name followed by last name) and prints them out in the usual order - i.e. alphabetically by last name, using first names to break ties.
Last modified by LT M. Johnson 10/23/2007 08:59:49 AM