Prolog 寫氣泡排序法 Bubble Sort

看到有人還在寫 Prolog 語言的氣泡排序法 ( http://lethalman.blogspot.com/2011/02/bubble-sort-for-prolog.html ),就來回顧一下。氣泡排序法對任何程式語言都是很好的入門題,因為程式結構是很標準的洋蔥結構:最小的處理單位是二數字比大小,然後是一列數字兩兩相對較大的浮上來,最外層是將一列數字依序讓每個數字浮到該有的大小的位置。 (好繞口,簡單的概念很難用口語明確解釋。)

Luca 的程式傾向於一般程式設計師的想法,會用具體的符號像 sorted, unsorted 來表示函數的求值結果。不過,我所欣賞 Prolog 的美妙就是它不是用來寫程式,而是寫一些句子來限定問題或限定答案的範圍。所寫的不是函數而是 predicate , predicate 我們用中文說明可能會說是狀態的描述。例如 father(Someone, ‘John’) 就是說誰是 John 的爸爸,有主詞、受詞和動詞,是完整的句子,而比較不會用 father(Someone, ‘John’, YesNo) 來說誰是不是 John 的爸爸呢,是或不是的答案放在 YesNo 裡頭。而 Luca 所提到的 Roman 的程式,是蠻熟晰的 tail recursion 格式,是一種很成熟的程式技巧,藉由一個額外的 accumulating parameter 使任何遞迴呼叫都出現在最後,這種技巧可以讓 Prolog 程式執行得比較有效率。

好!我的程式,首先:二數字比大小不用寫, Prolog 本來就有,只要寫 M > N 就是判斷 M 是不是大於 N ,或者寫 M =< N 判斷 M 是不是不等於或小於 N 。

Bubbling!冒泡程序,要藉由 M > N 或 M =< N 做基礎,使一列數字較大的儘量向同一邊浮上去,或是讓較小的向另一邊沉下去。這裡我考慮一般寫程式都是用陣列,把一列處理完的數字從右邊開始縮減範圍,可是到 Prolog 語言來看, list 都是 [ A | [ B | [ C | … ] ] ] 這種結構,從頭開始拆掉一個元素比較簡單,所以把冒泡程序寫成比較小的數字往左邊沉下去。

bubble([E], [E]).
bubble([H|T], [S,H|Z]) :-
  bubble(T, [S|Z]), H > S, !.
bubble([H|T], [H,S|Z]) :-
  bubble(T, [S|Z]).

這樣,如果求 bubble([43,1,6,79,50,2],Z) 會得到 Z = [1, 43, 2, 6, 79, 50] ,最小的數字鐵定靠到最左邊,之後就可以直接把頭元素拆掉。所以,最外層程式為:

bubblesort([], []).
bubblesort([H|T], [H1|Z]) :-
  bubble([H|T], [H1|T1]),
  bubblesort(T1, Z).

每次冒泡一次 ( bubble/2 ) 就可以把結果的尾巴 ( T1 ) 拆出來再排序一次 ( bubblesort/2 ) ,排到最後沒資料可以排了,自然而然結束了。

求值時使用 bubblesort([43,1,6,79,50,2],Z) ,得到 Z = [1, 2, 6, 43, 50, 79] 。

廣告

About 黃耀賢 (Yau-Hsien Huang)

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

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s