Bubble sort implemented in pure R

Please note that this is programming I purely did for the learning experience. The pure R bubble sort implemented in this post is veeeeery slow for two reasons:

  1. Interpreted code with lots of iteration is very slow.
  2. Bubble sort is one of the slowest sorting algorithms (O(N^2))

The bubble sort sorting algorithm works by iterating over the unsorted vector and comparing pairs of numbers. Let’s say the first point pair is c(61, 3), here the numbers need to be swapped as the 3 should be earlier in the sorted vector. The following function returns TRUE if the numbers should be swapped, and returns FALSE otherwise:

This function is used by the following function:

which returns the swapped version of the pair if appropriate, or the original pair if the order is ok. For each point pair (element1-element2, element2-element3, etc) swap_if_larger is called:

One pass of this function performs a comparison on all pairs, swapping if necessary. To fully sort the vector, we need to perform multiple passes until no swaps are needed anymore. I chose to implement this using recursion:

The function starts by perform a swapping pass over the vector. If the new vector is equal to the old vector, no swaps where needed, i.e. the vector is already sorted. The function than returns the vector. Alternatively, if the vectors are different, the vector is not yet fully sorted, and we need to perform more passes. This is accomplished by recursively calling bubble_sort again on the vector. An example of the function in action:

The full sorting process is nicely illustrated by the following animated gif (linked from wikipedia):

enter image description here

This implementation is horribly slow:

Probably implementing the relatively slow bubble sort in a compiled language pose a dramatic increase in speed. Maybe a nice first testcase for Rcpp

Tagged with: , , ,
Posted in R stuff
No Comments » for Bubble sort implemented in pure R
2 Pings/Trackbacks for "Bubble sort implemented in pure R"
  1. [...] I wrote a blogpost showing the implementation of a simple bubble sort algorithm in pure R code. The downside of that [...]

  2. […] my hands, and implemented the bubble sort algorithm that I have already posted about several times (R, C++). The main argument for Julia is it’s speed. It claims speeds comparable to that of a […]

Leave a Reply

Your email address will not be published. Required fields are marked *

*

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">