Sorting algorithms in Erlang, Part 1

Ok, so I am continuing my series of posts on sorting algorithms. In the first parts, I implemented some classic sorting algorithms in Ruby, an OO language. Right now, I will implement similar algorithms in a purely functional language, Erlang.

I will not explain the basis for the algorithms in these posts as I have already done so in the Ruby posts.

Differences in implementations

Implementing Bubble sort in Erlang was really hard for me. While implementing it in Ruby was dead simple, in Erlang this algorithm was one of the hardest, if not the hardest for me to figure out. Going into this, I was already expecting the iterative algorithms to be harder to implement in a functional style, but not this much. There is more code and it is harder to follow then a procedural or OO implementation.

If you were to give the task of implementing a sorting algorithm to a class of green CS students, in a procedural or OO language, without asking them to focus on performance, you would probably get a few bubble sorts. Bubble sort, Insertion sort and Selection sort are all very intuitive in a procedural paradigm.

I don’t see someone coming up with Bubble sort intuitively in a functional language. Clearly this is a sign of how different paradigms shape our way of coming up with solutions. The languages and more importantly the paradigms we use ,shape our very way of thinking.

For the purely iterative algorithms to work in Erlang, I had to change them into recursive algorithms. The concepts of in-place and out of place sorting were also thrown out the window. “while” loops in other languages often depend on mutable state to work, in Erlang these must be replaced with recursion as there is no mutable state.

Bubble sort

Here is the code for what I came up with. Disclaimer, I am still a novice with Erlang and there are better/shorter implementations on the web.

% empty list an single element list
bubble_sort([]) -> [];
bubble_sort([X | []]) -> [X];

bubble_sort(ToSort) -> {RList, RSwapped} = bubble_sort(ToSort, false),
					   case RSwapped of
					   		true -> bubble_sort(RList);
					   		false -> RList
					   end.

% We have come to the last element of the list
bubble_sort([X, Y | []], Swapped) -> case X > Y of
							  			true -> {[Y, X], true};
										false -> {[X, Y], Swapped} 
							   	     end;

% We are working through the list
bubble_sort([X, Y | Tail], Swapped) -> case X > Y of
										true -> {NewTail, RSwapped} = bubble_sort([X | Tail], true), {[Y] ++ NewTail, RSwapped};
										false -> {NewTail, RSwapped} = bubble_sort([Y | Tail], Swapped), {[X] ++ NewTail, RSwapped} 
							  		 end.  

The algorithm works by defining that an empty list and a list with a single element is already sorted. In any other case, we traverse the list recursively with bubble_sort/2, swapping the elements when returning from the chain of recursive calls.

Swapped is passed along to monitor if any swaps have taken place. This way we can tell the bubble_sort/1 to recursively start another chain of recursive calls to bubble_sort/2 and go through the whole list again.

Insertion sort

Insertion sort was much easier to write in Erlang than Bubble sort. I also find it a lot easier on the eyes to. Contrary to Bubble sort, I did not find implementing Insertion sort in Erlang harder than in Ruby. This solution feels more natural in Erlang than the previous one.

Note that the code is simplified because it relies on the max/1 function. Without relying on this built-in function the code would have been more dense.

Of course, this isn’t a “pure” textbook insertion sort, but you could call it a functional Insertion sort.

insertion_sort([]) -> [];
insertion_sort([X | []]) -> [X];

insertion_sort(ToSort) -> insertion_sort(ToSort, []).

insertion_sort([], Sorted) -> Sorted;

insertion_sort(Unsorted, Sorted) -> Max = lists:max(Unsorted),
									insertion_sort(lists:delete(Max, Unsorted), 
                                                   [Max] ++ Sorted).

The function insertion_sort/1 calls insertion_sort/2. It’s first parameter is the list to sort and the second parameter the sorted list.

See you next time as I implement more sorting algorithms.

Sorting algorithms in Erlang, Part 2