Bubble sort на языке Пролог

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

Я получаю бесконечный цикл. Я должен сохранить подпись функции:

BubbleSort (Т1, Т2)

Я застрял в этом вопросе на 2 часа. У кого-нибудь есть идеи, как я могу это сделать?

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(T1, T2) он запрашивает bubblesort(swap(T1, T2), T2), затем по второму предложению bubblesort/2, bubblesort(swap(swap(T1, T2), T2'), T2) и T2 объединяется в T2, а затем циклОн никогда не получит первый результат запроса swap(T1, T2).

Answer 3

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

Answer 4

Почти больно писать что-то неэффективное:

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 5

Простой алгоритм сортировки пузырьков состоит из двух основных циклов:

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 выше берет список и рекурсивно меняет последовательные элементы в списке, если они не удовлетворяют критерию =< (3-е предложение). Этот внутренний цикл затем вызывается предикатом внешнего цикла 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, пока предикат 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 - это важно, иначе алгоритм может не прекратить!)