Keeping it Small and Simple

2007.05.20

Understanding algorithms for novice programmers

Filed under: Algorithms, Computer Programming — Lorenzo E. Danielsson @ 19:12

Q: what two tools are essential for a novice programmer trying to understand how algorithms work?
A: pen and paper.

I think that one of the major hurdles for novice programmers comes when they have managed to grasp the syntax of a programming language and move on to actually trying to do something with the language. That is when the concept of algorithms comes in. The first step for the programmer is to learn about existing algorithms and to try to understand them. Already here many people start to find difficulties.

In the old days, when much of the world was ruled by the Emperor of Rome and I was learning how to program, we were encouraged to always work through algorithms on a piece of paper. Going through the algorithm step by step really helps in understanding what the code does. So my usual advice to new programmers is this: always work through parts of the code that you don’t understand on paper. If you still don’t understand the code, go through it again, and again, until you understand exactly what is happening.

Very few people seem to listen to this advice (I guess it is more fun to write code, even if you are just copying it off a web site). The people who don’t often come back to me later to tell me that they find programming difficult. Well, if you want learn how to swim, you really have to jump into the water. If somebody tells you this, and you don’t listen, can you then blame the water for the fact that you cannot swim?

Let’s look at a simple example: bubble sort. It is not the best of sorting routines, but it is, or at least was, the first sorting algorithm that most people learn. It’s also trivial so it makes a good example. Below is a simple implementation of bubble sort, written in C (the language is unimportant, I could have given the example in Pascal and the principle would still have been the same).

 1 #include <stdio.h>
 2 
 3 #define ARRAYLEN 10
 4 
 5 int main(int argc, char **argv)
 6 {
 7     int nums[] = { 7, 2, 6, 10, 1, 9, 5, 8, 4, 3 };
 8     int i, j, tmp;
 9 
10     for (i = 0; i < ARRAYLEN-1; ++i) {
11         for (j = i+1; j < ARRAYLEN; ++j) {
12             if (nums[i] > nums[j]) {
13                 tmp = nums[i];
14                 nums[i] = nums[j];
15                 nums[j] = tmp;
16             }
17         }
18     }
19 
20     for (i = 0; i < ARRAYLEN; ++i)
21         printf("%dn", nums[i]);
22 
23     return 0;
24 }

Anybody who has even the slightest programming experience should be able to follow what the code does, from a syntactical point of view. But let’s try to understand what the code does, that is, what results are produced. So go and grab a notebook and a pen.

The lines 10-18 are where the integers are sorted. This is the part of the code that we need to analyze. First of all, draw a small table, two rows and ten columns. You will draw this again, several times. In the first row you write down the index values of the array. That would be 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. In the second row you fill in the number that occupies each array element at the start of the program. Now you have your start condition.

During the course of the program the integers in the array will be thrown around until finally they are sorted from the lowest number to the highest. Now you want to understand why that happens. We can see that we have an iterator, i, that loops through the values 0 to the second-to-last element of the array. On your paper, jot down that i is 0 (zero).

Next we have an inner loop where the iterator j loops through the values i+1 up to the last element of the array. On your piece of paper, write down that j is 1.

The next code block compares the value held in nums[i] with that of nums[j]. In the first iteration of both loops, that means we are comparing the value of nums[0] with that of nums[1] (look at your paper and you should see i = 0, j = 1 there). The values of these are 7 for nums[0] and 2 for nums[1]. Since 7 is larger than 2 the if statement evaluates to true and its code block is executed.

What happens in the code block is that two variables, nums[0] and nums[1] exchange values. In order to do that we proceed as follows: 1. copy the value of nums[0] to a temporary variable, 2. copy the value of nums[1] to nums[0], 3. copy the old value of nums[0] to nums[1]. In step 2 we overwrite the value of nums[0], that is why we need to store it away to a temporary variable.

What has happened is the first two array elements have swapped values. So draw the array table once more. This time array element 0 should hold the number 2, and array element 1 should hold the number 7.

The next thing that will happen is that j will be incremented by 1 (i will only be incremented once the inner loop completes). Check if the control condition is still true. It is. The value of j is now 2, and the control condition states that the loop should continue as long as j is less than ten.

The value of nums[0] (which is now 2) will now be compared to that of nums[2] (6). This time, 2 is less than 6, so the if statement evaluates to false. We increase j by one and check if the loop condition is true. The program continues like this until j has reached 10. Then the inner loop completes.

If you have been following along with your pen and paper through all the steps of your inner loop, then your last array table should contain the number 1 in array position 0. What that means is that after one iteration of the outer loop, the first array position contains the lowest value in the array.

Now it is time to increment i by 1. On your paper you write down that i is now 1. Next we start a new cycle of the inner loop, so you write down j = 2 (i+1) on your paper. For each iteration of the inner loop, we again go through the comparison and swap values if the condition nums[i] > nums[j] is true. If you look at your array table after the second iteration of the outer loop, the first two array elements should contain 1 and 2.

By the time you have gone through the last iteration of the outer loop you will hopefully have gained a good understanding of how the bubble sort algorithm works. Writing it is trivial, copying it from somebody else even more so. But in order to be a programmer you don't need to just be able to type code and get it to run, you need to understand it as well.

Stepping through code in this way also gives you the opportunity to test a few "what ifs". Suppose, for example, you didn't understand why the start value of j should be i+1 and not i. Well, then you could test it. By writing down all the values and comparisons that are done step-by-step you will soon see that that would introduce a redundant comparison when a value is compared with itself.

You may notice that it takes quite a bit of time to analyze a piece of code in this way. But it's well worth it, especially when you apply the principle to more complex algorithms where it is not so apparent what the code does. And remember, in order to learn programming (or any other skill for that matter), you must be ready to sacrifice some time and effort.

Create a free website or blog at WordPress.com.