Sorting algorithms in Erlang, Part 2

Hello again. Today I continue my series on sorting. In the last instalment I reimplemented in Erlang two iterative sorting algorithms that I had previously done in Ruby. Today, I am going to re implement two recursive algorithms.

Before going into this, I was thinking the recursive algorithms would be a more natural fit for the language and easier to implement. No surprises here, it turned out as expected.

Merge sort

Here is my Merge sort implementation in Erlang:

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

merge_sort(ToSort) -> {FirstList, SecondList} = lists:split(round(length(ToSort) / 2), ToSort),
					  lists:merge(merge_sort(FirstList), merge_sort(SecondList)).

You could say I cheated a bit here. In the Ruby version, I chose to implement my own merge method rather than use a prebuilt like I just did here in Erlang…

To be fair in my comparison, I also implemented a merge function.

merge(X, []) -> X;
merge([], Y) -> Y;
merge([X | TailX], [Y | TailY]) when X < Y -> [X] ++ merge(TailX, [Y | TailY]);
merge([X | TailX], [Y | TailY]) when X > Y -> [Y] ++ merge([X | TailX], TailY).

You just have to replace lists:merge with merge in the previous code and everything works the same. I could have only shown you the implementation with the custom merge, but the version with the built-in merge is very striking. It’s quick, clear and to the point.

The merge function is different in both implementations, the sort function on the other hand is very similar in logic.

If you go back to the Ruby version you will see it is a bit longer than the Erlang one. This is because I used intermediary variables in the Ruby version. If you add them to the Erlang one they become very similar.

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

merge_sort(ToSort) -> {FirstList, SecondList} = lists:split(round(length(ToSort) / 2), ToSort),
					  FirstSortedList = merge_sort(FirstList),
					  SecondSortedList = merge_sort(SecondList),
					  lists:merge(FirstSortedList, SecondSortedList).

Here is the Ruby version (without the comments) for reference:

def sort(to_sort)
	if to_sort.length <= 1 
		then return to_sort 
	end
		
	second_array = to_sort.slice!((to_sort.length / 2.0).round..to_sort.length)
				
	first_sorted_array = sort(to_sort)
	second_sorted_array = sort(second_array)

	return merge(first_sorted_array, second_sorted_array)
end

Quicksort

When I originally started the series I mentioned I was going to implement the algorithms without resorting to reading other implementations or pseudo-code. I would try as much as possible to work with the textual descriptions of the algorithms. I have pretty much followed this. In some rare cases tough, I did glean at some pseudo-code.

Unfortunately, while reading the official Erlang documentation, I stumbled upon a quicksort implementation on the list comprehension page. It was very short and I couldn’t stop reading it before it was too late. Rather than pretend I never saw it (and also because it’s very cool) I will present it as is:

sort([Pivot|T]) ->
    sort([ X || X <- T, X < Pivot]) ++
    [Pivot] ++
    sort([ X || X <- T, X >= Pivot]);
sort([]) -> [].

(original source)

As you can see it uses the first element as a pivot, something that isn’t optimal but that I also did in my Ruby implementation. I like the implementation very much. It’s short, concise and very elegant.

I also wrote my own implementation, it’s not as short but it uses the middle element as the pivot. This prevent some of the performance problems when the list is already sorted or nearly sorted.

Here it is:

quicksort([]) -> [];

quicksort(ToSort) -> Pivot = lists:nth(round(length(ToSort) / 2), ToSort),
					 SmallerElements = lists:filter(fun(X) -> X < Pivot end, ToSort),
					 LargerElements = lists:filter(fun(X) -> X > Pivot end, ToSort),
					 quicksort(SmallerElements) ++ [Pivot] ++ quicksort(LargerElements).

Conclusion

As you you can see with merge sort, you can sometimes come up with similar approaches in two different paradigms. In some languages, for example C#, not only can you apply algorithms commonly found in functional languages, but the language integrates some functional concepts as well.

When you aren’t used to thinking in functional terms it can be challenging to use these concepts to their fullest. Learning to program in a functional language is not only an end to itself, it also helps with applying new concepts in languages you are already familiar with.

Sorting algorithms in Erlang, Part 1

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