このディレクトリの索引
http://hibari.2ch.net/test/read.cgi/tech/1291471791/659
#  [1] 授業単元:アルゴリズムとデータ構造 
#  [2] 問題文(含コード&リンク): 
#    クイックソートにより異なる15個の要素を配列するとき、比較回数の最小値と最大値求め、 
#    そのときに与えた要素をそれぞれ答えなさい。 
#    たとえば1、2、3、、、、15を与えると、105回となる。といったかんじです。 
#    
#    プログラムの提出はないです。 
#      
#  [4] 期限: 2010年12月17日13:00まで。 
#   

'クイックソートにより異なる15個の要素を配列するとき、比較回数の最小値と最大値求め、そのときに与えた要素をそれぞれ答えなさい。' :-
        findall([_比較回数,_15個の要素],(
                    15個の要素を生成(_15個の要素),
                    クイックソートの比較回数の最小値と最大値求め(_15個の要素,_比較回数),
                L),
        max(L,[_最大比較回数,_最大比較回数の時の15個の要素]),
        min(L,[_最小比較回数,_最小比較回数の時の15個の要素]),
        write_formatted('最小比較回数は要素が%tの時で%t回\n',[_最小比較回数の時の15個の要素,_最小比較回数]),
        write_formatted('最大比較回数は要素が%tの時で%t回\n',[_最大比較回数の時の15個の要素,_最大比較回数]),!.

15個の要素を生成(_15個の要素) :-
        順列([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],15,_15個の要素).

比較回数を記録したクイックソート([],0) :- !.
比較回数を記録したクイックソート([A|R1],_比較回数) :-
        比較回数を記録した分割(A,R1,_Aより小さいならび,_Aと等しいか大きいならび,0,_比較回数0),
        比較回数を記録したクイックソート(_Aより小さいならび,L3,_比較回数1),
        比較回数を記録したクイックソート(_Aと等しいか大きいならび,L4,_比較回数2),
        append(L3,[A|L4],L2),
        _比較回数 is _比較回数0 + _比較回数1 + _比較回数2.

比較回数を記録した分割(A,[],[],[],_比較回数,_比較回数) :- !.
比較回数を記録した分割(A,[B|R1],R2,[B|R3],_比較回数1,_比較回数) :-
        B @>= A,
        _比較回数2 is _比較回数1 + 1,
        比較回数を記録した分割(A,[B|R1],R2,[B|R3],_比較回数2,_比較回数).
比較回数を記録した分割(A,[B|R1],[B|R2],R3,_比較回数1,_比較回数) :-
        B @< A,
        _比較回数2 is _比較回数1 + 1,
        比較回数を記録した分割(A,[B|R1],[B|R2],R3,_比較回数2,_比較回数).