Lecture 22: Algorithms

Algorithm

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 mathematician, Mohammed ibn-Musa Al-Khowarizmi, 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 so-called 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 N-1 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*(N-1) numbers
maximally has to go N-1 times through the array, hence read 2*(N-1)² numbers.
on the average: N²-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 + (N-1) + (N-2) + (N-3) ... 1 = N²/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 numbers.
on the average: N²/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 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 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