Prolog排序系列: Shell Sort

Shell Sort是個很囉唆的排序演算法,方法的精神與氣泡排序雷同,所謂精神是:不同的步驟分別處理不同的未排序部份,使結果的總合是一列排序的結果。 Shell Sort 是經過研究,不同的間距的資料各自排序,各自排序的結果前後覆蓋…… (老實說,看完 Wikipedia 的 Shell Sort 條目,我懂了演算法,卻看不出像是 shell 字面所講的剝殼那種層次感。)

Prolog程式寫起來,跟其他排序法相比較,長度真長,因為邏輯比較繁複吧!

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

shell(UnsortedList, SortedList) :-
    shell([701, 301, 132, 57, 23, 10, 4, 1], UnsortedList, SortedList).
shell([], SortedList, SortedList).
shell([Gap|Rest], UnsortedList, SortedList) :-
    length(UnsortedList, Len), Gap > Len, !,
    shell(Rest, UnsortedList, SortedList).
shell([Gap|Rest], UnsortedList, SortedList) :-
    separate(UnsortedList, Gap, UnsortedLists),
    findall(Slist, (member(Uslist,UnsortedLists), insertion(Uslist, Slist)),
            SortedLists),
    fuse(SortedLists, UnsortedList1),
    shell(Rest, UnsortedList1, SortedList).
separate(OriginList, Gap, SepLists) :-
    takelists(Gap, AccuLists),
    separate(OriginList, Gap, Gap, AccuLists, SepLists).
takelists(0, []).
takelists(N, [[]|Rest]) :- N > 0,
    N1 is N-1,
    takelists(N1, Rest).
separate([], _, _, SepLists, SepLists).
separate([H|Rest], N, Gap, AccuLists, SepLists) :-
    nth1(N, AccuLists, AccuList),
    N1 is N-1,
    p99:slice(AccuLists, 1, N1, LeftLists),
    N2 is N+1,
    length(AccuLists, Len),
    p99:slice(AccuLists, N2, Len, RightLists),
    append(LeftLists, [[H|AccuList]|RightLists], AccuLists1),
    (N =:= 1 -> N3 is Gap; N > 1 -> N3 is N-1),
    separate(Rest, N3, Gap, AccuLists1, SepLists).
fuse(OriginLists, FusedList) :-
    fuse(OriginLists, [], FusedList).
fuse(OriginLists, AccuLists, FusedList) :- lists:flatten(OriginLists, []), !,
    lists:reverse(AccuLists, FusedLists),
    lists:flatten(FusedLists, FusedList).
fuse(OriginLists, AccuLists, FusedList) :-
    findall(H, member([H|_],OriginLists), AccuList),
    findall(Rest, member([_|Rest],OriginLists), OriginLists1),
    fuse(OriginLists1, [AccuList|AccuLists], FusedList).

本程式用到 P99: Ninty-nine Prolog Problems 的 slice/4 ,定義如此:

:- module(p99, [slice/4]).

slice([], _, _, []).
slice(_, M, N, []) :- (M > N; M < 1; N < 1), !.
slice([_|Rest], M, N, Result) :- M > 1, N > 1, !,
    M1 is M-1,
    N1 is N-1,
    slice(Rest, M1, N1, Result).
slice([H|_], 1, 1, [H]).
slice([H|Rest], 1, N, [H|Rest1]) :- N > 1,
    N1 is N-1,
    slice(Rest, 1, N1, Rest1).

執行一例:

?- sort:shell([62,83,18,53,7,17,95,86,47,69,25,28], Sorted), write(Sorted), nl.
[7,17,18,25,28,47,53,62,69,83,86,95]
Sorted = [7, 17, 18, 25, 28, 47, 53, 62, 69|...] ;
false.
廣告

About 黃耀賢 (Yau-Hsien Huang)

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