Prolog中的Bubble Sort算法的聲明式解釋

Question

我對Prolog中的BubbleSort算法如何工作如何工作有些疑問。

我很清楚BubbleSort算法是如何工作的，所以我的疑問只與Prolog一階邏輯和聲明式解釋有關。

這是我的代碼：

bubbleSort(List, SortedList) :- swap(List, List1), 
           !, 
           bubbleSort(List1, SortedList). 

bubbleSort(SortedList, SortedList). 

/* swap predicate swap the two element if X come after Y in lexicographical order */ 
swap([X,Y|Tail], [Y,X|Tail]) :- X @> Y. 

/* If it is not true that X come after Y in lexicographical order let the head in its 
    original position and call the swap predicate on the sublist */ 
swap([Z|Tail], [Z|Tail1]) :- swap(Tail, Tail1). 

所以我對這個項目的說明性解釋一些疑問：

該方案的核心是冒泡/ 2謂詞執行的韻律在其中執行相鄰元素的最終交換的列表。

所以像交換/ 2謂詞工作程序，如果：

1）IF在子列表（X第一個元素）跟隨在子列表（Y）的第二元件在詞典順序是不好，所以執行交換。

2）否則X和Y是在正確的順序和嘗試在子列表執行TE交換尾

因此，舉例來說，如果我執行以下查詢：

[trace] ?- bubbleSort([3,2,1], Sorted). 

我獲得：

Call: (7) bubbleSort([3, 2, 1], _G399) ? creep 
Call: (8) swap([3, 2, 1], _G478) ? creep 
Call: (9) 3@>2 ? creep 
Exit: (9) 3@>2 ? creep 
Exit: (8) swap([3, 2, 1], [2, 3, 1]) ? creep 
Call: (8) bubbleSort([2, 3, 1], _G399) ? creep 

這裏調用冒泡/ 2第一個版本的原稿內部列表。要成爲TRUE，請調用swap/2謂詞的第一個版本，以檢查列表的前兩個元素是否彼此不按字典順序排列，這一事實是TRUE，因此交換這些元素。現在，swap/2謂詞被驗證，回來通過回溯和（爲了滿足bubbleSort/2）再次調用bubbleSort2現在說，原來的訂單列表是交換後的列表（其中第一和第二要素交換）

於是再次撥打冒泡而發生：

Call: (8) bubbleSort([2, 3, 1], _G399) ? creep 
Call: (9) swap([2, 3, 1], _G484) ? creep 
Call: (10) 2@>3 ? creep 
Fail: (10) 2@>3 ? creep 
Redo: (9) swap([2, 3, 1], _G484) ? creep 
Call: (10) swap([3, 1], _G480) ? creep 
Call: (11) 3@>1 ? creep 
Exit: (11) 3@>1 ? creep 
Exit: (10) swap([3, 1], [1, 3]) ? creep 
Exit: (9) swap([2, 3, 1], [2, 1, 3]) ? creep 

所以現在儘量滿足交換/ 2列表[2,3,1]，但現在這對前兩個元素不是按字典編排是不正確的因此第一個版本的swap/2謂詞失敗，所以它使用第二個版本，它簡單地在子列表** [3,1]上調用swap/2，其中的確是3按照1，所以交換它，我得到[1,3]列表。

這裏我有第一疑問：[2，1,3]在這一行：：

這個交換有關此子列表（從[3,1]到[1,3]）我獲得列表之後

Exit: (9) swap([2, 3, 1], [2, 1, 3]) ? creep 

爲什麼？這是因爲有滿意的交換後（尾，Tail1）斷言：

swap([Z|Tail], [Z|Tail1]) :- swap(Tail, Tail1). 

我有Tail1爲[1,3]所以z爲老人頭2和[Z | Tail1]爲[2 ，1,3]？

然而，現在是結束冒泡排序算法的第一韻律有以「大」元素在列表

執行繼續以同樣的方式結束，但我有一個疑問程序執行結束即：

Redo: (10) bubbleSort([1, 2, 3], _G399) ? creep 

：

Redo: (10) bubbleSort([1, 2, 3], _G399) ? creep 
    Exit: (10) bubbleSort([1, 2, 3], [1, 2, 3]) ? creep 
    Exit: (9) bubbleSort([2, 1, 3], [1, 2, 3]) ? creep 
    Exit: (8) bubbleSort([2, 3, 1], [1, 2, 3]) ? creep 
    Exit: (7) bubbleSort([3, 2, 1], [1, 2, 3]) ? creep 
Sorted = [1, 2, 3]. 

通過所以在最後調用冒泡/ 2謂詞有序列表

其中[1,2,3]是列表1。

現在我在第二個版本的冒泡/ 2謂語，這一個：

bubbleSort(SortedList, SortedList). 

在列表進行排序，並在排序列表是相同的（所以它意味着原有的列表完全排序）。

那麼這是什麼？基礎案例，一旦驗證，說程序執行必須結束？

所以執行回溯說，所有以前冒泡/ 2驗證，直到達到第一冒泡/ 2打電話說，這是vierified和統一排序與[1,2,3]列表

我的推理是否正確？對此有更多的說明性解釋嗎？

Answer 1

我認爲理解這個算法的關鍵是，當列表排序時，swap/2 失敗 - 空列表上沒有匹配。

從這裏開始第二個bubbleSort/2規則的必要性。