Much more efficient bubble sort in R using the Rcpp and inline packages

Recently I wrote a blogpost showing the implementation of a simple bubble sort algorithm in pure R code. The downside of that implementation was that is was awfully slow. And by slow, I mean really slow, as in “a 100 element vector takes 7 seconds to sort”-slow. One of the major opportunities for a speed is to start using a compiled language. I chose to use C++ as this is really easy to integrate into R using the Rcpp package. In addition to the Rcpp package I use the inline package which allows one to use C++ code and R code in a seamless fashion. The following code creates an R function bubble_sort_cpp:

require(inline)  ## for cxxfunction()                                                       
                                                                                            
src = 'Rcpp::NumericVector vec = Rcpp::NumericVector(vec_in);                               
       double tmp = 0;                                                                      
       int no_swaps;                                                                        
       while(true) {                                                                        
           no_swaps = 0;                                                                    
           for (int i = 0; i < vec.size()-1; ++i) {                                         
               if(vec[i] > vec[i+1]) {                                                      
                   no_swaps++;                                                              
                   tmp = vec[i];                                                            
                   vec[i] = vec[i+1];                                                       
                   vec[i+1] = tmp;                                                          
               };                                                                           
           };                                                                               
           if(no_swaps == 0) break;                                                         
       };                                                                                   
       return(vec);'                                                                        
bubble_sort_cpp = cxxfunction(signature(vec_in = "numeric"), body=src, plugin="Rcpp")

Quite amazing how easy it is to integrate R code and C++ code. inline compiles and links the C++ code on-the-fly, creating an R function that delivers the functionality. Of course the most important question is now how fast this is. I use the microbenchmark package to run the bubble sort I implemented in pure R (here), the bubble sort implemented in C++ (see above), and the standard R sorting algorithm:

library(microbenchmark) 
vector_size = 100                                                                           
print(microbenchmark(bubble_sort(sample(1:vector_size)),                                    
               bubble_sort_cpp(sample(1:vector_size)),                                      
               sort(sample(1:vector_size))))  
                                   expr       min         lq     median
     bubble_sort(sample(1:vector_size)) 67397.546 74358.9495 78143.0710
 bubble_sort_cpp(sample(1:vector_size))    44.895    55.9340    60.4930
            sort(sample(1:vector_size))    44.173    48.1315    62.3785
         uq        max neval
 81285.0215 105626.483   100 
    63.7715     74.643   100 
    67.2375    138.069   100

These results speak for itself, the C++ version is more than 1300 times faster when looking at the median speed, even faster than the built-in sort function. These differences will only get more pronounced when the size of the vector grows.