ExMurasakiQSort - デカルト言語 - 並列ロジック プログラミング言語 Wiki - デカルト言語 - 並列ロジック プログラミング言語

←　前のページに戻る

0.5 クイック・ソート

リストのソートを高速で行うプログラムを作成します。

ソートのアルゴリズムは、クイック・ソートを使います。

// リストのクイック・ソートのプログラム

// リストの追加処理:appendの処理
#xは()と#xのリスト追加です。
#zは#xと#yのリスト追加のとき、
(#a:#z)が(#a:#x)と#yのリスト追加です。

// quick sortの処理
()は、()のクイック・ソートである。

#xは、#listと#l1と#l2のqsplitであり、
#s1は、#l1のクイック・ソートであり、
#s2は、#l2のクイック・ソートであり、
#sは、#s1と(#x : #s2)のリスト追加である場合、
#sは、(#x : #list)のクイック・ソートである。

// 値の大小によるリストの分割処理
_は、()と()と()のqsplitです。

#y <= #xが成立し、
#xは、#listと#l1と#l2のqsplitである場合、
#xは、(#y : #list)と(#y : #l1)と#l2のqsplitです。

#xは、#listと#l1と#l2のqsplitである場合、
#xは、(#y : #list)と#l1と(#y : #l2)のqsplitです。

// 実行
#xは、(11 12 3 7 1 2 0 -1 10 9 4 8 5 6)のクイック・ソートですか？

このプログラムでは、リストの追加処理であるappend相当の処理を、リスト追加として最初に定義しています。

メインの処理は、クイック・ソートにより定義します。

さらに、クイックソートの中で、リストの分割処理のためにqsplitを定義しています。

さっそく実行してみましょう。

上のプログラムはsamples/qsort.mrsに入っているとします。

$ descartes murasaki samples/qsort.mrs

#xは、(11 12 3 7 1 2 0 -1 10 9 4 8 5 6)のクイック・ソートですか？
(-1 0 1 2 3 4 5 6 7 8 9 10 11 12)は、(11 12 3 7 1 2 0 -1 10 9 4 8 5 6)のクイック・ソートです。

正しくソートされてますね。

このプログラムは次に示すようなデカルト言語のプログラムにコンパイルされて実行されたものです。

 <M2 リスト追加 #x (() #x)>
        ;
 <M2 リスト追加 (#a:#z) ((#a:#x) #y)> 
　　　　　<M2 リスト追加 #z (#x #y)>
        ;
 <M2 クイック・ソート () (())>
        ;
 <M2 クイック・ソート #s ((#x : #list))> 
　　　　　<M2 qsplit #x (#list #l1 #l2)> 
　　　　　<M2 クイック・ソート #s1 (#l1)> 
　　　　　<M2 クイック・ソート #s2 (#l2)> 
　　　　　<M2 リスト追加 #s (#s1 (#x : #s2))>
        ;
 <M2 qsplit _ (() () ())>
        ;
 <M2 qsplit #x ((#y : #list) (#y : #l1) #l2)> 
　　　　　<compare #y <= #x> <M2 qsplit #x (#list #l1 #l2)>
        ;
 <M2 qsplit #x ((#y : #list) #l1 (#y : #l2))> 
　　　　　<M2 qsplit #x (#list #l1 #l2)>
        ;

? <printf '#xは、(11 12 3 7 1 2 0 -1 10 9 4 8 5 6)のクイック・ソートですか？' <\_n>>;
? <回答 (<M2 クイック・ソート #x ((11 12 3 7 1 2 0 -1 10 9 4 8 5 6))>)>;
? <print>;

--

--