Searching and Sorting

We have two basic data structures available now: the Array, and a Linked List. These are great for saving many data items, but we need to look at a few ways to use the data once it is in one of these things.

Searching

The basic tool to searching a data structure is the loop.

Lets start by finding the biggest and smallest element in a simple array. Here is the basic program:

Searching for an Integer

Here is what we want to do (this should look familiar):

#include <iostream>

using namespace std;
#define NUMSCORES 7

int searchMin(int list[], int size);
int searchMax(int list[], int size);

int main() {
    int testScores[] = { 90,67,86,88,98,69,72};

    int minScore;
    int maxScore;

    minScore = searchMin(testScores,NUMSCORES);
    maxScore = searchMax(testScores,NUMSCORES);

    cout << "min = " << minScore << " max = " << maxScore << endl;
}

Finding min and max

You gave this problem a try in an earlier lab. Let’s revisit the idea again.

The challenge is to figure out how to locate the required elements in the lists.

We solve this problem by looping over all the items in the Array (or list).

As you start, you have no items in hand. When you look at the first item it is both the biggest and the smallest seen so far, so we set a variable to this value (as either biggest or smallest depending on what you are looking for).

Then we enter a loop looking at the rest of the items doing a comparison and replacing our current selection if needed.

int searchMin(int list[], int size) {
    int min = list[0];
    for(int i=1;i<size;i++) {
        if(list[i] < min) min = list[i];
    }
    return min;
}

int searchMax(int list[], int size) {
    int max = 0list[0];
    for(int i=1;i<size;i++) {
        if(list[i] > max) max = list[i];
    }
    return max;
}

Running this example gives us this result:

$ search
min = 67 max = 98

That was not very hard, was it?

Finding an Element

If we want to know if some item is in the list, we again need to search all the elements, since we do not know where it might be.

Here is a routine to find an element

bool findItem(int list[], int size, int item) {
    bool found = false;
    for(int i=0;i<size;i++) {
        if(list[i] == item) {
            found = true;
            break;
        }
    }
    return found;
}

This is less than ideal. The logic here returns true if the item is in the array, but we do not know where it is located.

Can you think of a way to return the index where the item was found? What if the item is not in the list? What value will you return?

Let’s try this code out:

int item = 88;
findItem(testScores,NUMSCORES,item);

item = 30;
findItem(testScores,NUMSCORES,item);

And we get this result:

$ locate
88 is in the list
30 is not in the list

Now that we have got the basic idea of how we move through an array searching for something, let’s try to sort the array.

Ready, Set, Think!

Sorting an Array

How do we sort things? We obviously need to search for the biggest element in the list and put it first (assuming we want the biggest number first in our result). How do we get it there?

Think how you might do it manually. You would scan the array and locate the biggest element. Then you would need to move it to the front of the list. But there is something sitting there, so we need to put that element somewhere. Why not just swap them?

Now what.

We have the biggest element in place. Let’s just repeat the search, but now we look at only those elements from the second position down!

Neat!

Helper Routines

Before we try to code this, lets build a helper routine. This routine will tell us the index of the biggest element in a list. It looks like this:

Locating the Biggest Element

int locateMax(int list[],int size) {
    int max = list[0];
    int index = -1;

    for(int i=1;i<size;i++) {
        if(list[i] > max) {
            max = list[i];
            index = i;
        }
    }
    return index;
}

This look very similar to the search routine we had earlier.

Now, we need to work our way through the array, using this routine, and swapping elements. You will need to study this code and see how it works. Can you make it simpler?

Sorting Routine

void sortArray(int list[], int size) {
    for(int i=0;i<size;i++) {
        // get the biggest element from the i-th position down
        int bigint = locateMax(list+i,size-i) + i;

        // swap biggest with the first
        int temp = list[bigint];
        list[bigint] = list[i];
        list[i] = temp;
    }
}

Look closely at what is going on. We are looping over the entire array, looking for the biggest element in the sub-array that starts at index i. When we find that element, we swap the contents of the current array position i with the location of the biggest element. When the smoke clears, we get a sorted array!

Note

Go back and look at that code again. In the sortArray function, we call the findMax function. That second function takes a list as a parameter. Notice that we call it with an expression: list + 1. WHat in the world happens there?

C++ sends down an address when we pass an array to the function, The address of the list is just list. Howeverm we added “i” to that address. If you remember how memory is organized in an array, that expression calculated the address of the next item in the list. So, findMax does not the initial address of the list, it gets successively smaller lists to search. That is just what we want here!

Sorted Output

$ sort
0 = 98
1 = 90
2 = 88
3 = 86
4 = 72
5 = 69
6 = 67

This kind of code is very useful when you have complex data and you need to locate some value. Remember that an array can hold any object, even objects from some class. Our search scheme can be adapted to look inside each object and sort based on some attribute inside!