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
cout <<
"Not found.\n";
}
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)
return top;
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)
return top;
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
cout <<
"Not found.\n";
}
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:
¨ Overloading the << and >>
input/output operators using friend functions.
¨
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.