Prolog排序系列: Comb Sort

本來想繼續寫 Comb Sort ,但從維基百科了解一番之後,覺得寫法大概跟 Shell Sort 大同小異。原因很簡單,二者都是改良演算法, Comb Sort 沿用並改良 Bubble Sort ,而 Shell Sort 借用 Insertion Sort 或 Bubble Sort 應用在較小片段的資料範圍來改良 Insertion Sort。

Comb Sort 也是著眼在討論間隔多遠的資料互相比大小; Bubble Sort 是每一項資料都和固定間隔為 1 的另一項資料互相比較大小。而 Comb Sort 是先將這個間隔放到最大,大到是資料數目那麼大的間隔,之後依次將間隔按照某一個比例縮小,直到最後間隔為 1 。 Comb Sort 改良的效果,是讓一次從左到右兩兩比較資料而造成一輪的資料位置重新放置的輪次中,該跑到右邊的資料會比較快跑到右邊,而該跑到左邊的資料也會比較快跑到左邊。

實在懶得寫 Comb Sort 程式了,因為程式長相會和 Shell Sort 非常像。就寫個 Comb Sort 的起頭吧:

:- module(sort, [comb/2]).

comb(UnsortedList, SortedList) :-
    length(UnsortedList, Len),
    takegaps(Len, GapList),
    comb(GapList, UnsortedList, SortedList).
takegaps(0, []).
takegaps(Gap, [Gap|Rest]) :- Gap > 0,
    Gap1 is Gap / 1.247330950103979,
    Gap2 is floor(Gap1),
    takegaps(Gap2, Rest).
comb([], SortedList, SortedList).
comb([Gap|Rest], UnsortedList, SortedList) :-
    combTo(UnsortedList, Gap, UnsortedList1),
    comb(Rest, UnsortedList1, SortedList).
combTo(UnsortedList, Gap, UnsortedList1) :-
% comTo/3 是將 UnsortedList 的固定間隔 Gap 遠的資料兩兩依序比較並交換,像氣泡排序那樣
廣告

About 黃耀賢 (Yau-Hsien Huang)

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