Prolog语言中的冒泡排序

发布于 2024-10-13 02:55:42 字数 401 浏览 15 评论 0原文

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

我已经实现了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)

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

原文

I must implement the bubble sort function (the sorting algorithm).

I have already implemented bubblesort and swap, a help function for 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)).

I get an infinite loop. I must keep the signature of the function:

bubblesort(T1,T2)

I'm stuck on this question for 2 hours. Does anyone have an idea how I can do that?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

等待我真够勒 2024-10-20 02:55:43

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

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 ).

Until there is no change in swap procedure, keep swapping. If there was no change in swap then you have sorted list.

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 ).

回复收藏 0 原文

寂寞美少年 2024-10-20 02:55:43

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

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).

It almost hurts to write something so inefficient:

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).

回复收藏 0 原文

压抑⊿情绪 2024-10-20 02:55:43

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

遍历列表，“交换”每个循环一对元素，如果它们不是“按顺序”（内循环）。
对结果重复 (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 中使用的那样 - 这很重要，否则算法可能不会终止！）

The simple bubble sort algorithm is made up of two main loops:

Traverse the list, 'swapping' each pair of elements if they are not 'in order' (inner loop).
Repeat (1) on the result until the list is completely sorted (outer loop).

The inner loop (1) can be expressed like this:

% 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 above takes a list, and recursively swaps consecutive elements along the list if they don't satisfy the =< test (3rd clause). This inner loop is then called by the outer loop predicate, bubble_sort/2, as shown below:

% 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)
    ).

This predicate takes the input list and recursively applies do_bubble_sort/2 until the predicate sorted_order/1 succeeds on the result, i.e., if the list is eventually sorted. sorted_order/1 can be defined like this:

% 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]).

This predicate takes a list and recursively checks that each pair of consecutive elements are in sorted order (by way of the =< test, just as we're using in do_bubble_sort/2 - this is important, otherwise the algorithm mightn't terminate!)

回复收藏 0 原文

開玄 2024-10-20 02:55:43

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

回复收藏 0 原文

天冷不及心凉 2024-10-20 02:55:43

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

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

回复收藏 0 原文

初心 2024-10-20 02:55:43


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).


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).

回复收藏 0 原文

~没有更多了~