# Review my F# BubbleSort Program

I have written this code for BubbleSort in F#. Can you review and let me know how I can do this in most functional way.

let rec getHighest list =
match list with
| [x] -> x
| [x; y] when x > y -> x
| [x; y] -> y
| hd1 :: hd2 :: tl when hd1 > hd2 -> getHighest (hd1 :: tl)
| hd1 :: tl -> getHighest tl
| _ -> failwith "unknown pattern"

let bubbleSort list =
let rec innerBubbleSort sorted = function
| [] -> sorted
| l ->
let x = getHighest l
let (a, b) = List.partition (fun i -> i = x) l
innerBubbleSort (a @ sorted) b
innerBubbleSort [] list

[<EntryPoint>]
let main args =
let input = [10; 7; 1; 0; -1; 9; 33; 12; 6; 2; 3; 33; 34;]
let output = bubbleSort input
printfn "%s" (List.fold (fun acc x -> acc + " " + x.ToString()) "" output)
0


The first part could be rewritten as

match list with
| hd1 :: hd2 :: tl when hd1 > hd2 -> getHighest (hd1 :: tl)
| hd1 :: hd2 :: tl -> getHighest (hd2::t1)
| hd1 :: [] -> hd1
| _ -> failwith "unknown pattern"


which is significantly simpler

• even simpler if you replace the first two patterns with a single one: | hd1::hd2::tl -> let hd = if hd1 > hd2 then hd1 else hd2 in getHighest (hd::tl) Dec 29, 2013 at 22:32

I think a cleaner way to write getHighest would be to use accumulator:

let getHighest list =
let rec getHighestImpl list highest =
match list with
| [] -> highest


You could also use the version of this function that already exists in the library: List.max.

This is not bubble sort. In bubble sort, you compare neighboring items and swap them if they're in the wrong order. You do something similar in your getHighest, but you don't preserve the swaps. So, in the end, your algorithm is closer to selection sort, than bubble sort.