# 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. __ATA.cmd.push(function() { __ATA.initDynamicSlot({ id: 'atatags-26942-5e4bb3d5f3c3e', location: 120, formFactor: '001', label: { text: 'Advertisements', }, creative: { reportAd: { text: 'Report this ad', }, privacySettings: { text: 'Privacy settings', } } }); }); ```
``` Comments (4) ```
``` ```
``` Pages About Me Blogroll Free Gamer Faneshi Members Ben’s Blog Edem’s Blog George’s blog Henry’s blog Odzangba’s blog Ziggy’s blog Politics Desertpeace For What It’s Worth Freedom Universal People’s Geography Categories Accra.rb Alfresco Algorithms Anarchism Battle for Wesnoth Blogs c programming Chinese Commodore 64 Computer Games Computer Programming CSS Debian Direct Action Document Processing Documentaries Emacs Family Game Programming Ghana Graphics Programming Health History HTML Humor Japanese Java Programming jboss Joomla JRuby Linguistics Literature Mail clients Mathematics Memories Midi Movies Music MySQL News Object-oriented programming Open Source PDF Perl Programming Personal Philosophy PHP Programming Politics programming Programming tools Pygame Pygame Tutorial Python Programming Python Tutorial Rants Religion Retrogames Revision Control Ruby Programming Rubygame Rubygame Tutorial Sex Software Sports SQL Sverige Sweden Swedish Tech News Technology Toftbyn Uncategorized Utilities Vim Web Sites Wordpress X Windows Zimbra Zsh Search for: Archives April 2008 March 2008 February 2008 January 2008 December 2007 September 2007 August 2007 July 2007 June 2007 May 2007 Meta Register Log in Entries feed Comments feed WordPress.com Blog at WordPress.com. ```
``` var WPGroHo = {"my_hash":""}; //initialize and attach hovercards to all gravatars jQuery( document ).ready( function( \$ ) { if (typeof Gravatar === "undefined"){ return; } if ( typeof Gravatar.init !== "function" ) { return; } Gravatar.profile_cb = function( hash, id ) { WPGroHo.syncProfileData( hash, id ); }; Gravatar.my_hash = WPGroHo.my_hash; Gravatar.init( 'body', '#wp-admin-bar-my-account' ); }); ( function () { var setupPrivacy = function() { var \$ = window.jQuery; if ( ! \$ ) return; // jQuery required \$( document ).ready( function() { // Minimal Mozilla Cookie library // https://developer.mozilla.org/en-US/docs/Web/API/Document/cookie/Simple_document.cookie_framework var cookieLib = {getItem:function(e){return e&&decodeURIComponent(document.cookie.replace(new RegExp("(?:(?:^|.*;)\\s*"+encodeURIComponent(e).replace(/[\-\.\+\*]/g,"\\\$&")+"\\s*\\=\\s*([^;]*).*\$)|^.*\$"),"\$1"))||null},setItem:function(e,o,n,t,r,i){if(!e||/^(?:expires|max\-age|path|domain|secure)\$/i.test(e))return!1;var c="";if(n)switch(n.constructor){case Number:c=n===1/0?"; expires=Fri, 31 Dec 9999 23:59:59 GMT":"; max-age="+n;break;case String:c="; expires="+n;break;case Date:c="; expires="+n.toUTCString()}return"rootDomain"!==r&&".rootDomain"!==r||(r=(".rootDomain"===r?".":"")+document.location.hostname.split(".").slice(-2).join(".")),document.cookie=encodeURIComponent(e)+"="+encodeURIComponent(o)+c+(r?"; domain="+r:"")+(t?"; path="+t:"")+(i?"; secure":""),!0}}; var setDefaultOptInCookie = function() { var value = '1YNN'; cookieLib.setItem( 'usprivacy', value, 365 * 24 * 60 * 60, '/', '.rootDomain' ); }; var setCcpaAppliesCookie = function( value ) { cookieLib.setItem( 'ccpa_applies', value, 24 * 60 * 60, '/', '.rootDomain' ); } var maybeCallDoNotSellCallback = function() { if ( 'function' === typeof window.doNotSellCallback ) { return window.doNotSellCallback( \$ ); } return false; } var usprivacyCookie = cookieLib.getItem( 'usprivacy' ); if ( null !== usprivacyCookie ) { maybeCallDoNotSellCallback(); return; } var ccpaCookie = cookieLib.getItem( 'ccpa_applies' ); if ( null === ccpaCookie ) { \$.ajax({ type: 'GET', dataType: "json", cache: false, url: 'https://public-api.wordpress.com/geo/', success: function( data ) { var ccpa_applies = data['region'] && data['region'].toLowerCase() === 'california'; setCcpaAppliesCookie( ccpa_applies ); if ( ccpa_applies ) { if ( maybeCallDoNotSellCallback() ) { setDefaultOptInCookie(); } } }, error: function() { setCcpaAppliesCookie( true ); if ( maybeCallDoNotSellCallback() ) { setDefaultOptInCookie(); } }, } ); } else { if ( ccpaCookie === 'true' ) { if ( maybeCallDoNotSellCallback() ) { setDefaultOptInCookie(); } } } } ); }; if ( window.defQueue && defQueue.isLOHP && defQueue.isLOHP === 2020 ) { defQueue.items.push( setupPrivacy ); } else { setupPrivacy(); } } )(); Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use. To find out more, including how to control cookies, see here: Cookie Policy var actionbardata = {"siteID":"1086070","siteName":"Keeping it Small and Simple","siteURL":"http:\/\/lorenzod8n.wordpress.com","icon":"<img alt='' src='https:\/\/s2.wp.com\/i\/logo\/wpcom-gray-white.png' class='avatar avatar-50' height='50' width='50' \/>","canManageOptions":"","canCustomizeSite":"","isFollowing":"","themeSlug":"pub\/silver-black","signupURL":"https:\/\/wordpress.com\/start\/","loginURL":"https:\/\/wordpress.com\/log-in?redirect_to=https%3A%2F%2Florenzod8n.wordpress.com%2F2007%2F05%2F20%2Funderstanding-algorithms-for-novice-programmers%2F&signup_flow=account","themeURL":"","xhrURL":"https:\/\/lorenzod8n.wordpress.com\/wp-admin\/admin-ajax.php","nonce":"a75d6e1c62","isSingular":"","isFolded":"","isLoggedIn":"","isMobile":"","subscribeNonce":"<input type=\"hidden\" id=\"_wpnonce\" name=\"_wpnonce\" value=\"4b256712dd\" \/>","referer":"https:\/\/lorenzod8n.wordpress.com\/category\/algorithms\/","canFollow":"1","feedID":"14451208","statusMessage":"","customizeLink":"https:\/\/lorenzod8n.wordpress.com\/wp-admin\/customize.php?url=https%3A%2F%2Florenzod8n.wordpress.com%2Fcategory%2Falgorithms%2F","i18n":{"view":"View site","follow":"Follow","following":"Following","edit":"Edit","login":"Log in","signup":"Sign up","customize":"Customize","report":"Report this content","themeInfo":"Get theme: Silver is the New Black","shortlink":"Copy shortlink","copied":"Copied","followedText":"New posts from this site will now appear in your <a href=\"https:\/\/wordpress.com\/read\">Reader<\/a>","foldBar":"Collapse this bar","unfoldBar":"Expand this bar","editSubs":"Manage subscriptions","viewReader":"View site in Reader","viewReadPost":"View post in Reader","subscribe":"Sign me up","enterEmail":"Enter your email address","followers":"Join 32 other followers","alreadyUser":"Already have a WordPress.com account? <a href=\"https:\/\/wordpress.com\/log-in?redirect_to=https%3A%2F%2Florenzod8n.wordpress.com%2F2007%2F05%2F20%2Funderstanding-algorithms-for-novice-programmers%2F&signup_flow=account\">Log in now.<\/a>","stats":"Stats"}}; ( 'fetch' in window ) || document.write( '<script src="https://s0.wp.com/wp-includes/js/dist/vendor/wp-polyfill-fetch.min.js?m=1573572739h&#038;ver=3.0.0"></' + 'ipt>' );( document.contains ) || document.write( '<script src="https://s1.wp.com/wp-includes/js/dist/vendor/wp-polyfill-node-contains.min.js?m=1540208548h&#038;ver=3.26.0-0"></' + 'ipt>' );( window.FormData && window.FormData.prototype.keys ) || document.write( '<script src="https://s1.wp.com/wp-includes/js/dist/vendor/wp-polyfill-formdata.min.js?m=1550600082h&#038;ver=3.0.12"></' + 'ipt>' );( Element.prototype.matches && Element.prototype.closest ) || document.write( '<script src="https://s2.wp.com/wp-includes/js/dist/vendor/wp-polyfill-element-closest.min.js?m=1540208548h&#038;ver=2.0.2"></' + 'ipt>' ); // <![CDATA[ (function() { try{ if ( window.external &&'msIsSiteMode' in window.external) { if (window.external.msIsSiteMode()) { var jl = document.createElement('script'); jl.type='text/javascript'; jl.async=true; jl.src='/wp-content/plugins/ie-sitemode/custom-jumplist.php'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(jl, s); } } }catch(e){} })(); // ]]> _tkq = window._tkq || []; _stq = window._stq || []; _tkq.push(['storeContext', {'blog_id':'1086070','blog_tz':'0','user_lang':'en','blog_lang':'en','user_id':'0'}]); _stq.push(['view', {'blog':'1086070','v':'wpcom','tz':'0','user_id':'0','subd':'lorenzod8n'}]); _stq.push(['extra', {'crypt':'UE5XaGUuOTlwaD85flAmcm1mcmZsaDhkV11YdWFnNncxc1tjZG9XVXhRREQ/V0xPZ1hKXy9VOT9ucVYmanZ5TjFVZzFfYTRHREkrXUE1LXMmRE1OaVFFM1lib2Y5dlVpd0cxTEYvWFs0MnMlbUNWVXx5M35oL1hhdV1ZMjhYfGViSC1nJUFwNkkvQk9jb1VNSEFfdFBPdl9bcG05alg2Q0ZOSz9nQ1AueTVQNVRjQ3QlNUtldFJpaktaSE4rQ2E/TX41anA/VisxbF0rd09naFVUU0NPSldfSGpdVCZ6bSxwVVozNm5JTFBFOTZoLUtFNGdSNmU0ZVhZMEw='}]); _stq.push([ 'clickTrackerInit', '1086070', '0' ]); if ( 'object' === typeof wpcom_mobile_user_agent_info ) { wpcom_mobile_user_agent_info.init(); var mobileStatsQueryString = ""; if( false !== wpcom_mobile_user_agent_info.matchedPlatformName ) mobileStatsQueryString += "&x_" + 'mobile_platforms' + '=' + wpcom_mobile_user_agent_info.matchedPlatformName; if( false !== wpcom_mobile_user_agent_info.matchedUserAgentName ) mobileStatsQueryString += "&x_" + 'mobile_devices' + '=' + wpcom_mobile_user_agent_info.matchedUserAgentName; if( wpcom_mobile_user_agent_info.isIPad() ) mobileStatsQueryString += "&x_" + 'ipad_views' + '=' + 'views'; if( "" != mobileStatsQueryString ) { new Image().src = document.location.protocol + '//pixel.wp.com/g.gif?v=wpcom-no-pv' + mobileStatsQueryString + '&baba=' + Math.random(); } } ```