One of the most important features of an array is that it can be sorted in numerical or alphabetical order. We can only do a linear search on an unsorted array, but on sorted array we can do a binary search. In this chapter we will study two different algorithms for sorting, selection sort and bubble sort. We will also learn linear and binary search.

Now let us write a program to accept some scores and sort them from smallest to largest. There are several sorting algorithms. For this example, we will use the selection sort algorithm, that involves finding the smallest of the numbers and exchanging with the first element, finding the next smallest and exchanging with the second number, and so on. The algorithm to find the smallest number is to set the first number as the smallest number and then compare every subsequent numbers. If another number is smaller than the smallest then keep it as the smallest number. In order to exchange the smallest number with another not only we need to know which is the smallest number, but also the array index. In fact, we only need to keep the array index of the smallest number, no need to keep the number itself. Program Six_5 illustrates how to find the smallest number using the array index.

Program Seven_1.

Program Run Seven_1.

In the foregoing example, we did not keep the smallest number, rather its index. We can exchange this number with the first number as follows:

Tmp = scores[1];

Scores[I] = scores[smallest];

Scores[smallest] = temp;

To find the next smallest number, we simple move the index to start with to be the next index (I used begin as the variable). If we continue this process n-1 times we will have the scores sorted. Let us code the program.

Program Seven_2.

Program Run Seven_2.

If the selection sort algorithm was difficult to follow, I suggest you make some cards with numbers and place them inside some squares numbered 1 to n. Then follow the movements of the sort routine and shift the cards around. You will be able to learn the sort routine quicker that way.

While selection sort is an easy sort routine, the algorithm is not designed to detect an already sorted list. Many times a list might be already sorted, it would good to exit the sort routine when a list is sorted. For this reason we use another sort routine called bubble sort. Perhaps the bubble sort is the most popular sorting routine. Bubble sort algorithm is based on comparing one item in the list with the next one and swapping them if needed. This way the largest number settles to the bottom while the smaller ones bubbles up. It is very important to avoid comparing the very last number in the list with a non-existent number. If no swapping is required while comparing all items in the list, the list is sorted and the sort operation may be stopped.

########################## Program Seven-3 #####################################

/*************************************************

Bubble Sort

Teaching objective -Array processing. Array sorting

By Dr. John Abraham

Created for 1380 students

**************************************************/

#include <iostream.h>

int getScores (int scores[]);

void sort(int scores[], int);

void display(int scores[], int);

void swap (int &, int&);

//mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

int main ()

{

int scores[90];

int n; // n for number of scores.

n = getScores(scores); //go get the scores and how many

sort(scores, n);

display(scores,n);

return(0);

}

//mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm

int getScores(int scores[])

{

int n=1;

cout << "ENTER A SCORE AND PRESS ENTER. YOU QUIT ANY TIME BY ENTERING A NEG NUMBER!\n";

cout << "Enter score# " << n << " ";

cin >> scores[n];

while (scores[n] >= 0)

{

n++;

cout << "Enter score# " << n <<" ";

cin >> scores[n];

}

return n-1; //n-1 actual scores read.

}

//fffffffffffffffffffffffffffffffffffffffffffffffffff

void sort(int scores[], int n)

{

int i;

bool cont;

do

{

cont = false;

for (i = 1; i <n; i++) // max i is n-1

{

if (scores[i] > scores [i+1]) // compare with next

{

swap(scores[i],scores[i+1]);

cont = true;

}

}

n = n-1;

}while (cont);

}

//fffffffffffffffffffffffffffffffffffffffffffffffffff

void display(int scores[], int n)

{

int i;

cout<<"Sorted Scores: \n";

for (i=1; i<=n; i++)

cout << scores[i] <<endl;

}

//fffffffffffffffffffffffffffffffffffffffffffffffffffff

void swap (int & a, int & b)

{

int tmp;

tmp = a;

a = b;

b = tmp;

}

########################## Program Seven-3 #####################################

Program Run Seven-3.

Just like the select short, the bubble sort given in Program Seven-3 also uses two loops. The external loop checks to see if the list is sorted. In order to determine if a list is sorted the list should be gone over once to check if the value located in an index is lesser than the value located in the next index. The inner loop does just that; it compares two numbers (one value with the next one), if the first number is greater than the second number they are swapped. Again if you are not clear how the bubble sort works, make some note cards put numbers on them, follow the sort algorithm and learn how it works.

Let us now turn to another program. Here, we will make two lists, names and telephone numbers, and search for a name to find the appropriate telephone number. In this program I introduce a new concept, defining a type. Until now we only used types that were provided to us by C++ compiler. Since most other languages have built in string type, I thought it would appropriate for us to define a string data type. A string is made up of an array of characters. typedef char string[255]; This new type string can be used within this program as any other types; we can make any number of variables of this type.

########################## Program Seven-4 #####################################

/*************************************************

Searching

Teaching objective -Linear Search, unordered list.

By Dr. John Abraham

user defined data type is introduced.

Created for 1380 students

**************************************************/

#include <iostream.h>

#include <string.h>

typedef char string[15]; // type string defined.

int getNames (string names[], string tele[]);

int lookup (int,string, string names[], string tele[]);

int main ()

{

string names[10], tele[10], lookfor;

int n, location;

n = getNames(names, tele);

cout << "\n*******************************\n";

cout << "Enter a name to lookup telephone number ";

cin >> lookfor;

location = lookup (n, lookfor, names, tele);

if (location > 0)

cout << "Name found at location " << location

<< ", Telephone# " << tele[location] << endl;

else cout << "Name not in list! \n";

return 0;

}

int getNames (string names[], string tele[])

{

int n=1;

cout << "Enter a name or 'quit' to stop entry-> ";

cin >> names[n];

while (strcmp (names[n], "quit") !=0 && n <10)

{

cout << "Enter Telephone for " << names[n] << "-> ";

cin >> tele[n];

cout << "--------------------\n";

n++;

if (n<10) {

cout << "Enter a name or 'quit' to stop entry-> ";

cin >> names[n];}

}

return n-1;

}

int lookup (int n,string lookfor, string names[], string tele[])

{

int i=1;

bool found=false;

while (!found && i <=n)

if (strcmp(names[i], lookfor)==0)

found = true;

else i++;

if (found) return i;

else return 0;

}

########################## Program Seven-4 #####################################

########################## Program Run Seven-4 #####################################

Enter a name or 'quit' to stop entry-> Pearl

Enter Telephone for Pearl-> 381-3551

--------------------

Enter a name or 'quit' to stop entry-> Wendy

Enter Telephone for Wendy-> 381-2334

--------------------

Enter a name or 'quit' to stop entry-> Richard

Enter Telephone for Richard-> 512-3312

--------------------

Enter a name or 'quit' to stop entry-> John

Enter Telephone for John-> 3550

--------------------

Enter a name or 'quit' to stop entry-> quit

*******************************

Enter a name to lookup telephone number Richard

Name found at location 3 Telephone# 512-3312

Press any key to continue

########################## Program Run Seven-4 #####################################

########################## Program Seven-5 #####################################

/*************************************************

Searching

Teaching objective -Binary Search sorted list.

By Dr. John Abraham

Created for 1380 students

**************************************************/

#include <iostream.h>

#include <string.h>

typedef char string[15]; // type string defined.

int getNames (string names[], string tele[]);

void sort (int, string names[], string tele[]);

int lookup (int,string, string names[], string tele[]);

void Display(int n, string names[], string tele[]);

int main ()

{

string names[10], tele[10];

int n;

n = getNames(names, tele);

cout << "\n*******************************\n";

sort(n, names, tele);

Display( n, names, tele);

return 0;

}

int getNames (string names[], string tele[])

{

int n=1;

cout << "Enter a name or 'quit' to stop entry-> ";

cin >> names[n];

while (strcmp (names[n], "quit") !=0 && n <10)

{

cout << "Enter Telephone for " << names[n] << "-> ";

cin >> tele[n];

cout << "--------------------\n";

n++;

if (n<10) {

cout << "Enter a name or 'quit' to stop entry-> ";

cin >> names[n];}

}

return n-1;

}

int lookup (int n,string lookfor, string names[], string tele[])

{

int first=1, last=n, middle;

bool found=false;

while (!found && first <= last)

{

middle = (first+last)/2;

if (strcmp(names[middle], lookfor)==0)

found = true;

else if (strcmp(names[middle], lookfor) < 0) first = middle+1;

else last = middle-1;

}

if (found) return middle;

else return 0;

}

void sort(int n, string names[], string tele[])

{

int i;

char temp[15], ttemp[15];

bool sorted = false;

while (!sorted)

{

sorted = true;

for (i=1;i <= n-1; i++)

if (strcmp (names[i], names[i+1]) >0)

{

strcpy (temp,names[i]); strcpy(ttemp,tele[i]);

strcpy (names[i],names[i+1]); strcpy(tele[i], tele[i+1]);

strcpy (names[i+1],temp); strcpy(tele[i+1],ttemp);

sorted = false;

}

n--;

}

}

void Display(int n, string names[], string tele[])

{

string lookfor;

int i, location;

cout << "Sorted names \n";

for (i=1; i <=n; i++) cout << i <<" "<< names[i] <<" " <<tele[i] <<endl;

cout << "SEARCH ROUTINE. ENTER quit TO STOP\n";

cout << "Enter a name to lookup telephone number ";

cin >> lookfor;

while (strcmp(lookfor,"quit")!=0)

{

location = lookup (n, lookfor, names, tele);

if (location > 0)

cout << lookfor <<" found at location " << location

<< ", Telephone# " << tele[location] << endl;

else cout << "Name not in list! \n";

cout << "Enter a name to lookup telephone number ";

cin >> lookfor;

}

}

########################## Program Seven-5 #####################################

########################## Program Run Seven-5 #####################################

Enter a name or 'quit' to stop entry-> fowler

Enter Telephone for fowler-> 381-5122

--------------------

Enter a name or 'quit' to stop entry-> chen

Enter Telephone for chen-> 382-5512

--------------------

Enter a name or 'quit' to stop entry-> meng

Enter Telephone for meng-> 381-5512

--------------------

Enter a name or 'quit' to stop entry-> quit

*******************************

Sorted names

1 chen 382-5512

2 fowler 381-5122

3 fox 312-5512

4 meng 381-5512

SEARCH ROUTINE. ENTER quit TO STOP

Enter a name to lookup telephone number meng

meng found at location 4, Telephone# 381-5512

Enter a name to lookup telephone number reggie

Name not in list!

Enter a name to lookup telephone number chen

chen found at location 1, Telephone# 382-5512

########################## Program Run Seven-5 #####################################