このディレクトリの索引
http://hibari.2ch.net/test/read.cgi/tech/1312201995/826
#  [1] 授業単元:クイックソート 
#  [2] 問題文(含コード&リンク): http://ime.nu/ideone.com/duPFX 
#  
#  問題1. 整数データの配列a[], 全体のサイズn を引数にとり、単純なpivot(=x とする) 
により
#  x 以下の左部分とx より大きな右部分に分割して、pivot の値, 左部分、右部分を
#  表示する関数を作成して正しく動くことを確認せよ。
#  
#  問題2. 整数データの配列に対してソートをかける関数を、クイックソートで作成し、正
しく動くことを確認せよ。
#  ただし、pivot は単純なものでよい。これをquick と呼ぶ。
#  
#  問題2. 整数データの配列に対してソートをかける関数を、クイックソートで作成し、正
しく動くことを確認せよ。
#  ただし、pivot は単純なものでよい。これをquick と呼ぶ。
#  
#  問題3. 問題2 を変更して、pivot を両端と中央での値の3個の値の中央値として
#  クイックソートを作成し、正しく動くことを確認せよ。
#  これをquick2 と呼ぶことにする。
#  
#  問題4. 問題3 を変更して、もし配列のサイズが10 以下であれば挿入ソートを
#  行うように再帰呼び出しを変更しなさい。これをquick3 と呼ぶことにする。
#  
#  問題5.Merge ソート,quick,quick2,quick3 について時間計測をして比較しなさい
#  

軸要素を得る([A],A) :- !.
軸要素を得る([A,B],A) :- !.
軸要素を得る(_a,_x) :-
        要素数が偶数の場合(_a,A,B,C).
        中間値(A,B,C,_x),!.
軸要素を得る(_a,_x) :-
        要素数が奇数の場合(_a,A,B,C),
        中間値(A,B,C,_x),!.

要素数が偶数の場合(_a,_x) :-
        append([A|R1],[B|R2],_a),
        length(R1,N),
        length(R2,N),
        last(R2,C),!.

要素数が奇数の場合(_a,_x) :-
        append([A|R1],[B|R2],_a),
        length([A|R1],N),
        length(R2,N),
        last(R2,C),!.

quick2([],[]).
quick2(_ならび,_整列されたならび) :-
        軸要素を得る(_ならび,_x),
        '単純なpivot(=x とする)によりx 以下の左部分とx より大きな右部分に分割して'(_ならび,_x,_左部分,_右部分),
        quick2(_左部分,_整列された左部分),
        quick2(_右部分,_整列された右部分),
        append(_整列された左部分,[_x|_整列された右部分],_整列されたならび).