MLのクイックソート

quicksort([],[]).
quicksort([A|B],C) :-
partition(B,A,B1,B2),
quicksort(B1,C1),
quicksort(B2,C2);
append(C1,[A|C2],C).

partition([],_,[],[]).
partition([D|B],A,[D|B1],B2) :-
D < A,
partition(B,A,B1,B2).
partition([D|B],B1,[D|B2]) :-
D >= A,
partition(D,A,B1,B2).

このプログラムがどのように動いているのか、
よくわかりません。誰か、どう処理しているのか教えてください。

No.4 ベストアンサー 回答者： salsberry 回答日時： 2009/07/07 21:42

No.3です。

昨夜回答した後一晩経っても違和感が消えず、見直してみました。
このプログラムはMLではなくてPrologですね。
その点以外はNo.3で書いた内容の修正はありません。

> この３つの部分が具体的に何をしているのか
> 分からないです。

> quicksort([A|B],C) :-

quicksort()という述語を定義する。:-　の後ろ、ピリオドまでがquicksort()の本体部。本体部でquicksort()を参照する再帰的定義になっている。
quicksort(B2,C2)の後ろのセミコロンはコロンが正しいはず。

> partition(B,A,B1,B2),

リストBの内容をB1とB2に分ける。B1の要素はA未満の値、B2の要素はA以上の値。
ただし、No.3でも書いたとおりpartition()の定義が間違っている。

> append(C1,[A|C2],C).

リストC1とリスト[A|C2]を連結したものをCとする。

参考URL：http://ja.wikipedia.org/wiki/Prolog

この回答へのお礼

二回も回答ありがとうごいます。
Prologで調べて見ると同じようなプログラムを発見できました。
MLの説明に載っていたので、まさかMLでなくPrologだと思いませんでした。
助かりました。

お礼日時：2009/07/09 18:22

No.3 回答者： salsberry 回答日時： 2009/07/06 21:18

久しくMLのコードを書いていないのでうろ覚えで書きます。

partition(W, X, Y, Z)は「リストWを、X未満の値からなるリストYとX以上の値からなるリストZに分割する」という意味になるのだと想像できますが、一番下に書かれている3引数のpartition()の定義が謎ですね。きっと書き写し間違いなのでしょうけれど。

No.2 回答者： Tacosan 回答日時： 2009/07/06 00:58

同感＞#1.

クイックソートのアルゴリズムを「そのまま」実装した, って感じ.

No.1 回答者： rabbit_cat 回答日時： 2009/07/06 00:48

＞このプログラムがどのように動いているのか、よくわかりません

どこが分からないのかがわからないと教えようがありません。

プログラム自体では、クイックソートを普通に実装したもので、それほど難しいところ（トリッキーなところ）があるとも思えないのですが。

この回答への補足

言葉が足りず、すいませんでした。
quicksort([A|B],C) :-
partition(B,A,B1,B2),
append(C1,[A|C2],C).
この３つの部分が具体的に何をしているのか
分からないです。

補足日時：2009/07/06 21:14