**Reading**

*None*.

**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