Testing Julia for speed (ii)

The next test for evaluating the performance of Julia uses the Bubblesort. 

Bubblesort is arguably one of the most infamous sorting algorithms, partially because it is simple, and partially because it is one of the worst performing sorting algorithms. It works by repeatedly passing through an array, comparing two items and swapping them if they are in the wrong order. A bubble sort has a worst case complexity of O(n²).

So how fast (or slow) is bubble sort? Here is the code in Julia.

function bubblesort(arr)
    n = length(arr)
 
    for i=1:n, j=1:n-i
        if (arr[j] > arr[j+1])
            arr[j], arr[j+1] = arr[j+1], arr[j]
        end
    end
end

arr=[]
for i=1:1000
  push!(arr,rand(1:10000))
end

bubblesort(arr)

Again, code in C, Fortran, and Python is similar, so I’m not going to reproduce it. Note the interesting use of the variable swapping syntax, and the ease with which a random array of numbers is created.

The timings for sorting 1000, and 100,000 random numbers is given below.

timingBubblesort

Again, C and Fortran have similar timings, with Julia approximately 5 times slower than either, for the large sort. The big eye opener is Python of course  which, having issues with loops, is over 16 times slower than Julia, and 89 times slower than C.

Note that all the code for these programs was written the same way, i.e. an efficient version of Bubblesort was not implemented. Both Julia and Python used their intrinsic syntax for swapping two numbers, versus the use of the swap() function in C and Fortran.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s