このディレクトリの索引
http://toro.2ch.net/test/read.cgi/tech/1342966104/243
#  [1] 授業単元:アルゴリズムとデータ構造 
#  [2] 問題文(含コード&リンク): 
#  ・問 マルチキークイックソートを非再帰で実装せよ。 
#  マルチキークイックソートは文字列を辞書順にソートする手法である。 
#  例えば、文字列appleを5回巡回し、5つの文字列を生成する。 
#  この5つの文字列を辞書順にソートすると、以下のようになる。 
#   
#  巡回     ソート後 
#  apple          apple 
#  pplea         eappl 
#  pleap  →    leapp 
#  leapp          pleap 
#  eappl          pplea 
#   
#  実際には文字列appleを2倍にし巡回文字列を得る。 
#  例 : appleapple 
#  この文字列に対して非再帰のマルチキークイックソートを適用せよ。 
#   

マルチキークイックソートは文字列を辞書順にソートする(_文字列,_辞書順に整列した文字列) :-
        マルチキークイックソートの整列対象文字列の生成(_文字列,_整列対象文字列ならび),
        辞書順整列(_整列対象文字列ならび,_辞書順に整列した文字列).

マルチキークイックソートの整列対象文字列の生成(_文字列,_整列対象文字列ならび) :-
        atom_chars(_文字列,_文字ならび),
        atom_length(_文字列,_n),
        findall(_回転した文字列,(
                    between(1,_n,N),
                    ならびの回転(左方向,N,L,_回転した文字ならび),
                    atom_chars(_回転した文字列,_回転した文字ならび)),
                _整列対象文字列ならび).

辞書順整列([],[]).
辞書順整列([_軸要素文字列|_残り文字列],_辞書順に整列した文字列) :-
        辞書順分割(_軸要素文字列,_残り文字列,_より小さい文字列,_等しいかより大きい文字列),
        辞書順整列(_より小さい文字列,_整列したより小さい文字列),
        辞書順整列(_等しいかより大きい文字列,_整列した等しいかより大きい文字列),
        append(_整列したより小さい文字列,[_軸要素文字列|_整列した等しいかより大きい文字列],_辞書順に整列した文字列).

辞書順分割(_軸要素文字列,[],[],[]).
辞書順分割(_軸要素文字列,[_文字列|R1],L1,L2) :-
        atom_chars(_軸文字列,_文字ならび_1),
        atom_chars(_文字列,_文字列ならび_2),
        辞書順分割(_文字ならび_1,_文字ならび_2,L1,L2,R1,R2),
        辞書順分割(_軸要素文字列,R1,R1,R2).

辞書順分割(_文字ならび_1,_文字ならび_2,L1,R2,R1,R2) :-
        辞書順文字列の比較(_軸要素文字ならび_1,_文字ならび,_文字ならび,_),
        atom_chars(_文字列,_文字ならび),
        L1 = [_文字列|R1],!.
辞書順分割(_文字ならび_1,_文字ならび_2,R1,L2,R1,R2) :-
        辞書順文字列の比較(_軸要素文字ならび_1,_文字ならび,_,_文字ならび),
        atom_chars(_文字列,_文字ならび),
        L2 = [_文字列|R2],!.

辞書順文字列の比較([],[],[],[]) :- !.
辞書順文字列の比較(L,[],[],L) :- !.
辞書順文字列の比較([],L,[],L) :- !.
辞書順文字列の比較([_文字|R1],[_文字|R2],[_文字|R3],[_文字|R4]) :-
        辞書順文字列の比較(R1,R2,R3,R4),!.
辞書順文字列の比較([_文字_1|R1],[_文字_2|R2],[_文字_1|R1],[_文字_2|R2]) :-
        英大文字(_文字_1),
        英小文字(_文字_2),
        to_upper(_文字_2,_文字_1),!.
辞書順文字列の比較([_文字_1|R1],[_文字_2|R2],[_文字_2|R2],[_文字_1|R1]) :-
        英小文字(_文字_1),
        英大文字(_文字_2),
        to_upper(_文字_1,_文字_2),!.
辞書順文字列の比較([_文字_1|R1],[_文字_2|R2],[_文字_1|R1],[_文字_2|R2]) :-
        _文字_1 @< _文字_2,!.
辞書順文字列の比較([_文字_1|R1],[_文字_2|R2],[_文字_2|R2],[_文字_1|R1]) :-
        _文字_1 @>= _文字_2,!.

英小文字(_英小文字) :-
        _英小文字 @>= 'a',
        _英小文字 @=< 'z'.

英大文字(_英大文字) :-
        _英大文字 @>= 'A',
        _英大文字 @=< 'Z'.