Elemental selection sort functions in R

Question

A simple selection sort functions in R. Just for practice.

Given the choice of algorithm and tools I wonder what can most easily be improved about the functions.

NB. I wanted to keep the first function as elemental as possible.

# Selection sort playing with loops
sels <- function(x) {
 n <- length(x)
 for (i in 1:(n - 1)) {
 min <- i # this variable keeps track of smallest number in unsorted
 # just some prior, update if confronted with better info
 for (j in (i + 1):n) {
 if (x[j] < x[min]) {
 min <- j # update as we find something smaller
 }
 }
 if (min != i) { # now if we did update prior; swap
 temp <- x[i]
 x[i] <- x[min]
 x[min] <- temp
 }
 }
 x
}
# Selection sort in more R'ish-style
selsr <- function(x) {
 # Selection sort a vector
 n <- length(x)
 for (i in 1:(n - 1)) {
 j <- i + which.min(x[(i + 1):n])
 if (j != i) {
 temp <- x[i]
 x[i] <- x[j]
 x[j] <- temp
 }
 }
 x
}

Answer 1

Here are some ideas, somewhat sorted by order of importance. I hope it helps.

1) There is a problem with your second function, see that

> selsr(1:5)
[1] 2 3 4 5 1

You should be doing

j <- i - 1L + which.min(x[i:n])

2) Your choice of 1:(n - 1) will not properly handle the n == 0. Also, it does handle the n == 1 case properly but it is a bit of luck considering you are looping over 1:0... The robust alternative to the : operator is to use seq_len or seq_along. Or you could just have a if (n < 2L) return(x) near the top of your functions.

3) While on the topic of corner cases, your code assumes that x is a numerical vector. You could be checking for that by adding:

stopifnot(is.vector(x), is.numeric(x))

4) You can achieve the swaping without a temporary variable by doing:

x[c(i, j)] <- x[c(j, i)]

5) min is a questionable variable name, given it is also the name of a base function.

6) This is debatable: I would get rid of the if (j != i) condition since it won't hurt doing the swap even if j == i. IMO, the simpler code is preferable to the marginal computation time gain.

7) A nit: know the difference between 1 (numeric) and 1L (integer). Here you are using 1 when you mean to use 1L, which causes unnecessary conversions from integer to numeric (though the : operator brings you back to integers by doing the opposite conversion).

• snoram: Fantastic lesson! On 7) Would you convert every instance of 1 to 1L or just the ones where it is +/- 1? On 2) Could I just add n > 1Lto the stopifnot? It seems to work, even if the stopifnotis placed above the definition of n.
• flodel: 7) All of them, but it's really a detail. 2) It is up to you, whether you want the function to return something or error out for these special cases. For inspiration, you could see what sort(c()) and sort(1) do. Finally, I doubt stopifnot(n > 1L) will work unless n is defined before; maybe it did not error out because you had an defined in your global environment.
• snoram: Ah yes, my mistake, n must have been defined globally.