# Elemental selection sort functions in R

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
}


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)
 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).

• 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. – snoram Dec 29 '16 at 20:14
• 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. – flodel Dec 29 '16 at 21:46
• Ah yes, my mistake, n must have been defined globally. – snoram Dec 30 '16 at 0:46