
Lecture 22: Algorithms


Algorithm
The term algorithm (pronounced ALgorithum) is a procedure or formula
for solving a problem. The word derives from the name of the
mathematician,
Mohammed ibnMusa AlKhowarizmi, who was part of the royal court in
Baghdad
and who lived from about 780 to 850 AD.
(http://searchvb.techtarget.com)
Sorting
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
integers
of determined length N and we want to sort them. How we are going to do
that?
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
will
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
first place.
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
for
our array.

Bubble sort
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
bubbles
in water. Let us implement this algorithm in PASCAL. Let's first
put the idea into a socalled flow diagram. 

Flow diagram of the Bubble sort algorithm. [i]
signifies array element i.

In this flow diagram we can already distinguish a little bit of
programming.
We can see at least two loops: one with i to check if two consecutive
elements
are ordered and one loop which repeats until the entire array is
sorted.
Apart from tis there is an instruction for exchanging two elements.
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
ordered:
if n[i] < n[i+1] then ...
2) To exchange two numbers is also not
difficult.
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
we need
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
declare
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:
repeat
change := FALSE; (* no changes
so far in this pass *)
for i := 1 to N1 do (* check all
consecutive pairs: *)
if n[i]>n[i+1] (*
not ordered? *)
begin
(* exhange the two numbers: *)
temp := n[i];
n[i] := n[i+1];
n[i+1] := temp;
(* and signal there was a change: *)
change := TRUE;
end;
until NOT change;
Speed
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
proportional
to the number of times an element is read, we can say the following:
The Bubble sort algorithm has to

minimally has to go once through the array, hence read
2*(N1)
numbers

maximally has to go N1 times
through the array, hence read 2*(N1)^{2}
numbers.

on the average: N^{2}N
(the average of the two numbers above)
with N the array size.
In comparison, the other algorithm given in this chapter would have

minimally has to go through the array N times, but each
time
read a little less (the first time it has to read all N elements, the
second
time only starting from element 2, then from element 3, etc.), hence
read
N + (N1) + (N2)
+ (N3) ... 1 = N^{2}/2 numbers

The program always has to read the same amount of numbers,
independent
of the distribution of the numbers. Therefore, maximally it
also
has to read N^{2}/2 numbers.

on the average: N^{2}/2 (the average of the two
numbers
above)
Which of the two algorithms is more efficient? For large numbers, for
example
100, the second one becomes more and more efficient (5000 vs. 9900).
Also
note that in the Bubble sort algorithm we have more exchanges of
numbers.
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
will
take N1 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 Quicksort (which falls
outside
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
algorithms
in general.
Peter Stallinga.
Universidade
do Algarve, 6 Maio 2002