## 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.

*25 Oct 2009*
*Damien Wintour*
2 comments