Pseudocode, Insertion Sort and Loop Invariant

Pseudocode

In Chapter 2 of Introduction to Algorithms, the authors introduce pseudocode.  Pseudocode is a way to describe algorithms.  Pseudocode is not computer code and is not typically concerned with issues of software engineering (e.g., data abstraction, modularity, and error handling).  The pseudocode conventions in this book are:

• Syntax/format:
  • Indentation indicates block structure.  The body of a looping constructs while, for, and repeat-until and the if-else conditional construct are indented in the same block.  Moving into or out of an indentation level indicates beginning or ending of a construct.
  • The loop counter retains its value after exiting the loop, unlike some situations that arise in C++, Java, and Pascal. Thus, immediately after a for loop, the loop counter’s value is the value that first exceeded the for loop bound.
  • We use the keyword to when a for loop increments its loop counter in each iteration, and we use the keyword downto when a for loop decrements its loop counter. When the loop counter changes by an amount greater than 1, the amount of change follows the optional keyword by.
  • The symbol “//” indicates that the remainder of the line is a comment.
  • We access array elements by specifying the array name followed by the index in square brackets. For example, A.[i] indicates the ith element of the array A. The notation “..” is used to indicate a range of values within an array. Thus, A[1..j]  indicates the subarray of A consisting of the first j elements A.[1],A.[2],…,A.[j].
• Data can be objects, which are composed of attributes. We access an attribute using the syntax of many object-oriented programming languages: the object name, followed by a dot, followed by the attribute name. E.g., an array is an object with the attribute length indicating how many elements it contains. A.length specifies the number of elements in an array A.
• Assignment:
  • Variables are local to the given procedure. We shall not use global variables without explicit indication.
  • A multiple assignment of the form i = j = e assigns to both variables i and j the value of expression e; it should be treated as equivalent to the assignment j = e followed by the assignment i = j.
  • A variable representing an array or object as a pointer to the data representing the array or object.  E.g., x = y results in the variable x pointing to array/object y, along with all its attributes.  Therefore, as y changes x also changes.
  • A pointer that points to no object has the value NIL.
• A called procedure has parameters that are passed on to it by value, unlike a variable.  The called procedure receives its own copy of the parameters, and if it assigns a value to a parameter, the change does not take effect outside the procedure.  But individual assignments (a specified attribute of an object or a specified individual array element) do take effect outside the called procedure.
• A return statement immediately transfers control back to the point of call in the calling procedure. Most return statements also take a value to pass back to the caller. Our pseudocode differs from many programming languages in that we allow multiple values to be returned in a single return statement.
• The boolean operators “and” and “or” short circuit. That is, when we evaluate the expression “x and y” we first evaluate x. If x evaluates to FALSE, then the expression cannot evaluate to TRUE, and so we do not evaluate y.  Similarly, in the expression “x or y” we evaluate the expression y only if x evaluates to FALSE.
• The keyword error indicates that an error occurred because conditions were wrong for the procedure to have been called.

Pseudocode are explained below for solving the sorting problem as discussed in my last post.

Insertion Sort

The insertion sort algorithm can be described in English as:  separate the given list of numbers into two list: one sorted, one unsorted.  The sorted list initially contains the first element of the given list while the unsorted list initially contains the rest of the elements.  In each step, take the first element from the unsorted list, compare it with each element of the sorted list, starting from the right most (or left most) element.  Stop comparing and insert the element right after the element it should follow.

The pseudocode for insertion sort of an array A is on p.18 of the book.  In this post I talk about writing this in OCaml.  I explain the code in my own words below:

Line 1: started the for loop that initiates with j = 2 and terminates when j equals the length of the array.  At the beginning of each loop, the subarray consists of j-1 elements of the originally array, but in sorted order.

Line 2 [in for loop started in Line 1]: set key to be the element to be sorted.  The first element to be sorted is the second element (hence the for loop initiates at j = 2) because insertion sort compares the element to be sorted with the sorted element(s) to determine the order.  When j = length of the array, the element to be sorted is the last element.  Therefore, the algorithm terminates correctly.

Line 3: A comment explaining the following lines.

Line 4: set i to be the index of the element that was last sorted.

Line 5: started a while loop that only execute when i>0, and the element to be sorted is smaller than the last sorted element.  That is, the while loop only execute if the element to be sorted is smaller than the element right before it.  If it is bigger than the element right before it, then Line 8 is executed.  If not, Line 6 and 7 are executed.  The loop terminates when i=0, i.e., when the first element of the array was compared to key.

Line 6 and 7[in while loop started in Line 5]: Repeated put the ith element in the (i+1)th element, because the element to be sorted (key) is smaller than the ith element.  Decrease i (the element to be compared to key) by 1.

Line 8 [for loop started in Line 1 ends after this line]: put the element to be sorted (key) in the (i+1)th element.

Loop Invariant

Loops are an important part of an algorithm.  For an algorithm to be correct, we show that we have loop invariant, by showing:

1. Initialization: The first iteration of the loop is correct.  That is, the first loop achieve the desired property.
2. Maintenance: It maintains correctness and achieve the desired property before the next iteration of the loop.
3. Termination: When the loop terminates, the algorithm is correct.

In the next post I will discuss how one analyses an algorithm.