Prolog 氣泡排序

我寫過多少次氣泡排序了?雖然寫很多次,但是每看到 Lethalman 所寫的這篇Bubble sort for prolog @ Thoughts about computer technologies就覺得心神迷亂,他用的是直覺的、定義式的作法,做的太好了。

最近我閉起眼睛臨摹他這篇做法,仍沒有完成。

後來重新做一下我自己的版本。因為 Prolog 的基本資料結構 list 是將資料一個一個加在前端,所以很不容易做 bubble (大的數字浮上去/加在list後面) 。但可以反過來,作 sink (小的數字沉下去/加在list前面) ,所以我的沈降式氣泡排序法就是這樣:

bubble_sort([A], [A]) :- !.
bubble_sort(U, [A|S]) :- sink(U, [A|P]), bubble_sort(P, S).
sink([A], [A]).
sink([A|R], L) :- sink(R, [B|S]), (A =< B, !, L = [A,B|S]; L = [B,A|S]).

廣告

About 黃耀賢 (Yau-Hsien Huang)

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s