Sorting Algorithms in F#

A while ago I reviewed basic sorting algorithms in Java and C#. I've been playing a lot with F# over the past 6 months so I'd thought it would be worthwhile whipping up the same algorithms in F#.

The earlier posts with Java and C# implementations are here:
Sorting Fundamentals: Part 1
Sorting Fundamentals: Part 2

Bubble Sort

Everyone knows this is an inefficient algorithm but none-the-less it has "educational value". In my F# implementation I've defined 2 recursive functions, sink and outer. Both functions accept a list and return a new list. The sink function makes a single pass through the list sinking the largest value to the rightmost/last position in the list using simple pattern matching semantics. In lines 7-8 the cons operator (::) is used to separate the first 2 items in the list from the remainder of the list so a greater than pairwise comparison can be make on the leading pair. Note that lists, and indeed all identifiers not explicitly marked as mutable, are immutable so a new list is created rather than returning the original list. In other words, it is not in-place.

The second function, outer, is logically equivalent to the outer loop in the C#/Java implementation that you've no doubt seen before. We pass a list and the list size to this function. The function sinks one value using the function described above, then calls itself recursively on a new list that is a copy of the original list but has one fewer items - the "sunken" element is removed from the end.

    1 #light
    2 open System
    3 
    4 let rec sink ls =
    5     match ls with
    6     | [] -> []
    7     | x::y::rest when x > y -> y::(sink (x::rest))
    8     | x::rest -> x::(sink rest)
    9 
   10 let rec bubbleSort ls =
   11   let rec outer ls lsSize =
   12     match lsSize with
   13     | 0 -> ls
   14     | x -> outer (sink ls) (x - 1)
   15   outer ls (Seq.length ls)
   16 
   17 let mylist = [3;5;1;2;2;78;9;8;43;5;-6]
   18 let mylistsorted = (bubbleSort mylist)
   19 print_any mylistsorted
   20 Console.ReadLine() |> ignore

Insertion Sort

The insertion sort algorithm works by inserting each item into an already sorted sub-list. In F# I've implemented it using 2 recursive functions, insert and insertionSort. Both functions take a list and return a new list. The insert function takes an item and a list and creates a new list which is a copy of the one passed but it inserts the passed item into the new list. This function is designed to take a sorted list or an empty list - which then becomes a sorted list.

The insertionSort function picks off the first item in the list and inserts it into the already-sorted sublist .

    1 #light
    2 open System
    3 
    4 let rec insert x ls =  
    5     match ls with 
    6     | []    -> [x]
    7     | y::rest -> if x <= y then x::y::rest
    8                  else y::(insert x rest)
    9 
   10 let rec insertionSort ls = 
   11     match ls with 
   12     | []    -> []
   13     | x::rest -> insert x (insertionSort rest)      
   14 
   15 let mylist = [3;5;1;2;2;78;9;8;43;5;-6]
   16 let mylistsorted = (insertionSort mylist)
   17 print_any mylistsorted
   18 Console.ReadLine() |> ignore

QuickSort

The quicksort algorithm is a classic divide-and-conquer algorithm. It selects a pivot from the list then creates 2 sub-lists containing all items less than, and greater than the pivot. The result is a new list which is the concatenation of the less-than list, the pivot, and the greater-than list. And, in order to sort the 2 sub-lists it calls itself recursively.

#light

open System

let rec quickSort ls =

  match ls with

  | [] -> []

  | p::r ->

     quickSort [for i in r do if (compare i p) <= 0 then yield i]

     @ [p]

     @ quickSort [for i in r do if (compare i p) > 0 then yield i]

let mylist = [3;5;1;2;2;78;9;8;43;5;-6]

let mylistsorted = (quickSort mylist)

print_any mylistsorted

Console.ReadLine() |> ignore

MergeSort

Of all the sort algorithms, quicksort is perhaps the most amenable to functional programming as it can exploit parallelization. If I had 10 billion records in numerous files over many machines a modified version of mergeSort is what you'd want top use, but that's a topic for another post...

    1 #light
    2 open System
    3 
    4 let rec splitList ls n =
    5     match ls with
    6     | [] -> [],[]
    7     | ls when n=0 -> ([],ls)
    8     | head::tail -> 
    9         let l1, l2 = splitList tail (n-1);
   10         head::l1, l2
   11 
   12 let rec mergeLists ls1 ls2 =
   13     match ls1, ls2 with
   14     | [],[] -> []
   15     | [],ls2 -> ls2
   16     | ls1,[] -> ls1
   17     | h1::t1, h2::t2 when h1 <= h2 -> h1 :: mergeLists t1 ls2
   18     | h1::t1, h2::t2 -> h2 :: mergeLists ls1 t2
   19 
   20 let rec mergeSort ls =
   21     match ls with
   22     | [] -> []
   23     | [x] -> [x]
   24     | ls ->
   25         let ls1, ls2 = splitList ls (ls.Length/2)
   26         mergeLists (mergeSort ls1) (mergeSort ls2)
   27 
   28 let mylist = [3;5;1;2;2;78;9;8;43;5;-6]
   29 let mylistsorted = (mergeSort mylist)
   30 print_any mylistsorted
   31 Console.ReadLine() |> ignore

As you can see, F# code is succinct and highly expressive. I liken it to Python in it's terseness without the performance penalty! The beauty of F# is a lightweight syntax where whitespace is used instead of block- and scope-defining curly braces, and the clever use of type inference within a strongly-typed type system, so I needn't get bogged down defining explicit types which makes the code's purpose clearer.

Necessary and Sufficient