Skip to content
TheChatArchiveThe Chat Archive
Qwenqwen3-235b-a22b-no-thinking· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

Coqでクイックソートのプログラムを書いてください。

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-opus-4-20250514’s answer.
  1. User

    Coqでクイックソートのプログラムを書いてください。

  2. Qwen Assistant

    以下は、Coq でクイックソート(Quick Sort)を実装した例です。Coq ではプログラムを書くだけでなく、その正しさ(たとえば「ソートされたこと」や「元の要素と同じ要素のみが含まれる」など)を証明することもできます。

    ここではまず、関数としてのクイックソートを定義し、その後に簡単な説明をつけます。証明部分については必要に応じて拡張可能です。


    ✅ Coq でのクイックソートの実装

    Require Import List.
    Require Import Arith.
    Require Import Lia.
    Import ListNotations.
    
    (* 比較関数:自然数の比較 *)
    Definition leq (x y : nat) : bool := x <=? y.
    
    (* 指定した述語に対して、リストを2つの部分に分割する補助関数 *)
    Fixpoint partition {A} (f : A -> bool) (l : list A) : list A * list A :=
      match l with
      | [] => ([], [])
      | a :: l' =>
        let (s, t) := partition f l' in
        if f a then (a :: s, t) else (s, a :: t)
      end.
    
    (* クイックソートの定義 *)
    Fixpoint qsort (l : list nat) : list nat :=
      match l with
      | [] => []
      | pivot :: l' =>
        let (left, right) := partition (leq pivot) l' in
        qsort left ++ [pivot] ++ qsort right
      end.
    

    🔍 実行例

    REPL (coqtop) または Eval コマンドを使って動作確認ができます:

    Eval compute in (qsort [3; 1; 4; 1; 5; 9; 2; 6]).
    (* 結果: [1; 1; 2; 3; 4; 5; 6; 9] *)
    

    📝 補足

    • この実装では、リストの先頭要素 pivot をピボットとして使い、partition 関数で「pivot 以下のもの」と「より大きいもの」に分割しています。
    • partition 関数は総称的に使えるよう A 型に対して定義されていますが、ここでは nat 型に限定して使っています。
    • ++ はリストの連結演算子です。

    🧪 追加:ソートの正当性証明(簡易版)

    必要であれば、この関数が本当に「ソートしている」ことや、「元のリストと要素が等しい多重集合である」ことを証明できます。以下はその準備としての述語の定義です。

    (* リストがソート済みかどうかを判定する関数 *)
    Fixpoint sorted (l : list nat) :=
      match l with
      | [] => true
      | a :: l' =>
        match l' with
        | [] => true
        | b :: _ => a <=? b && sorted l'
        end
      end.
    
    (* ソートの結果が本当にソートされているか評価 *)
    Example test_sorted: sorted (qsort [3; 1; 4; 1; 5; 9; 2; 6]) = true.
    Proof. reflexivity. Qed.
    

    📚 必要なライブラリ

    上記コードを動かすには、次のようなライブラリのインポートが必要です:

    Require Import List.
    Require Import Arith.
    Require Import Lia.
    Import ListNotations.
    

    必要があれば、要素の順序の保持や多重集合としての等価性(Permutation)についても証明できます。それを希望すれば、追加で証明付きバージョンを提供します!


    何か他にもご希望がありましたらお知らせください!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.