クイックソート

以前、Webか本かなにかでクイックソートのコードを読んだことがあるのだけれど、雰囲気以外忘れてしまった気がする。ちょうど都合がよいので自分で書いてみることに。

let rec sort = function
  | [] -> []
  | pivot::rest ->
      let rec sep left right = function
        | [] -> (left, right)
        | hd::tl ->
            if hd < pivot
            then sep (hd::left) right tl
            else sep left (hd::right) tl in
      let (left, right) = sep [] [] rest in
      (sort left) @ (pivot::sort right)

let make_list n =
  let _ = Random.self_init in
  let max = 100000000 in
  let rec loop l i =
    if i > 0
    then loop (Random.int max::l) (i - 1)
    else l in
  loop [] n

let show_list f n =
  List.iter (fun x -> Printf.printf "<%d> " x) (f (make_list n))

ちなみに、後半はテスト用のコード。
以下は実行結果。

mitsu@garlic$ ocaml
        Objective Caml version 3.10.2

# #use "qs.ml";;
val sort : 'a list -> 'a list = <fun>
val make_list : int -> int list = <fun>
val show_list : (int list -> int list) -> int -> unit = <fun>
# show_list sort 10;;
<19618234> <25724514> <39820757> <51173925> <54357265> <61540548> <71565600> <84529876> <86925328> <98793717> - : unit = ()
#

最近思ったんだけども、例えば徹底的に末尾再帰になるようこだわっていると、私のレベルだとどうにも本来の意図が読み取りにくいコードになってしまう。

そうすると、なんというかそのコードがあまり好きでは無くなってくるきらいがあるので、基本はざっくりレベルにしておこうかと。とりあえず趣味だし、そんな方針で。