13 Standard algorithms
Each new program has its own challenges, its own unique features. But the same old
subproblems keep recurring. So, very often at some point in your program you will
have to search for a key value in an ordered collection, or sort some data. These
subproblems have been beaten to death by generations of computer theoreticians and
programmers. The best approaches are now known and defined by standard algorithms.
This chapter presents four of these. Section 13.1 looks at searching for key values.
The next three sections explore various "sorting" algorithms.
The study of algorithms once formed a major part of sophomore/junior level studies
in Computer Science. Fashions change. You will study algorithms in some subsequent
subjects but probably only to a limited extent, and mainly from a theoretical perspective
while learning to analyse the complexity of programs.
FINDING THE RIGHT ELEMENT: BINARY SEARCH
The code in the "keyword picker' (the example in section 12.4) had to search linearly
through the table of keywords because the words were unordered. However, one often
has data that are ordered. For instance you might have a list of names:
"Tomlinson", "Torrecilla", …
If you are searching for a particular value, e.g. Sreckovic, you should be able to take
advantage of the fact that the data are ordered. Think how you might look up the name
in a phone book. You would open the book in the middle of the "subscriber" pages to
find names like "Meadows". The name you want is later in the alphabet so you pick a
point half way between Meadows and Zylstra, and find a name like Terry. Too far, so
split again between Meadows and Terry to get to Romanows. Eventually you will get
to Sreckovic. May take a bit of time but it is faster than checking of Aavik, Abbas,
Subject to a few restrictions, the same ge