§ /prog/ Challenge #32767 §

The Challenge: Given a number k where k ≥ 2, print another program (in the language you solve this challenge) that performs an O(n^k) sort on a list (in-place or not is for you to decide).

The Deadline: 2011/05/18, 00:00 UTC.


let rec sortExprStr (k:int) (listExpr:string) =
    if k = 2 then
        "let rec qsort(xs : List<int>) =
                match xs with
                | [] -> []
                | x :: xs ->
                    let smaller = qsort (xs |> List.filter(fun e -> e <= x))
                    let larger = qsort (xs |> List.filter(fun e -> e >= x))
                    smaller @ [x] @ larger
           qsort %listExpr".Replace("%listExpr", listExpr)
    else
        let subSort = sortExprStr (k - 1) listExpr
        "%listExpr |> List.fold (fun acc n -> begin %subSort end) []".Replace("%listExpr", listExpr).Replace("%subSort", subSort)

System.Console.WriteLine(sortExprStr 10 "[3; 2; 1]")