Дошёл черёд до реализации быстрой сортировки на OCaml, пока я слушаю курс по алгоритмам (Algorithmic Toolbox). Поскольку основная цель - практика программирования на OCaml, то этот раз я не стал заниматься разработкой partion с ручным перемещением элементов списка, а заменил её двумя вызовами List.filter. Код для тестирования взял из сортировки слиянием, а функцию генерации тестовых данных сделал как в сортировке подсчётом, чтобы в список входили отрицательные числа.

Исходный код:

open Core.Std


let rec quicksort lst =
    let open List in
    match lst with
    | [] | [_] -> lst
    | hd :: tl ->
            let left = quicksort (filter tl (fun i -> i <= hd)) in
            let right = quicksort (filter tl (fun i -> i > hd)) in
            concat [left; [hd]; right]


let rec create_test_data = function
    | 0 -> []
    | size -> (Random.int 100) - 50 :: create_test_data (size - 1)


let render color text =
    sprintf "\027[38;5;%dm%s\027[0m\n" color text


let render_success data qs_sorted sorted =
    let color = 2 in
    let message = "Ok" in
    if List.length data < 20 then
        [
            message;
            "Data: " ^ (List.to_string data ~f:string_of_int);
            "Quicksort: " ^ (List.to_string qs_sorted ~f:string_of_int);
            "List sort: " ^ (List.to_string sorted ~f:string_of_int);
        ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""
    else
        render color (message ^ " size: " ^ (string_of_int (List.length data)))


let render_error data qs_sorted sorted =
    let color = 1 in
    let message = "Error"in
    [
        message;
        "Data: " ^ (List.to_string data ~f:string_of_int);
        "Quicksort: " ^ (List.to_string qs_sorted ~f:string_of_int);
        "List sort: " ^ (List.to_string sorted ~f:string_of_int);
    ] |> List.map ~f:(fun str -> render color str) |> String.concat ~sep:""



let rec test size =
    let data = create_test_data size in
    let qs_sorted = quicksort data in
    let sorted = List.sort data ~cmp:compare in
    match compare sorted qs_sorted with
    | 0 -> (
        printf "%s%!" (render_success data qs_sorted sorted);
        if size > 0 then
            test (size - 1)
    )
    | _ -> printf "%s%!" (render_error data qs_sorted sorted)


let () =
    printf "Let's begin\n";
    test 1000

open Core.Std


let rec quicksort3 lst =
    let open List in
    match lst with
    | [] | [_] -> lst
    | hd :: _ ->
        match map [(<); (=); (>)] (fun f -> filter lst (fun i -> f i hd)) with
        | [l; c; r] -> concat [quicksort3 l; c; quicksort3 r]
        | _ -> assert false