in R 264 Words

R and C++ Selection Sort

Casually following along with Princton’s Coursera course on algorithms taught in Java. Trying to implement the 5 different sorting algorithms without looking at the Java implementation. At the same time trying to learn a bit of C++ and use R’s Rcpp function.

I implemented selection sort in both R and C++ and boy is the C++ version faster — 1000+ times faster!!! Below you can see a comparison sorting a 50,000 element numeric vector. The C++ version took less than a second, while the R version took 14 minutes. Crazy!!

> unsorted = sample(1:50000)
> R_time = system.time(selection_sort_R(unsorted))
> Cpp_time = system.time(selection_sort_Cpp(unsorted))
> R_time['elapsed']/Cpp_time['elapsed']
 elapsed 
1040.395
> Cpp_time
   user  system elapsed 
   0.82    0.00    0.81 
> R_time
   user  system elapsed 
 838.79    0.09  842.72

Created by Pretty R at inside-R.org

Below are the implementations in R and C++.

###################################################
# R Selection Sort
###################################################
# Define R selection Sort
selection_sort_R = function(v) {
  N = length(v)
 
  for(i in 1:N) {
    min = i
 
    for(j in i:N) {
      if(v[j] < v[min]) {
        min = j
      }    
    }
    temp = v[i]
    v[i] = v[min]
    v[min] = temp
  }
  return(v)
}

Created by Pretty R at inside-R.org

###################################################
# C++ Selection Sort
###################################################
# Define C++ selection Sort
require(Rcpp)
cppFunction('NumericVector selection_sort_Cpp(NumericVector v) {
  int N = v.size();
  int min;
  int temp;
 
  for(int i = 0; i < N; i++) {
    min = i;
 
    for(int j = i; j < N; j++) {
      if(v[j] < v[min]) {
        min = j;
      }    
    }
    temp = v[i];
    v[i] = v[min];
    v[min] = temp;
  }
  return v;
}')

Created by Pretty R at inside-R.org

Leave a comment