2
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.