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
}
}
}
``````