Friday, September 28, 2012

F# on Algorithms - Quick sort

For a long time, I heard the F# is good at algorithm and today I decided to start on what can F# do when implement basic algorithms. The first one is the quick sort algorithm. I was shocked when I finished my first task. The code is very clean and easy to understand. If you replace the (<=) with (<), you can actually remove the duplicated elements in the array.

let rec quickSort (data:int list) =
    match data with
    | [] -> []
    | [a] -> [a]
    | head::tail ->
        let l0 =
            tail
            | > List.filter ((<=) head)
        let l1 =
            tail
            | > List.filter ((>) head)
        quickSort(l0) @ [head] @ quickSort(l1)

quickSort [-2; -3; 4; -1; 0; 1; 5; 7; -2]


1 comment:

Yura Yaroshevich said...

Using List.partition even more concise :)
let rec quickSort (l : _ list) =
match l with
| hd :: tl ->
let lt, gtq = tl |> List.partition ((>) hd)
quickSort lt @ hd :: quickSort gtq
| _ -> []