Lecture 22: Algorithms
The term algorithm (pronounced AL-go-rith-um) is a procedure or formula
for solving a problem. The word derives from the name of the
Mohammed ibn-Musa Al-Khowarizmi, who was part of the royal court in
and who lived from about 780 to 850 AD.
For our lectures it means that before we even touch the computer we are
going to design a method for solving the problem. As an example we use
the problem of sorting of an array. Imagine we have an array of
of determined length N and we want to sort them. How we are going to do
The figure shows an array of 10 elements that we are going to sort.
Without looking at the details, we for example can have the ideas:
Go through the list. If two consecutive elements are not ordered we
exchange them. Repeat doing this until the list is ordered. The figure
below gives the first couple of steps.
- Go through the list, find the smallest element. Put this in the
Then find the smallest of the rest. Put this in the second place, etc.
Repeat this N times. The figure below shows the fist couple of steps
These are two examples of algorithms. The first one is normally refered
to as "Bubble sort", because it resembles the slowly moving up of air
in water. Let us implement this algorithm in PASCAL. Let's first
put the idea into a so-called flow diagram.
In this flow diagram we can already distinguish a little bit of
We can see at least two loops: one with i to check if two consecutive
are ordered and one loop which repeats until the entire array is
Apart from tis there is an instruction for exchanging two elements.
Flow diagram of the Bubble sort algorithm. [i]
signifies array element i.
Now we are going to look at the details. We will program the three
distinct parts of the figure above. Assume we have an array n[1..N]
as presented in the figure above.
1) To check if two consecutive numbers are
if n[i] < n[i+1] then ...
2) To exchange two numbers is also not
We can do this in the following way:
n[i] := n[i] + n[i+1];
n[i+1] := n[i] - n[i+1];
n[i] := n[i] - n[i+1];
Although this method really exchanges two numbers (check this), it
is a little bit clumsy. Normally we exchange two numbers by using a new
variable for temporarily storing information:
temp := n[i];
n[i] := n[i+1];
n[i+1] := temp;
3) To check if the entire array is ordered
to use a variable that saves the information if any exchange took place
in the previous cycle of checking all consecutive pairs. For this we
a variable change that will be TRUE
when there was an exchange in the last pass of the array.
With this, the complete procedure becomes:
change := FALSE; (* no changes
so far in this pass *)
for i := 1 to N-1 do (* check all
consecutive pairs: *)
if n[i]>n[i+1] (*
not ordered? *)
(* exhange the two numbers: *)
temp := n[i];
n[i] := n[i+1];
n[i+1] := temp;
(* and signal there was a change: *)
change := TRUE;
until NOT change;
In the analysis of our algorithm we can also say something about
the speed, the efficiency of our method. What are the minimum, maximum
and average execution times. If we consider that the execution is
to the number of times an element is read, we can say the following:
The Bubble sort algorithm has to
with N the array size.
minimally has to go once through the array, hence read
maximally has to go N-1 times
through the array, hence read 2*(N-1)2
on the average: N2-N
(the average of the two numbers above)
In comparison, the other algorithm given in this chapter would have
Which of the two algorithms is more efficient? For large numbers, for
100, the second one becomes more and more efficient (5000 vs. 9900).
note that in the Bubble sort algorithm we have more exchanges of
This is easy to see why. If a number is all the way at the other end of
the array, it has to move its way slowly up to the other side. This
take N-1 exchanges. In the other algorithm,
the value is copied only once. In fact, Bubble sort is one of the most
inefficient algorithms. Probably the best is Quick-sort (which falls
the scope of this lecture). The reason to use Bubble sort is that it is
a very elegant algorithm and very useful for explaining sorting or
minimally has to go through the array N times, but each
read a little less (the first time it has to read all N elements, the
time only starting from element 2, then from element 3, etc.), hence
N + (N-1) + (N-2)
+ (N-3) ... 1 = N2/2 numbers
The program always has to read the same amount of numbers,
of the distribution of the numbers. Therefore, maximally it
has to read N2/2 numbers.
on the average: N2/2 (the average of the two
do Algarve, 6 Maio 2002