Prolog语言中的冒泡排序

Question

我必须实现冒泡排序功能（排序算法）。

我已经实现了bubblesort和swap，这是bubblesort的帮助函数：

swap([X,Y|T1],[Y,X|T1]):-(Y<X,!).
swap([X|T1],[X|T2]):- swap(T1,T2).

bubblesort([],[]) :- !.
bubblesort(T1,T2) :- (bubblesort(swap(T1,T2),T2)).

我得到了一个无限循环。我必须保留函数的签名：

冒泡排序(T1,T2)

我在这个问题上停留了两个小时。有谁知道我该怎么做？

Answer 1

直到交换过程没有变化为止，继续交换。如果交换没有变化，那么您已经对列表进行了排序。

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

swap ( [ X, Y | Rest ], [ Y, X | Rest ] ) :-
    X > Y, ! .
swap ( [ Z | Rest ], [ Z | Rest1 ] ) : -
    swap (Rest, Rest1 ).

Answer 2

写出如此低效的东西几乎是痛苦的：

bubblesort(L, L1) :-
        (   bubble(L, L2)
        ->  bubblesort(L2, L1)
        ;   L = L1 ).

bubble([A, B|T], L) :-
        (   A > B
        ->  L = [B, A|T]
        ;   L = [A | L1],
            bubble([B|T], L1)).

:- bubblesort([2,4,2,3, 2, 6,6,3,1, 11, 2, 3, 1], Out).

Answer 3

简单的冒泡排序算法由两个主要循环组成：

1. 遍历列表，“交换”每个循环一对元素，如果它们不是“按顺序”（内循环）。
2. 对结果重复 (1)，直到列表完全排序（外循环）。

内部循环 (1) 可以这样表示：

% performs a single pass of a bubble-sort on a list
do_bubble_sort([], []).
do_bubble_sort([X], [X]).
do_bubble_sort([X0,X1|Xs], [X0|Rem]) :-
    X0 =< X1, !,
    do_bubble_sort([X1|Xs], Rem).
do_bubble_sort([X0,X1|Xs], [X1|Rem]) :-
    do_bubble_sort([X0|Xs], Rem).

上面的 do_bubble_sort/2 接受一个列表，如果不满足 =<，则递归地交换列表中的连续元素。代码>测试（第三条）。然后，该内部循环由外部循环谓词 bubble_sort/2 调用，如下所示：

% repeatedly performs a bubble sort on a list until it is sorted
bubble_sort(L, SL) :-
    do_bubble_sort(L, L0),
    (sorted_order(L0) ->
        SL = L0
    ;   bubble_sort(L0, SL)
    ).

该谓词采用输入列表并递归应用 do_bubble_sort/2 直到谓词 < code>sorted_order/1 结果成功，即列表最终排序。 sorted_order/1 可以这样定义：

% checks a list of things are in sorted (ascending) order
sorted_order([]).
sorted_order([_]) :- !.
sorted_order([X0,X1|R]) :-
    X0 =< X1,
    sorted_order([X1|R]).

该谓词采用一个列表并递归地检查每对连续元素是否按排序顺序（通过 =< 测试，就像我们在 do_bubble_sort/2 中使用的那样 - 这很重要，否则算法可能不会终止！）

Answer 4

该问题是由递归查询引起的。查询冒泡排序(T1, T2)时，
它查询bubblesort(swap(T1, T2), T2)，然后通过bubblesort/2的第二个子句，
bubblesort(swap(swap(T1, T2), T2'), T2)和T2统一为T2，然后循环。
它永远不会得到 swap(T1, T2) 查询的第一个结果。

Answer 5

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

Answer 6

bubbleSort(InputList,SortList):-swap(InputList,List),
                                 !,
                                 printList(List),
                                 bubbleSort(List,SortList).
bubbleSort(SortList,SortList).

swap([X,Y|T],[Y,X|T]):-X>Y.
swap([Z|T],[Z|T1]):-swap(T,T1).

printList([]):-nl.
printList([Head|List]):-write(Head),
                        write(' '),
                        printList(List).