Review my F# BubbleSort Program

Question

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

Answer 1

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

Answer 2

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
        | head::tail -> getHighestImpl tail (max head highest)
    getHighestImpl (List.tail list) (List.head list)

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.