layout: archive style: /css/static.css —

Pseudo-code and an R Implementation

The “bubble sort” algorithm is a procedure for sorting. If the input is a collection of random letters, the following “pseudo-code” provides a set of instructions that will lead to sorting the collection alphabetically. To test that the steps will succede, pretend to “compute” the procedure for the array of letters ['q', 'e', 'd'].

1. let A refer to some collection of letters
2. let n refer to the number of letters in A
3. for i referring to any positive integer, let A[i] refer to the i^th letter in A
4. let swapped refer to ‘No’
5. let i refer to 0
6. let i refer to the value of i + 1
7. if A[i + 1] comes before A[i] in the alphabet, then swap them in the collection A and let swapped refer to ‘Yes’
8. if i is less than n go back to step 6, but otherwise continue to step 9.
9. if swapped refers to ‘Yes’, go back to 4, otherwise A is in alphabetical order

The following is a script in the R programming language that implements bubble sort, beginning from the assumption that A already refers to an array of letters.

n <- length(A)
swapped <- TRUE
while (swapped) {
    swapped <- FALSE
    for (i in seq(1, n - 1)) {
        if (A[i+1] < A[i]) {
            a <- A[i+1]
            A[i+1] <- A[i]
            A[i] <- a
            swapped <- TRUE
        }
    }
}

If you understand the pseudo-code, then you know what the R code is accomplishing even though you can’t read the R language. However, you can probably deduce what a lot of it is doing!

• What do you think the combination of characters <- means? What about the pattern {...}?

• Which pseudo-code step is implemented by the if (...) {...} block?

• What is the role of a?

• What word in the code tells the interpreter to repeat a set of unstructions an unspecified number of times? What word causes a set of instructions to repeat a fixed number of times?

Pseudo-code Exercise 1

Complete the following pseudo-code to sum a given array of integers:

1. let A refer to the array of integers.
2. let n refer to the length of A
3. let sum refer to 0
   …

Pseudo-code Exercise 2

Complete the following pseudo-code with instructions to test whether a given integer is even or odd. Assume you can use a pre-existing capability to round any number to its nearest integer, as well as the arithmatic operators * and /.

1. let i refer to a given integer
2. if i is less than zero, let i refer to -1 * i
   …

Pseudo-code Exercise 3

Refer back to the bubble-sort algorithm. Step 7 says to “swap” elements of an array, but in the implementation that takes 3 lines of code including creation of a dummy variable. The implementation would be easier to read (since we, the reader, already understand what “swap” means) and “modular” if we replaced those lines with a swap function defined outside the loops.

Just using what you can infer from the pseudo-code and R code above, what would you replace each ... with below to improve our bubble-sort implementation.

swap <- function(j, x) {
  ...
  return(x)
}

n <- length(A)
swapped <- TRUE
while (swapped) {
    swapped <- FALSE
    for (i in seq(1, n - 1)) {
        if (A[i+1] < A[i]) {
            ...
            swapped <- TRUE
        }
    }
}