このディレクトリの索引
http://pc12.2ch.net/test/read.cgi/tech/1263824755/851
#  [1] 授業単元:知識情報基礎実験 
#  [2] 問題文(含コード&リンク): 
#  乱数を希望数取得し、それをバブルソート、挿入ソート、クイックソート、ヒーブソートの各種を用いてソートせよ(4個のプログラムを作成する)。  
#  また、それぞれ比較回数、実行時間を計測せよ。 
#  
クイックソート(_ならび,_整列したならび) :-
   第一要素を分割値とする(_ならび,_分割値,_残りならび),
   分割値に対しての大小で二分割する(_分割値,_残りならび,_分割値より小さいかまたは等しい値ならび,_分割値より大きい値ならび),
   分割値より小さい値ならびを整列する(_小さい値ならび,_整列した小さい値ならび),
   分割値より大きい値ならびを整列する(_大きい値ならび,_整列した大きい値ならび),
   整列した二つのならびと分割値を結合する(_分割値,_整列した小さい値ならび,_整列した大きい値ならび,_整列した値ならび).
クイックソート([],[]).

第一要素を分割値とする([_分割値|_残りならび],_分割値,_残りならび).

分割値に対しての大小で二分割する(_,[],[],[]) :- !.
分割値に対しての大小で二分割する(_分割値,[A|R1],[A|R2],R3) :-
   A @=< _分割値,
   分割値に対しての大小で二分割する(_分割値,R1,R2,R3),!.
分割値に対しての大小で二分割する(_分割値,[A|R1],R2,[A|R3]) :-
   A @> _分割値,
   分割値に対しての大小で二分割する(_分割値,R1,R2,R3),!.

分割された部分を整列する(_分割された値ならび,_整列した分割された値ならび) :-
   クイックソート(_分割された値ならび,_整列した分割された値ならび),!.

整列した二つのならびと分割値を結合する(_分割値,_整列した分割値より小さいかまたは等しい値ならび,_整列した分割値より大きい値ならび,_整列した値ならび) :-
   append(_整列した分割値より小さいかまたは等しい値ならび,[_分割値|_整列した分割値より大きい値ならび],_整列した値ならび),!. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

クイックソート(_対象ならび,_整列された値ならび) :-
   第一要素を分割値とする(_対象ならび,_分割値,_残り対象ならび),
   分割値に対しての大小でならびを二分割する(_分割値,_残り対象ならび,_分割値より小さいかまたは等しい値ならび,_分割値より大きい値ならび),
   分割されたならびを部分的に整列する(_分割値より小さいかまたは等しい値ならび,_整列された分割値より小さいかまたは等しい値ならび),
   分割されたならびを部分的に整列する(_分割値より大きい値ならび,_整列された分割値より大きい値ならび),
   整列された二つのならびと分割値を結合する(_分割値,_整列された分割値より小さいかまたは等しい値ならび,_整列された分割値より大きい値ならび,_整列された値ならび).
クイックソート([],[]).

第一要素を分割値とする([_分割値|_残り対象ならび],_分割値,_残り対象ならび).

分割値に対しての大小でならびを二分割する(_,[],[],[]) :- !.
分割値に対しての大小でならびを二分割する(_分割値,[A|R1],[A|R2],R3) :-
   A @=< _分割値,
   分割値に対しての大小でならびを二分割する(_分割値,R1,R2,R3),!.
分割値に対しての大小でならびを二分割する(_分割値,[A|R1],R2,[A|R3]) :-
   A @> _分割値,
   分割値に対しての大小でならびを二分割する(_分割値,R1,R2,R3),!.

分割されたならびを部分的に整列する(_分割された値ならび,_整列された分割された値ならび) :-
   クイックソート(_分割された値ならび,_整列された分割された値ならび),!.

整列された二つのならびと分割値を結合する(_分割値,_整列された分割値より小さいかまたは等しい値ならび,_整列された分割値より大きい値ならび,_整列された値ならび) :-
   append(_整列された分割値より小さいかまたは等しい値ならび,[_分割値|_整列された分割値より大きい値ならび],_整列された値ならび),!. 

&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
クイックソート(L,X) :-
   第一要素を分割値とする(L,S,R),
   分割値に対しての大小でならびを二分割する(S,R,L1,L2),
   分割されたならびを部分的に整列する(L1,SL1),
   分割されたならびを部分的に整列する(L2,SL2),
   整列された二つのならびと分割値を結合する(P,SL1,SL2).
クイックソート([],[]).

第一要素を分割値とする([P|R],P,R).

分割値に対しての大小でならびを二分割する(_,[],[],[]) :- !.
分割値に対しての大小でならびを二分割する(P,[A|R1],[A|R2],R3) :-
   A @=< P,
   分割値に対しての大小でならびを二分割する(P,R1,R2,R3),!.
分割値に対して大小でならびを二分割する(P,[A|R1],R2,[A|R3]) :-
   A @> P,
   分割値に対しての大小でならびを二分割する(P,R1,R2,R3),!.

分割されたならびを部分的に整列する(L,X) :-
   クイックソート(L,X),!.

整列された二つのならびと分割値を結合する(P,SL1,SL2,L) :-
   append(SL1,[P|SL2],L),!.