Algorithmics - The Computing Universe: A Journey through a Revolution - page 90

Fig. 5.5. An example of the bubble
sort algorithm. This example works by
exchanging adjacent names if they are
out of order, starting from the bottom of
the list, and continuing until the bubble
of paired names has reached the top.
This is repeated until all items are sorted
correctly.

Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8

Bob Bob Bob Bob Bob Bob Bob Alice

Ted Ted Ted Ted Ted Ted Alice Bob

Alice Alice Alice Alice Alice Alice Ted Ted

Pat Pat Pat Pat Eve Eve Eve Eve

Joe Joe Joe Eve Pat Pat Pat Pat

Fred Fred Eve Joe Joe Joe Joe Joe

May Eve Fred Fred Fred Fred Fred Fred

Eve May May May May May May May

in 1945 and uses a fundamental technique of computer science called divide-
and-conquer . We begin by splitting our eight-name list into two halves, so that
we have two lists of four names. We then split each half again into two lists
of two names. We order each of the pairs of names and then merge the sorted
pairs. The merge is done by repeatedly comparing the characters at the head of
each list and sending the alphabetically lower item to the output. We complete
the sort by merging the two sorted lists of four names in the same way. The dia-
gram in Figure 5.6 illustrates how the merge sort algorithm works.
In programming the merge sort algorithm, we can write the program using
“recursion” for the divide phase, creating a subroutine calling itself a number
of times. In this case, we can introduce a subroutine called “Divide” and use it
to split the list into two halves. If there are only two elements left in the list, it
returns them in alphabetical order; if there are more than two elements, the
Divide subroutine calls itself and repeats the process. This carries on until there
are only one or two elements left in the divided list. The use of recursion is a
very powerful programming technique much loved by computer scientists. The
merge phase can also be programmed recursively using a Merge subroutine.
We will compare the efficiencies of some algorithms later in this chapter, in
the section on complexity theory.

Graph problems

We are familiar with the use of routing algorithms from our GPS navigation
systems. Indeed the systems are becoming so reliable that we are fast approach-
ing a time when finding our way by reading a paper map will be a lost art! All
we do to find the shortest route from A to B is to enter the start and end points
in the car navigation system. How do computers solve such problems? The solu-
tion uses another branch of mathematics invented by Euler: “graph theory.”
The city of Königsberg in Prussia - now Kaliningrad, Russia - was famous
for a long-standing puzzle in mathematics. The city is located on both sides of
the Pregel River, and there are two large islands in the river connected to the
mainland by seven bridges ( Fig. 5.7a ). The seven bridges problem was to find a
walk through the city that would cross each bridge only once. In 1735, Euler