SWI-Prologでのクイックソートの実装

2020-12-20 Prolog

SWI-Prologを使って、クイックソートを実装してみました。partition/4とappend/3は、SWI-Prologの独自の実装なので、他のPrologの実装だとこのままでは動かないかもしれません。

% クイックソート (quick sort)
quicksort([], []).
quicksort([Head | Tail], Sorted) :-
    partition(@>=(Head), Tail, Smaller, Larger),
    quicksort(Smaller, SortedSmaller),
    quicksort(Larger, SortedLarger),
    append(SortedSmaller, [Head | SortedLarger], Sorted).

% クイックソート (quick sort)

quicksort([], []).

quicksort([Head | Tail], Sorted) :-

partition(@>=(Head), Tail, Smaller, Larger),

quicksort(Smaller, SortedSmaller),

quicksort(Larger, SortedLarger),

append(SortedSmaller, [Head | SortedLarger], Sorted).

% 実行例
?- [quick_sort].
true.

?- quicksort([2, 5, 7, 1, 4, 6, 3], X).
X = [1, 2, 3, 4, 5, 6, 7] ;

?- quicksort([e, f, a, d, c, b, s], X).
X = [a, b, c, d, e, f, s].

% 実行例

?- [quick_sort].

true.

?- quicksort([2, 5, 7, 1, 4, 6, 3], X).

X = [1, 2, 3, 4, 5, 6, 7] ;

?- quicksort([e, f, a, d, c, b, s], X).

X = [a, b, c, d, e, f, s].

参考文献