Prolog排序系列

最近重新認真寫 Prolog 程式,從敲按鍵盤的手感,覺得自己更了解SWI-Prolog了。

隨手寫個例行的排序實作,包括快速排序、氣泡排序、插入排序和選擇排序等。程式中遇到的問題,是在 insertion/2 和 selection/2 時,我不知道如何直接寫,而非得用到 accumulating parameters 技巧。接著想寫外殼排序 (Shell Sort) 時,覺得開始卡到了,不容易直接寫跨間距局部排序。

:- module(sort, [quick/2, bubble/2, insertion/2, selection/2]).

quick([], []).
quick([Pivot|Rest], SortedList) :-
    findall(N, (member(N,Rest), N =< Pivot), LessList),
   findall(N, (member(N,Rest), N > Pivot), GreaterList),
   quick(LessList, SortedLessList),
   quick(GreaterList, SortedGreaterList),
   append(SortedLessList, [Pivot|SortedGreaterList], SortedList).

bubble([], []).
bubble(UnsortedList, SortedList) :-
   bubbling(UnsortedList, [H|PartialUnsortedList]),
   bubble(PartialUnsortedList, PartialSortedList),
   SortedList = [H|PartialSortedList].

bubbling([], []).
bubbling([X], [X]) :- !.
bubbling([A,B], [B,A]) :- A > B, !.
bubbling([A,B], [A,B]) :- A =< B, !.
bubbling([A|Rest], Result) :-
   bubbling(Rest, [B|Rest1]),
   (A =< B, Result = [A,B|Rest1];
   A > B, Result = [B,A|Rest1]).

insertion(UnsortedList, SortedList) :-
   insertion(UnsortedList, [], SortedList).
insertion([], SortedList, SortedList).
insertion([H|Rest], AccuList, SortedList) :-
   findall(N, (member(N,AccuList), N =< H), LessList),
   findall(N, (member(N,AccuList), N > H), GreaterList),
   append(LessList, [H|GreaterList], AccuList1),
   insertion(Rest, AccuList1, SortedList).

selection(UnsortedList, SortedList) :-
   selection(UnsortedList, [], SortedList).
selection([], SortedList, SortedList).
selection(UnsortedList, AccuList, SortedList) :-
   takeMax(UnsortedList, M, UnsortedList1),
   AccuList1 = [M|AccuList],
   selection(UnsortedList1, AccuList1, SortedList).

takeMax([X], X, []) :- !.
takeMax([Max|List], Max, List) :- forall(member(N,List), Max > N), !.
takeMax([H|Rest], Max, List) :- !,
   takeMax(Rest, Max, Rest1),
   List = [H|Rest1].

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Prolog 並標籤為 。將永久鏈結加入書籤。