Benjamin Halsted // [bgh] todo, add something clever here.

Erlang Programming Exercise: 3-6 (quicksort)

Quicksort! Wow, it's been forever since I've had to implement a sorting routine. Here are the instructions:

Quicksort: The head of the list is taken as the pivot; the list is then split according to those elements smaller than the pivot and the rest. These two lists are then recursively sorted by quicksort, and joined together, with the pivot between them.

-module(threesix).
-export([quicksort/1]).

quicksort(Pivot, Left, Right, []=_Src) ->
	{Left, Pivot, Right};
quicksort(Pivot, Left, Right, [H|T]=_Src) when H < Pivot ->
	quicksort(Pivot, [H|Left], Right, T);
quicksort(Pivot, Left, Right, [H|T]=_Src) ->
	quicksort(Pivot, Left, [H|Right], T).

quicksort([]) ->
	[];
quicksort([H|T]=_List) ->
	{Left, Pivot, Right} = quicksort(H, [], [], T),
	quicksort(Left) ++ [Pivot] ++ quicksort(Right).

In chapter 2 of Erlang Programming the author talks about how the ++ operator isn't very efficient. So I tried swapping it out with my previous implementation of concatenate. I then ran some timing tests and found that ++ was faster than my concatenate. A bit disturbed by this I went back to read the warnings again and found that the author was warning against using the ++ operator to prepend single items to a list. So you shouldn't use [1] ++ [2,3,4] in place of [1|[2,3,4]].

To test this out, I went back and modified my reverse function to use the ++ operator:

reverseA(To, []) ->
        To;
reverseA(To, [H|T]) ->
        reverseA([H] ++ To, T).
reverseA(List) ->
        reverseA([], List).

To my surprise, there was no difference in the speed. I then swapped the [H] and To:

reverseA(To, []) ->
        To;
reverseA(To, [H|T]) ->
        reverseA(To ++ [H], T).
reverseA(List) ->
        reverseA([], List).

This version took FOREVER to run. I didn't quite understand it so I went searching. There is a nice post here that has a nice explanation.

Here is the important bit from that page:

++ is only slow when used wrongly, used carefully it is as fast as anything you could craft by hand. You have to make sure you work through the list in the correct direction, otherwise the resulting append is O(N^2). When we do X ++ Y, we must make a copy of X and then prepend it to Y which is not copied.

Cheers,
-Halzy