Jason's Blog

In this post, I'm going to take a Rcpp example that call a C++ function to find kth smallest element from an array. A partition-based selection algorithm could be used for implementation. A most basic partition-based selection algorithm, quickselect , is able to achieve linear performance to find the kth element in an unordered list. Quickselect is a variant of quicksort , both of which choose a pivot and then partitions the data by it. The procedure of quickselect is to firstly move all elements smaller than the pivot to the left and what greater than the pivot the the right by exchanging the location of them, given a pivot such as the last element in the list; and then to move the elements in the left or right sublist again according to a new pivot until getting exact kth elements. The difference from quicksort is that quickselect only need to recurses on one side where the desired kth element is, instead of recursing on both sides of the partition which is what quicksort ...

It sometimes could be a great idea to incorporate bits of C++ into our R coding through the Rcpp package. Before writing or calling our C++ functions, we need firstly a working C++ setup for R, which is not difficult on Mac OS system. First, we need a C++ compiler. We can download XCode and install the Command Line Tools. Second, we need to create a file  $\sim$/.R/Makevars , to tell R which compliers to use. The file creation can be done by typing the following commands in Terminal, cd ~/.R nano Makevars Now add the following text: CC = clang CXX = clang++ And follow the directions at the bottom of the screen to "write out" and close the file (Control-O Enter and Control-X). Next, we need to install Rcpp package in R from source so that it is built with the same C++ complier we are using. install.packages("Rcpp", type = "source") After finishing the setup of connection between C++ and R, we can write a C++ function that R c...