Sorting

Let's learn how to work with list by implementing different sorting functions. There are several ways to sort a list and you should know them all. We will start with the most basic algorithm and then try some other (more or less good).

Insertion sort

In insertion sort, you sort a list of elements by taking them one at a time and insert them into an already sorted list. The already sorted list will of course be empty when we start but will when we are done contain all the elements.

Start by defining a function insert(element, list), that inserts the element at the right place in the list. Think of the two mayor cases, what to do if the list is empty and what to do if the list contains at least one element. Assume that the elements are integers and can be compared using the regular $<$ operator.

Once you have insert/2 working, implement the sorting function isort(list); again what should you do if the list is empty, what should you do if it contains at least one element?

Now all you have to do is provide a function isort(list), that calls the function insert/2 using the right arguments.

def isort(l) do
    [] -> 
      ...
    [h | t] ->
      ...
  end
end

Try also to rewrite the isort function using the clause syntax; same-same but different.

As an exercise you can try to rewrite the isort/1 function to be tail recursive. As you have probably written it now you first do the recursive call to sort the rest of the list and then do the insertion. One could work with an accumulating argument that grows as we insert one element after the other.

def isort(l) do isort(l, []) end

def isort(l, sofar) do
    [] -> 
      ...
    [h | t] ->
      ...
  end
end

In this case it does however not help us much since insert/2 is not tail recursive so we will use a lot of stack space anyway. There are ways around this but it is a rather pointless exercise that will probably be slower than the version you have now.

Merge sort

In merge sort, you divide the list into two (as equal as possible) list. Then you merge sort each of these lists to obtain two sorted sub-lists. These sorted sub-lists are then merged into one final sorted list.

The two lists are merged by picking the smallest of the elements from each of the lists. Since each list is sorted, one need only to look at the first element of each list to determine which element is the smallest.

The skeleton code below will give you an idea of what the solution will look like. Here we do use the clause syntax when defining merge, you can try to define it using case expressions but it becomes a bit messy.

def msort(l) do 
    case ... do 
        ... -> ... 
        ... -> 
            {.., ...} = msplit(l, [], []) 
            merge(msort(...), msort(...)) 
    end 
end

def merge(..., ...) do ... end 
def merge(..., ...) do ... end 
def merge(..., ...) do 
    if ... 
        merge(.., ...) 
    else 
        merge(.., ...) 
    end 
end

def msplit(..., ..., ...) do 
    case ... do 
        ...  -> {..., ...} 
        ... -> msplit(..., ..., ...) 
    end
end

Quicksort

The quicksort algorithm sounds even quicker than merge sort but this is not true. The idea is similar but now we "do our sorting on the way down". First split the list into two parts, one containing low elements and one containing high elements. Then sort the two lists and when you're done append the results.

Splitting the lists is done using the first element in the list as a pivot element, all smaller or equal than this is added in one list and all larger in one list. When you're appending the final result, remember to put the pivot element in the middle.

def qsort(...) do ... end
def qsort([p | l]) do 
  {..., ...} = qsplit(p, l, [], [])
  small = ...
  large = ...
  append(small, [p | large])
end


def qsplit(_, [], small, large) do ... end
def qsplit(p, [h | t], small, large) do
  if ...  do
    ...
  else
    ...
  end
end

def append(..., ...) do
  case ... do
    [] -> ...
    [h | t] -> ...
  end
end