Chapter 11

# 11.1 The study of algorithms

An algorithm is a precise set of instructions for achieving a particular goal. In a computer program, all data structures have associated algorithms which are used to access and modify the data they contain. Built-in data structures in C++, such as ints and floats, have built-in algorithms for such things as arithmetic, input and output. User-defined classes have their associated algorithms encapsulated in their class functions.

For many operations performed on data structures, there are several different algorithms that may be used. Different algorithms make different demands on computer memory and running time. In an industrial setting, where the cost of commercial software and staff time become important, the availability and price of off-the-shelf routines that implement the algorithms, and the programming time required to implement the algorithm if no commercial package is available, must be considered.

It is therefore useful to know things like the running time and memory requirements of algorithms so that you can make an informed decision about which algorithm is best for your particular application. The theoretical study of algorithms, known as complexity theory, is a highly mathematical branch of computer science. It involves detailed analysis of the number of steps required by an algorithm to process varying amounts of data. For many algorithms, exact results have been derived, but for others, only approximations or averages are available.

Since this book assumes no significant mathematical knowledge on the part of the reader, we won’t be going into any detailed studies of the complexities of the algorithms we will be studying. It is still important, however, for you to achieve an understanding of how the complexity of an algorithm is measured, and to develop techniques whereby you can measure these complexities experimentally by actually running programs to calculate them. This is one of the goals of this chapter.

We begin our study of algorithms by looking at a couple of methods for searching a list of items. We use searching algorithms as an introduction because they are commonly used as examples in an introductory course in programming, so there is a good chance you have met them before. They are also fairly simple algorithms, both to code and to analyse, so you shouldn’t have to wrestle with the concepts behind the algorithms while you are trying to see how their efficiencies can be measured.

We will consider two searching algorithms: sequential search and binary search.

# 11.2 Sequential search

Both searching algorithms we will consider in this chapter work on one-dimensional lists of data. The data may be stored in an array or a linked list. The examples in this chapter all assume that the data are stored in an array.

A searching algorithm requires a target for which to search. The list is searched until either the target is located or the algorithm has determined that the target is not in the list. For simple data types, such as ints, a simple comparison is performed between the target and the data stored at each node in the list. For more complex data types such as user-defined classes, often one of the fields is chosen as a key field. The target is then compared only to the key field, with the other fields being ignored for the purposes of the search. For example, a database may store customer information for a company. A customer is represented by a class in which the surname, first name, address, phone number, and so on are stored. For searching purposes, an ID number  unique to each customer may be defined. This number is then used as the key field in the class, and the searching algorithm would expect the target to be an ID number.

The sequential search is simple: we start at the first array element and compare each key with the target until we have either found the target or reached the end of the list without finding it. The index of the corresponding array element is returned if the search is successful, and some flag value, such as -1, is returned if the search fails. We can formalize the algorithm as follows:

1. Read in Target; initialize Marker to first array index (0).

2. While Target != Key at location Marker and not at the end of the list:

3. Marker++.

4. If Target == Key at location Marker, then return Marker.

5. Else, return -1.

# 11.3 Binary search

There are two forms of the binary search algorithm, both of which are designed to be applied to lists of sorted data. The condition that the data be sorted is a constraint not present for the sequential search, and could mean that extra computing is required to sort the list before the binary search is used. Since sorting algorithms are always less efficient than searching algorithms (as we will see in the next chapter), this could mean that even though binary search on its own is much more efficient than sequential search, the combination of (sort + binary search) may actually be less efficient than sequential search on its own. The binary search algorithm is best used on lists that are constructed and sorted once, and then repeatedly searched.

We will only study one form of the binary search algorithm in depth here, and leave the other form for the exercises at the end of the chapter. The form we will look at here is sometimes called the forgetful binary search because it doesn’t bother to check if the target node has been found until the very end of the algorithm. The forgetful algorithm looks less efficient than it needs to be, but as we will see, it is in most cases more efficient than the other form of the binary search.

The basic idea behind either binary search algorithm is to chop the list in half at each step, so that you only have half as many keys to search at each stage. The forgetful binary search continues to chop the list in half until there is only one element left, and then checks to see if this single remaining element is the target. The more traditional form of binary search checks at each stage to see if the target has been found.

The formal statement of the forgetful binary search algorithm is as follows, where we have a list of numdata elements stored in an array with indexes ranging from 0 to ArraySize - 1. We use three markers (top, bottom, middle) to mark positions in the list.

1.   Set top = numdata - 1; set bottom = 0.

2.   While top > bottom do:

3.   set middle = (top + bottom) / 2 [using integer division]

4.   if key at index middle is less than target key, then set bottom = middle   + 1

5.   Else, set top = middle.

6.   If top == -1, return -1 indicating that the list is empty.

7.   If key at location top is the target key, return location top indicating that the target has been found.

8.   Else, return -1 indicating target has not been found.

You should work through the algorithm by hand on a short list (around 10 elements) for cases where the target is present in the list and where it is not present. If you count the number of comparisons done in the while loop (step 2 above) you should see that doubling the length of the list adds, on average, only one extra comparison to the algorithm.

We will return to the discussion of the efficiency of this algorithm later. For now, we will write some C++ templates that can be used for searching.

# 11.4 C++ templates for searching algorithms

Since we have precise statements of both searching algorithms, writing C++ code to implement the algorithms is straightforward. Since we would like to be able to apply these algorithms to any type of data, we will write templates for classes in which the algorithms are implemented.

## 11.4.1 Sequential search

Let us begin with the sequential search algorithm. We can define a class template that contains the basics that will be needed in any class involving searching: the array in which the data are to be stored, the searching function itself, and input and output functions. We will use this opportunity to show how to overload the << and >> operators for output and input, so that user-defined objects can be read from istream objects (such as cin) and written to ostream objects (such as cout).

We will define a base class called datalist which is a general purpose array-based list class containing a pointer to a dynamically allocated array Element, a constructor, destructor, and input/output functions. We will make use of this class in many algorithms in this and later chapters. The definition of the class is in the file datalist.h:

#ifndef DATALIST_H

#define DATALIST_H

#include "mydefs.h"

#include <iostream.h>

template <class Type>

class datalist

{

protected:

Type *Element;

int ArraySize;

public:

datalist(int arraysize = 10) : ArraySize(arraysize),

Element(new Type[arraysize]) {}

virtual ~datalist();

friend ostream& operator<<(ostream& OutStream, const

datalist<Type>& OutList);

friend istream& operator>>(istream& InStream,

datalist<Type>& InList);

};

#endif

The class searchlist inherits datalist and adds a Search() function which will implement the sequential search algorithm. The definition of the searchlist class is in the file search.h:

#ifndef SEARCH_H

#define SEARCH_H

#include "datalist.h"

template <class Type>

class searchlist : public datalist<Type>

{

public:

searchlist(int arraysize = 10) :

datalist<Type>(arraysize) {}

virtual ~searchlist() {}

virtual int Search(const Type& Target) const;

};

#endif

Most things (apart from the input/output functions) should look familiar in these classes. Since we are planning on inheriting the datalist class, we have made the non-public fields protected, and have declared the functions as virtual.

Now we must consider the input/output functions in the datalist class. We would like to be able to use the << and >> operators for output and input of the array elements and other information in this class. You might think that since << and >> are just operators, we could overload them in the same way we have been overloading other operators such as +, >, and so on up to now. In a sense we could do this, but there is a slight problem. If we want to use the << operator to print the contents of a datalist object ListObject to the output stream cout, we would like to be able to say

cout << ListObject;

Note that cout is the left operand of the << operator, and the class object ListObject is the right operand. If we tried to overload the << operator in the same way we have used for other operator overloadings up to now, we would write a declaration like:

ostream& operator<<(ostream& OutStream);

This declaration, however, assumes that the class object calling the operator is the left operand and the output stream OutStream is the right operand, so that to use this declaration, we would have to say:

ListObject << cout;

which doesn’t look right. It would also make it impossible to chain output of user-defined objects with other built-in variables in the same output statement.

We therefore need a way of overloading an operator so that the object calling the operator is the right operand and the external object is the left operand. Doing this requires the use of an external function (a function that is not a member of the class). The declaration

friend ostream& operator<<(ostream& OutStream,

const datalist<Type>& OutList);

declares an overloaded << operator whose left operand is an ostream object (cout, for example) and whose right operand is a datalist object. Because this operator will need access to the protected fields Element and ArraySize, the function must be made a friend of the class. A friend function is allowed access to all protected and private fields of a class.

As mentioned earlier, the friend concept in C++ should be used sparingly, since it presents glaring opportunities to violate the principles of object oriented programming by allowing any function or class to have access to the private fields of any other class. Because of the way C++ was designed, however, there are some cases where friends must be used, since there is no other way of doing things. The situation here is an example of this. There is no C++ language syntax which allows a class function to overload an operator such that the object calling the overloaded operator is that operator’s right operand. Perhaps in a future version of the language there will be, at which time the use of friends in this context can be eliminated.

The definitions of these functions are in the two files datatemp.h and searchtm.h. First, datatemp.h:

#ifndef DATATEMP_H

#define DATATEMP_H

#include "datalist.h"

template <class Type>

datalist<Type>::~datalist()

{

delete [] Element;

}

template <class Type>

ostream& operator<<(ostream& OutStream,

const datalist<Type>& OutList)

{

OutStream << "Array contents:\n";

for (int element=0; element < OutList.ArraySize;

element++)

OutStream << OutList.Element[element] << ' ';

OutStream << endl;

OutStream << "Array size: " << OutList.ArraySize

<< endl;

return OutStream;

}

template <class Type>

istream& operator>>(istream& InStream,

datalist<Type>& InList)

{

cout << "Enter array elements:\n";

for (int element=0; element < InList.ArraySize;

element++)

{

cout << "Element " << element << ": ";

InStream >> InList.Element[element];

}

return InStream;

}

#endif

The overloaded << operator prints out the heading “Array contents:” and then lists the contents of the array Element separated by blanks. Note that the << operator is also used to print out each array element, so if these elements are objects of a user-defined class, that class must also have an overloaded << operator defined for it (we will see an example of this at the end of this chapter).

The overloaded << operator returns an ostream object to allow chaining of objects to the output stream. For example, if we wanted to print out two objects of type searchlist, we could write:

cout << ListObject1 << ListObject2;

This statement is constructed left to right. The first operation to be performed is cout << ListObject1. Here, the left operand of the << operator is the standard output stream cout, and the right operand is ListObject1. The various elements in ListObject1 are copied into cout according to the instructions in the operator<<() function given above. At the end of this function call, the stream cout is returned. Thus the return value of the operation cout << ListObject1 is cout. The second operation then becomes cout << ListObject2, which causes the components in ListObject2 to be added to cout. The result is that the operator<<() function is called twice: once to print out the components in ListObject1 and then to print out the components in ListObject2.

Similar considerations apply to the overloaded >> operator for reading input from an istream object.

Finally, the Search() function implements the sequential search algorithm, and is defined in the file searchtm.h:

#ifndef SEARCHTM_H

#define SEARCHTM_H

#include "search.h"

#include "datatemp.h"

template <class Type>

int searchlist<Type>::Search(const Type& Target) const

{

for (int element=0; element < ArraySize; element++)

{

if (Element[element] == Target)

return element;

}

return -1;

}

#endif

A main() function that tests these routines is in the file search.cpp:

#include "searchtm.h"

const int SIZE = 5;

main()

{

searchlist<float> List1(SIZE);

float Target;

int Location;

cin >> List1;

cout << List1;

for (int i = 0; i < 5; i++)

{

cout << "Search for a float: ";

cin >> Target;

if ((Location = List1.Search(Target)) != -1)

cout << "Found at index " << Location << endl;

else

}

return 0;

}

A list of five floats is declared, and read in from the keyboard, using the cin >> List1 statement. The << operator is then tested by printing out the list that has just been read in. Finally, the for loop gives the user five chances to look up some numbers in the list and prints out the results.

## 11.4.2 Binary search

Having laid the groundwork for our searching templates with the sequential search algorithm, we may use inheritance to define a class that implements the binary search algorithm. We can inherit everything from the datalist template defined above, and add a Search() function which implements the binary search algorithm.

The derived class is defined in the file binary.h:

#ifndef BINARYH

#define BINARYH

#include "datalist.h"

template <class Type>

class forgetsearch : public datalist<Type>

{

public:

forgetsearch(int arraysize=10) :

datalist<Type>(arraysize) {}

virtual ~forgetsearch() {}

virtual int Search(const Type& Target) const;

};

#endif

We inherit the datalist class template (remember that the Type parameter must be included in all references to the datalist template). The forgetsearch constructor calls the datalist constructor to initialize the ArraySize field. The forgetsearch destructor will call the datalist constructor automatically.

The Search() function is defined in the file bintemp.h:

#ifndef BINTEMPH

#define BINTEMPH

#include "binary.h"

#include "datatemp.h"

template <class Type>

int forgetsearch<Type>::

Search(const Type& Target) const

{

int top=ArraySize-1, bottom=0, middle;

while(top > bottom) {

middle = (top+bottom)/2;

if (Element[middle] < Target)

bottom = middle+1;

else

top = middle;

}

if (top == -1)

return -1;

if (Element[top] == Target)

else

return -1;

}

template <class Type>

int targetsearch<Type>::

Search(const Type& Target) const

{

int top=ArraySize-1, bottom=0, middle;

while(top >= bottom) {

middle = (top+bottom)/2;

if (Element[middle] == Target)

return middle;

else if (Element[middle] < Target)

bottom = middle+1;

else

top = middle-1;

}

return -1;

}

#endif

This function implements the algorithm exactly as it was stated in the previous section.

# 11.5 Efficiency of searching algorithms - counting steps

The two searching algorithms presented in this chapter demonstrate that different methods require different amounts of work to achieve the same ends. The sequential search requires a number of comparisons (on average) that is roughly proportional to the size of the list being searched, while the binary search requires only one extra comparison (on average) when the list size is doubled.

Similar situations exist with the various algorithms that are used to perform other common computing tasks, such as sorting, dealing with trees and graphs, and so on. In order for you to make an intelligent choice of which algorithm to use in a given situation, you need to have some idea of how the efficiencies of algorithms are calculated. A full treatment of algorithm efficiency requires a proficiency in mathematics that we are not requiring of any reader of this book. We will try to convey a feel for how the efficiency of algorithms can be measured without using anything more than basic arithmetic, so that you can at least take an educated guess at the efficiency of an algorithm when you first meet it.

## 11.5.1 Best, worst, and average cases

There are three main measures of efficiency that can be applied to most algorithms: the best, worst, and average cases. For example, in the sequential search algorithm, the best case occurs when the target for which you are searching is the first item in the list, since only one comparison needs to be done. The worst case is when the target is either the last item in the list or is not in the list at all, since the target must be compared with every list key in either of these cases. The average case is found by considering all possible outcomes of a search and averaging the number of comparisons over all these cases.

## 11.5.2 Efficiency of the sequential search

Let us try to estimate the best, worst, and average number of comparisons for a list of length n. As just mentioned, the best case for the sequential search occurs when the target is the first item in the list, since only one comparison must be done. Thus the best case is always one comparison, independent of the list length n.

The worst case occurs when the target is either the last list item or is not present in the list, since both of these cases require n comparisons. Thus the worst case is proportional to the length of the list: double the length of the list and you double the amount of work you need to do.

The average case can be worked out by adding up the number of comparisons that you need to do for all possible outcomes and then dividing by the number of possible outcomes. However, it is more useful if we separate the efficiency estimates for the cases of successful and unsuccessful outcomes of the search. For an unsuccessful search, we know that we always require n comparisons, so the best, worst, and average efficiencies are all the same. For a successful search, the best case requires one comparison, and the worst case requires n comparisons.

What of the average number of comparisons required for a successful search? If we assume that any of the keys in the list is equally likely to be the target for which we are searching, then we would expect that, on average, we would have to look at half the list before we found the target. Thus we can estimate that the average number of comparisons is about n/2.

If you know a bit of algebra it isn’t too hard to work out an exact formula for the average number of comparisons. Doing this shows that the value is (n + 1)/2, which is very close to our estimate of n/2, especially if the list is very long.

It is instructive to test these predictions by actually running the algorithms and counting the number of comparisons for a large number of searches. To this end, we will derive a new class from the searchlist template to test the efficiency of sequential search.

In doing our tests, we shall be concerned only with those comparisons between the target and a list element. In the program itself there are several other comparisons that are done (for example, testing termination conditions in for loops), but we shall ignore those. We want to find out how much work the algorithm itself is actually doing.

The new class will have some extra data fields for storing things like the number of comparisons done in a search, and the average numbers of comparisons for successful and unsuccessful searches. We will need to modify the Search() function to have it count the comparisons.

To calculate an average for the number of comparisons required in a search, we need to run the search a large number of times for various targets and keep some statistics on the outcomes. We will therefore use the constructor for the new class to fill up the array with numbers (rather than reading them in from the keyboard), and then use a random number generator to produce a stream of targets for which we shall search the list and record the number of comparisons required in each case. To separate successful from unsuccessful searches we will do a series of searches for numbers that we know to be in the list, and then another series of searches for numbers that we know are not in the list.

The derived class is in the file srcheff.h:

#ifndef SRCHEFF_H

#define SRCHEFF_H

#include "bintemp.h"

#include <stdlib.h>

#include <time.h>

#include <fstream.h>

class sequentialEff : public searchlist<long>

{

protected:

long Comparisons;

float AverageSuccess, AverageFail;

long NumRuns;

public:

sequentialEff(int arraysize = 100,

long numruns = 100);

virtual int Search(const long& Target);

void TestSearch();

void SaveResults(const char *FileName) const;

};

#endif

This header file includes the file bintemp.h, which contains the template definitions for the binary search class, and also includes in turn the files defining the searchlist class. The other included files are for other features that we shall consider later.

The data fields AverageSuccess and AverageFail are for storing the average number of comparisons required for successful and unsuccessful searches, respectively. NumRuns specifies how many searches should be done to calculate the average values.

The size of the array (recall that the field ArraySize is inherited from searchlist) and number of runs are initialized in the constructor. The Search() function implements the sequential search with additional statements that count the number of comparisons. The function TestSearch() runs NumRuns successful and unsuccessful searches on the list, and calculates AverageSuccess and AverageFail. SaveResults() saves the averages and other data in a file.

The function definitions are:

#include "srcheff.h"

sequentialEff::sequentialEff(int arraysize,

long numruns) :

searchlist<long>(arraysize), NumRuns(numruns)

{

for (int count = 0; count < arraysize; count++)

Element[count] = count;

}

int sequentialEff::Search(const long& Target)

{

for (int element = 0; element < ArraySize; element++)

{

++Comparisons;

if (Element[element] == Target)

return element;

}

return -1;

}

void sequentialEff::TestSearch()

{

int count;

AverageSuccess = AverageFail = 0.0;

// Test successful searches

for (count = 0; count < NumRuns; ++count) {

Comparisons = 0;

Search(random(ArraySize));

AverageSuccess += Comparisons;

}

AverageSuccess /= NumRuns;

// Test unsuccessful searches

for (count = 0; count < NumRuns; ++count) {

Comparisons = 0;

Search(random(ArraySize) + ArraySize);

AverageFail += Comparisons;

}

AverageFail /= NumRuns;

}

void sequentialEff::

SaveResults(const char *FileName) const

{

ofstream SaveFile(FileName, ios::app);

SaveFile << NumRuns << ' ' << ArraySize << ' ' <<

AverageSuccess << ' ' << AverageFail << endl;

SaveFile.close();

}

The constructor loads the Element array with consecutive numbers from 0 to ArraySize, thus ensuring the list is sorted, as will be required for testing the binary search. The Search() function counts the number of comparisons.

The TestSearch() function does NumRuns successful and unsuccessful searches, using a random number generator to produce the targets. Unfortunately, random number generators are not standardized in C++ libraries, so the procedure for generating random numbers may be different in your compiler. The method used in this example is based on the Borland libraries. The random(ArraySize) call generates a random integer between 0 and ArraySize - 1, inclusive. Since these are the numbers we loaded into the Element array in the constructor, we know that all these searches will be successful. Similarly, in the loop that tests unsuccessful searches, the random numbers are generated in the range ArraySize to 2*ArraySize - 1. We know that none of these numbers is in the array, so the search is guaranteed to fail.

The SaveResults() function illustrates how to save data in an external file using C++ streams. First, you must declare and define a variable of type ofstream. The SaveFile variable in SaveResults() is of this type, and may be used in exactly the same way as cout, except that data are stored in a disk file instead of being printed to the screen. The ofstream constructor takes two arguments: a char pointer which points to a string giving the name of the file, and a second flag that indicates how the file is to be accessed. We have specified ios::app for this flag, which means that the data are to be appended to the file. If you want to erase the contents of the file and start writing from scratch, use ios::out instead of ios::app.

Reading data from a file can be done by declaring an ifstream object in a similar way. For example, the declaration

ifstream InFile("input.dat", ios::in);

will initialize an ifstream variable InFile so that data may be read from the disk file input.dat. The format for using an ifstream object is the same as that for using the cin object for reading from the keyboard.

To use file streams in C++, you must include the system header file fstream.h.

Following the opening of the file, NumRuns, ArraySize, AverageSuccess, and AverageFail are written to the file, and then the file is closed.

The main() function which runs the tests is in the file srchtest.cpp:

#include "srcheff.h"

int main()

{

sequentialEff *TestSeq;

int ListSize;

randomize();

for (ListSize = 10; ListSize <= 1000; ListSize += 10)          {

TestSeq = new sequentialEff(ListSize);

TestSeq->TestSearch();

TestSeq->SaveResults("testseq.dat");

delete TestSeq;

}

return 0;

}

A pointer to a sequentialEff object is declared, rather than the object itself, because we will be creating a series of objects, each with a different list size. It is more efficient in terms of memory requirements to have only a single list in use at any one time, so we create a list of a specified size using the new operator, use the list to perform the efficiency test, and then delete the list before testing the next one.

One final comment about the random number generator. Most generators must be initialized before they are used. Otherwise, they will generate the same sequence of random numbers every time the program is run. Again, the methods for initializing the generator vary from one compiler to another. The Borland library provides the randomize() function which does the job for you.

This program was run on lists ranging in length from 10 to 1000. The results are shown in Fig. 11.1.

Fig. 11.1. Efficiency of sequential search.

You can see that the predictions of theory are borne out by the experimental runs. The average number of comparisons for a successful search is roughly half the length of the list, while the number of comparisons required to show that a target is not in the list is equal to the list length.

## 11.5.3 Efficiency of binary search

A similar experiment can be done to determine the efficiency of binary search. First, though, let us see if we can predict the results using simple arguments, as we did with the sequential search.

We know that the binary search looks first at the middle element in a sorted list. If the target lies in the upper half of the list, the lower half is ignored for the remainder of the search. Similarly, if the target lies in the lower half, the upper half is ignored. The process is repeated with the half-list and again with half of the half-list, and so on until we have only one element left. Finally, there is a comparison of this last element with the actual target to see if the target has been found.

We can get an estimate of how many comparisons are required by considering lists whose lengths are powers of 2 (2, 4, 8, 16, 32, and so on). The number of comparisons that is done in the first stage of the algorithm, where the list is being chopped in half at each stage, is equal to the number of times 2 divides the list length. For a list of length 8, for example, 3 divisions will be done, since 8 = 2 ´ 2 ´ 2 = 23. The final comparison with the one remaining element makes a total of 4 comparisons for a list of length 8. For a list whose length is exactly the nth power of 2, there will be n + 1 comparisons required.

For lists with lengths that are not exact powers of 2, we would expect the number of comparisons to be close to that required for the list whose length is the nearest power of 2. For example, for a list of length 1000, we might expect that 10 comparisons would be needed to divide the list to the point where only one element remains (since the nearest power of 2 is 210­ = 1024), with one further comparison to see if that element is the target we are looking for. We would predict therefore, that about 11 comparisons would be needed to locate an element in a list of length 1000. In addition, we would expect that the number of comparisons should be about the same whether the search is successful or unsuccessful.

We can derive a new class from the sequentialEff class above to test the efficiency of binary search. This class is added to the file srcheff.h:

class binaryEff : public sequentialEff

{

public:

binaryEff(int arraysize = 100, long numruns = 100);

int Search(const long& Target);

};

The class binaryEff will use most of the same fields and functions as the sequentialEff class. We need to replace the Search() function so that it implements binary search, and counts the comparisons. The functions required for binaryEff are added to the file srcheff.cpp:

binaryEff::binaryEff(int arraysize, long numruns) :

sequentialEff(arraysize, numruns)

{}

int binaryEff::Search(const long& Target)

{

int top = ArraySize - 1, bottom = 0, middle;

while(top > bottom) {

middle = (top + bottom)/2;

++Comparisons;

if (Element[middle] < Target)

bottom = middle + 1;

else

top = middle;

}

if (top == -1)

return -1;

++Comparisons;

if (Element[top] == Target)

else

return -1;

}

These functions should be self-explanatory if you have studied the original C++ code for the binary search presented earlier in this chapter.

This code is run with the main() function:

#include "srcheff.h"

int main()

{

binaryEff *TestBin;

int ListSize;

randomize();

for (ListSize = 10; ListSize <= 1000; ListSize += 10)

{

TestBin = new binaryEff(ListSize);

TestBin->TestSearch();

TestBin->SaveResults("testbin.dat");

delete TestBin;

}

return 0;

}

The results of running this program on lists ranging in size from 10 to 1000 are shown in Fig. 11.2.

Fig. 11.2. Efficiency of binary search.

You can see that the number of comparisons does increase by 1 each time the list length passes a power of 2 (recall that the powers of 2 are 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ¼). Also, the number of comparisons is about the same for successful and unsuccessful searches.

You may be wondering why the curve for successful searches increases fairly smoothly while that for unsuccessful searches goes up in steps at each power of 2 boundary. The reason lies in the way the tests were done. The numbers used in testing successful searches were chosen randomly from the range of numbers stored in the list. Those numbers used for testing unsuccessful searches are all larger than the largest number in the list. Thus we never examine what happens in the algorithm when a number for which we are searching lies between two numbers in the list. You might like to modify the searching program so that this test is done and see if it smooths out the curve.

The most important thing to notice about these two tests (for sequential and binary search) is how much less work is done by the binary search algorithm, once the list contains more than just a few elements. This seems to indicate that there is some fundamental difference between the two algorithms. We shall explore this idea in the next section.

# 11.6 Efficiency of algorithms - general

## 11.6.1 Classifying algorithms by their efficiency

We saw in the last section that two algorithms for achieving the same result (locating an item in a list) can have very different efficiencies. It is natural to ask whether such differences exist for algorithms in other areas, and whether there is any systematic way of finding and classifying efficiencies.

As you might expect, the answer to all these questions is ‘Yes’. There are various approaches to the study of algorithm efficiency, but since we are not assuming any great mathematical proficiency on the part of the reader, we must stick with heuristic and experimental methods. The general sorts of arguments and methods that we will use were illustrated in the last section, where we gave a simple argument to estimate the efficiencies of both the sequential and binary search algorithms. For some algorithms, such arguments are fairly easy to construct, for others, considerably more difficult. One thing we can always do, though, is a series of computer experiments in which we count the number of steps required to run the algorithm on data sets of varying sizes. We used this method in the last section as well, and managed to produce some plots of the number of steps as a function of the length of the list being searched.

We discovered, both by heuristic argument and by computer experiment, that the average number of comparisons required in using sequential search is directly proportional to the length of the list. Using the same methods, we discovered that the average number of comparisons required in the binary search is proportional to the power to which 2 must be raised to obtain the length of the list (that is, if the list length is 2n, the number of comparisons is proportional to n).

We usually find, either by theoretical argument or by computer experimentation, that the number of steps required by an algorithm depends on some simple expression involving the amount of data being processed. For example, in the case of sequential search, we can say the number C of comparisons is (roughly) equal to half the length L of the list: C = L/2. In the case of the binary search, if the length L of the list can be written as L = 2n, then the number of comparisons is roughly equal to n: C = n.

The most important thing to notice about the efficiency of the sequential search is that C is directly proportional to L. The fact that the scaling factor is 1/2, although useful to know, is not the most important fact. Knowing that C is directly proportional to L means that we know that if the length of the list is doubled, the number of comparisons required will double also; if the length is tripled, the number of comparisons also triples, and so on. In other words, what is important is that C is directly proportional to L, and not what the actual proportionality constant is. The main point of working out the efficiency of an algorithm is to know how it behaves for large amounts of data; in particular, how fast the amount of work increases as the amount of data increases.

We can therefore make an argument for classifying together all algorithms in which the number of steps increases in direct proportion to the amount of data. Such algorithms are called linear algorithms (since the graph of the amount of work versus the amount of data is a straight line, as we saw for the sequential search in the last section).

In a similar way, we can classify together all algorithms that behave like the binary search. These sorts of algorithms are called logarithmic algorithms. If you know how logarithms are defined in mathematics, you will see why this is true. If you don’t know what logarithms are, a brief description is in order.

Consider an expression like the one we used above for the length of a list in terms of a power of 2: L = 2n. The logarithm of L (to base 2) is defined to be n. That is, log L = n, if L = 2n. In words, the (base 2) logarithm of a number is the power to which 2 must be raised to give that number. The logarithm of 2 is therefore 1 (since 21 = 2), the logarithm of 4 is 2 (since 22 = 4), the logarithm of 8 is 3 (since 23 = 8), and so on.

Logarithms of numbers that aren’t exact powers of 2 can also be defined using some mathematical trickery. For example, we can define the logarithm of 5 to be the power to which 2 must be raised to give 5. Since 5 isn’t an exact power of 2, but lies between 4 and 8, you would expect that the logarithm of 5 is somewhere between 2 and 3, and you would be right (it is 2.322, to 3 decimal places). For the purposes of this book, don’t worry about how such ‘weird’ logarithms are calculated, since that requires a fair bit of mathematical knowledge. If you remember that a base 2 logarithm of a number is the power to which 2 has to be raised to get that number, that’s all you need.

The binary search algorithm has an efficiency that can therefore be written as C = log L, where C is the number of comparisons, and L is the length of the list.

One final note about logarithms: if you want to use a calculator to evaluate a base 2 logarithm, you may have to use a two-step procedure. Most calculators don’t have a button for working out base 2 logarithms directly. The most common logarithm buttons are labelled “log” or “ln”. The “log” button gives you a base 10 logarithm, which is the power to which 10 (not 2) must be raised to give a number. For example, the base 10 logarithm of 100 is 2, since 102 = 100, and so on. To get a base 2 logarithm from a base 10 logarithm, divide the base 10 logarithm of the number by the base 10 logarithm of 2. For example, to get the base 2 logarithm of 5, find the base 10 logarithm of 5 by pressing the “log” button on your calculator. The calculator will show the answer as 0.69897. Now divide this number by the base 10 logarithm of 2 (which is 0.30103) to get the base 2 logarithm of 5, which is 2.32193.

## 11.6.2 The big-oh notation

Once you get used to the idea of classifying algorithms by the general way they depend on the amount of data, you will find a shorthand notation for efficiency to be quite handy. We can borrow such a notation from mathematics. We can represent a linear algorithm (one where the number of steps increases in direct proportion to the amount of data) by the notation O(n), which is read “order n”. This notation means that, for ‘large’ values of n (where n is a quantity that measures the amount of data being processed by the algorithm; n was equal to L when we were discussing list lengths above, for example), the number of steps taken by the algorithm is directly proportional to the amount of data being processed.

The restriction of this definition to “large values of n” is imposed because in some cases the exact form of the dependence of the number of steps on the amount of data implied by the notation O(n) doesn’t become accurate until n gets quite large. For example, we mentioned above that the average number of comparisons required by sequential search on a list of length L is (L + 1)/2, which expands to L/2 + 1/2. The extra term of 1/2 means that the number of comparisons isn’t strictly proportional to L. However, when the list gets very long, so that L gets very large, the extra 1/2 fades into insignificance and saying that the number of steps is proportional to L becomes more and more accurate. The notation O(n) thus means that the term that increases the fastest is the one proportional to n. There could be other ‘lower order’ terms (that is, terms that don’t change as fast as n increases), but these will become negligible as n gets large.

In the case of the binary search, the highest order term (the term that increases the fastest) is the logarithmic term, so we say that the binary search is an O(log n) algorithm.

All algorithms can therefore be classified by giving their order, in the form of big-oh notation. To do this, of course, we must first find an expression for the dependence of the number of steps in the algorithm on the amount of data being processed. This is the hard bit. We may be able to do it by working out a formula analytically, by some form of heuristic argument, or by computer experimentation. However we do it, we are interested mainly in the term in this expression that increases the fastest as the amount of data becomes larger.

The most common orders of algorithms are the following, listed in increasing order of complexity:

¨       Constant (O(1)): the number of steps is independent of the amount of data. The best case result for the sequential search is O(1), since if the element for which we are searching is the first element in the list, only one comparison is required no matter how long the list is. Remember, though, that O(1) means that a constant number of steps is required, where the constant number can be any number, not necessarily just one. An algorithm that always requires 15 steps is still an O(1) algorithm.

¨       Logarithmic (O(log n)): algorithms like the binary search.

¨       Linear (O(n)): algorithms like the average case of the sequential search.

¨       Log-linear (O(n log n)): algorithms where the leading term is proportional to the product of the amount of data n by the logarithm of the amount of data (log n). The most efficient sorting algorithms are of this type, as we will see in the next chapter.

¨       Quadratic (O(n2)): algorithms where the number of steps depends on the square of the amount of data. In such algorithms, doubling the amount of data quadruples the amount of work that must be done. Some sorting algorithms are of this type.

Other forms of algorithms exist, but these are the only varieties that we shall meet in this book.

# 11.7 Using a template with a user-defined class -              searching a list of names

Finally in this chapter, we will give an example of a programming technique to which we have alluded several times in previous chapters. We have mentioned that one of the advantages of using a template to define a class is that the class may be used with any data type, even a user-defined class. We pointed out that if a user-defined class is used with a template, the user must ensure that all required operators and functions are present in the user-defined class.

As a concrete example of how this is done, we will present a program in which a binary search is done on an ordered list of people’s names. The class we shall define to represent a person’s name contains two text fields: one for the surname and the other for the first name. A list of names is sorted into alphabetical order using the surname as the principal key. Two names with identical surnames are then sorted using the first name as a secondary key. For example, “Steve Roberts” would come before “Jane Smith” in the list, since “Roberts” precedes “Smith” in alphabetical order. “Jane Smith” would come before “John Smith” since the surnames are the same, but “Jane” precedes “John” in alphabetical order.

The class definition is in the file name.h:

#ifndef NAME_H

#define NAME_H

#include <iostream.h>

#include <string.h>

#include "mydefs.h"

class name

{

private:

char FirstName[20], Surname[20];

public:

name();

BOOL operator <(const name& OtherName) const;

BOOL operator ==(const name& OtherName) const;

friend ostream& operator<<(ostream& OutStream,

const name& OutName);

friend istream& operator>>(istream& InStream,

name& InName);

};

#endif

The class contains the two text fields for first name and surname. Since the class is to be used with the forgetsearch template, we must ensure that all required operators are defined in the name class. We see that we need the comparison operators < and ==, and the overloaded input and output operators << and >>, so we provide these in the class. Since we will be using some functions from the string library to implement these operators, we must include the system string.h header file.

The function definitions are in the file name.cpp:

#include "name.h"

name::name()

{}

BOOL name::operator <(const name& OtherName) const

{

if (strcmp(Surname, OtherName.Surname) < 0)

return TRUE;

else if (strcmp(Surname, OtherName.Surname) > 0)

return FALSE;

else     // Surnames the same; compare first names

return strcmp(FirstName, OtherName.FirstName) < 0;

}

BOOL name::operator ==(const name& OtherName) const

{

return (!strcmp(Surname, OtherName.Surname) &&

!strcmp(FirstName, OtherName.FirstName));

}

istream& operator>>(istream& InStream, name& InName)

{

cout << "Enter surname: ";

InStream.getline(InName.Surname,

sizeof InName.Surname);

cout << "Enter first name: ";

InStream.getline(InName.FirstName,

sizeof InName.FirstName);

return InStream;

}

ostream& operator<<(ostream& OutStream,

const name& OutName)

{

OutStream << OutName.Surname << ", "

<< OutName.FirstName << endl;

return OutStream;

}

The overloaded < operator implements the ordering described above. The two surnames are compared using the strcmp() function from the string library. This function returns -1 if the first string is alphabetically prior to the second, 0 if the two strings are the same, and +1 if the first string is alphabetically after the second. We therefore compare the surnames and return TRUE or FALSE if the two surnames differ, depending on which order they are in, and if the two surnames are equal, we then compare the first names.

The overloaded == operator returns TRUE if both the surnames and the first names of the two strings match. Finally, the overloaded << and >> operators provide simple input and output routines for a name object. Note that these functions are friend functions of the name class, so their definitions do not have the name:: prefix before their names.

Finally, we present a main() function which uses the name class as a parameter in the forgetsearch template, reads in a list of names, and then offers the user a chance to search this list for names entered from the keyboard. The function is in the file namesrch.cpp:

#include "name.h"

#include "bintemp.h"

const int SIZE = 5;

int main()

{

forgetsearch<name> NameList(SIZE);

name NameTarget;

int Location;

cin >> NameList;

cout << NameList;

for (int i = 0; i < 5; i++)

{

cout << "Search for a name in NameList: ";

cin >> NameTarget;

if ((Location = NameList.Search(NameTarget)) != -1)

cout << "Found at index " << Location << endl;

else

}

return 0;

}

Note that we were able to use the forgetsearch template without any modifications, provided that we ensured that all the relevant operators were defined in the name class. The line cin >> NameList; for example, uses the overloaded >> operator in two forms. First, the overloaded form of the operator defined in the forgetsearch template is used to read in the list of names. Each name read in for this list calls the overloaded >> operator from the name class. The line cin >> NameTarget; on the other hand uses the overloaded >> operator from the name class directly. The other overloaded operators (< and ==) defined in the name class are used behind the scenes by the Search() function in the forgetsearch template.

This simple example demonstrates the power of the C++ template, combined with operator and function overloading. Templates for commonly used operations, such as searching and sorting, can be defined, and user-defined classes can be linked into these templates at a later time.

# 11.8 Summary

In this chapter we have studied two searching algorithms: sequential search and binary search. C++ templates for these algorithms were produced.

The main theoretical concepts covered in this chapter are:

¨       The efficiency of an algorithm is measured by counting (theoretically or experimentally) the number of steps it needs to process a certain amount of data.

¨       Different algorithms for accomplishing the same task (such as searching a list) can have very different efficiencies.

¨       The efficiency of an algorithm is classified by finding a simple expression which describes the number of steps taken by the algorithm as a function of the amount of data it processes.

¨       The big-oh notation is used as a shorthand for classifying algorithms.

¨       Algorithms studied in this book range from constant order (O(1)) up to quadratic order (O(n2)).

C++ programming techniques described in this chapter are:

¨       Writing data to and reading data from external files using the fstream library.

¨       Counting the steps in an algorithm as a function of the amount of data it processes. This is an experimental technique that can be used to estimate the efficiency of algorithms.

¨       Using objects of a user-defined class in a template. This example shows how to ensure that the operators required in the template are provided in the user-defined class.

# 11.9 Exercises

1. a. Write a general data template similar to the datalist template in the text, except that the data are stored as a linked list, rather than as an array.

b. Using this new template, write versions of the sequential search and forgetful binary search algorithms.

c. Derive a class from the template in part (b) and use it to calculate the efficiency of the two searching algorithms in a manner similar to that in the text.

2. Redesign the experiment used in the text for calculating the efficiency of the forgetful binary search so that, for unsuccessful searches, numbers less than the smallest number in the list, numbers between numbers in the list, and numbers greater than the largest number in the list are all used. Plot a graph of your results and compare it with the graph given in the text. Do you get a smoother curve?

3. As you will have noticed in question 1, implementing the binary search on a linked list requires many traversals of the list to locate the various elements to use in the comparisons. An alternative algorithm for searching a sorted linked list is as follows:

1. Set pointers Marker and OldMarker to the first data node in the list.

2. While Marker != 0

3. Compare data at location Marker with Target data:

4. If Target == Marker, return indicating target found

5. Else if Target > Marker, save current Marker in OldMarker, advance Marker by step nodes (step is usually >= 2; if step == 1, this algorithm is equivalent to sequential search) and repeat from step 2.

6. Else if Target < Marker, return to location OldMarker and compare the step - 1 nodes forward from that location with Target. If a match is found, return indicating that Target has been found; if no match is found, or a zero pointer is encountered, return indicating that Target has not been found.

The idea behind this algorithm is to use larger steps to do a crude initial search through the list. Once a pair of markers localizing the section of the list where Target may be found are identified, that section of the list is searched in detail.

Implement this algorithm for a linked list and run some experiments to calculate its efficiency. Try several values of step, and compare your results with the binary search.

4. As mentioned in the text, there is an alternative form of the binary search which tests at each halving of the list whether the node at the division point is equal to the target. If not, the relevant half of the list is then searched in the same manner. Implement this form of the binary search for an array, and run an experiment to calculate its efficiency. How does it compare with the forgetful binary search? The result is surprising, since it would seem that by checking for the target at each stage of the algorithm rather than only at the end, you should be able to shorten the search for a large number of targets. However, for any list of reasonable size, most of the elements will not be found until you have reduced the list to one or two elements anyway. The gain for a few list elements is more than offset by the fact that you must do two comparisons, rather than one, at each step.