algorithm - 了解 Prolog 中的冒泡排序解决方案

Question

这个冒泡排序解决方案在 Prolog 中如何工作？

bubblesort([], []).
bubblesort([H], [H]).
bubblesort([H|D], R) :-
    bubblesort(D, E),
    [B|G] = E,
    (  (H =< B, R = [H|E])
    ;  (H > B,  bubblesort([B,H|G], R))
    ).

这是一个跟踪示例:https://pastebin.com/T0DLsmAV

我知道 bubblesort(D,E) 行负责将其排序为一个元素，但我不明白它是如何工作的。我了解 prolog 中列表的基础知识，但仍然无法弄清楚该解决方案的运作方式。

Answer 1

这段代码的主要困难是选择了错误的变量名，这使得逻辑比需要的更难理解。

前两个案例显然是基本案例。第一个说“空列表已经排序”，第二个说“单例列表已经排序”。这应该是有道理的。第三种情况是事情变得有趣的地方。

让我们来看看第一部分。

bubblesort([H|D], R) :-
    bubblesort(D, E),

到目前为止，我们将结果命名为 R 并将输入分解为第一个元素 H 和尾部 D .从那里开始，我们已经说过，让我们对输入的尾部进行冒泡排序，并将其称为 E。也许这会更容易理解？

bubblesort([H|T], Result) :-
    bubblesort(T, TSorted),

接下来，

    [B|G] = E,

同样，不好的名字，但作者在这里打算做的很简单:拆开尾部排序的结果，这样我们就可以讨论排序后的尾部中的下一项是否是该位置的正确元素，或者如果它需要与我们输入的头部交换位置。让我们重命名:

    [HeadOfTSorted|RestOfTSorted] = TSorted,

现在我们有一个条件。把它想象成添加到一个排序列表中。假设你有一些元素，比如 3，我给你一个排序列表。你想确定你的 3 是在前面还是其他地方。好吧，假设我给了你一个看起来像 [5,7,19,23,...] 的排序列表。你会知道你的 3 就在它需要的地方，你会交回 [3,5,7,19,23,...]。这正是条件的第一种情况:

    (  (H =< HeadOfTSorted, Result = [H|TSorted])

现在考虑另一种情况，我给你一个以 [1,2,...] 开头的列表。你知道你不能只把 3 放在开头然后还给我 [3,1,2,...]。但是你真的不知道 3 去哪儿了；它只是一开始就没有。因此，您需要做的是对列表的其余部分进行排序，其中 3 在开头，在 1 之后:[1 | resorted([3,2,...])].这实际上是条件的另一个分支:

    ;  (H > HeadOfTSorted,  bubblesort([HeadOfTSorted,H|RestOfTSorted], R))
    ).

希望这对您有所帮助!