Pages

Thursday, September 2, 2010

QuickSort in F# using Continuation Passing Style (CPS)

The recursive implementation is a good approach for QuickSort algorithm; however, this implementation can lead to "stackOverflow" exception. We will use tail recursive to get rid of this flaw.


let rec qs list cont =
    match list with
        | [] -> cont([])
        | [a] -> cont([a])
        | head::tail ->
            let lessList = tail |> List.filter (fun i-> i<=head)
            let moreList = tail |> List.filter (fun i-> i>head)
            qs lessList (fun lessListPara -> 
                qs moreList (fun moreListPara -> cont(lessListPara@[head]@moreListPara)))

let list = [7;2;6;8;4]
let result = qs list (fun a -> a)

No comments: