ソート

なんか書けた。mergeSortはあやしい。

/* insertSort */
insert([],E,[E]).
insert([X|XS],E,[X|RR]) :-
    E >= X,
    insert(XS,E,RR).
insert(XS,E,[E|XS]).

insertSort([],[]).
insertSort([X],[X]).
insertSort([X|XS],R) :-
    insertSort(XS,RR),
    insert(RR,X,R).

/* quickSort */
partition(_,[],[],[]).
partition(P,[X|XS],[X|SS],B) :-
    X < P,
    partition(P,XS,SS,B).
partition(P,[X|XS],S,[X|BB]) :-
    partition(P,XS,S,BB).

qsort([],[]).
qsort([P|X],R) :-
    partition(P,X,A,B),
    qsort(A,AA),
    qsort(B,BB),
    append(AA,[P|BB],R).

/* mergeSort */
merge(X,[],X).
merge([],Y,Y).
merge([X|XS],[Y|YS],[X|RR]) :-
    X =< Y,
    merge(XS,[Y|YS],RR).
merge([X|XS],[Y|YS],[Y|RR]) :-
    merge([X|XS],YS,RR).
mergeSort([],[]).
mergeSort([A],[A]).
mergeSort([A,B|XS],R) :-
    merge([A],[B],RR),
    mergeSort(XS,RRR),
    merge(RR,RRR,R).