読者です 読者をやめる 読者になる 読者になる

チラシの裏

プログラミングとか色々

ちょっとだけクイックソート

OCaml

よい実装かどうかは抜きにして、一般的な関数型言語ではリストに対するクイックソートを簡単に書く事ができます。 一方、そのようなよく見かける実装ではリストの結合を再帰内で用いていますが、 一般に関数型言語ではO(n)の時間計算量を要するため、リストの結合を用いる事はよくないとされています。

今回はアキュムレータを用いる事でリストの結合を用いずにクイックソートを実装したいと思います。

以下の様なリストに対するクイックソートの実装を良く見かける事でしょう。

let rec quicksort leb = function
  | [] -> []
  | x :: xs ->
      let (lge, llt) = List.partition (leb x) xs in
      quicksort leb llt @ [x] @ quicksort leb lge
(* quicksort ( <= ) [3; 1; 4; 1; 5; 9; 2] *)

この実装の問題点の一つとしては冒頭の通りです。 他にも問題点は多々あるでしょうがここでは割愛します。

ここで、quicksortの引数を増やす事によってリストの結合を使わずに書く事ができます。

let rec quicksort aux leb = function
  | [] -> aux
  | x :: xs ->
      let (lge, llt) = List.partition (leb x) xs in
      quicksort (x :: quicksort aux leb lge) leb llt
let quicksort leb l = quicksort [] leb l

どうせpivot以下の要素とそれより大きい要素に分ける操作がO(n)なのでオーダー記法で見れば変化ありませんが、ちょっとだけ(定数倍)早くなったことでしょう。 元の実装がダメダメなのでまだまだ改善の余地は有りますが、ここでは深く追求しません。

実装を改めた際に気になるのはその正当性でしょう。 前者の実装は「Coq クイックソート」等で検索すると定理証明支援系を用いた証明を多数見つけられます。 僕もCoqを使って証明しようとしたのですが、停止性で躓いて関数の定義すらできませんでした。 Error: Nested recursive function are not allowed with Functionって何なんでしょうね…