Bubble sort in Prolog language

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 (T1, T2)

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

Answer 1

mergesort([],[]). /* covers special case */ 
mergesort([A],[A]). 
mergesort([A,B|R],S) :- 
    split([A,B|R],L1,L2), 
    mergesort(L1,S1), 
    mergesort(L2,S2), 
    merge(S1,S2,S). 

split([],[],[]). 
split([A],[A],[]). 
split([A,B|R],[A|Ra],[B|Rb]) :- split(R,Ra,Rb). 

merge(A,[],A). 
merge([],B,B). 
merge([A|Ra],[B|Rb],[A|M]) :- A =< B, merge(Ra,[B|Rb],M). 
merge([A|Ra],[B|Rb],[B|M]) :- A > B, merge([A|Ra],Rb,M). 

This example looks very usefull

Answer 2

Простой bubble sort algorithm состоит из двух основных циклов:

1. Traverse список «обменивать» каждую пару элементов, если они не являются «в порядке» (внутренний петля).
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, пока предикат 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 3

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

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 4

проблема была вызвана рекурсивными запросами. При запросе bubblesort(T1, T2), он запрашивает bubblesort(swap(T1, T2), T2), а затем, с помощью второго пункта из bubblesort/2, bubblesort(swap(swap(T1, T2), T2'), T2) и T2 едина, как T2, а затем цикл. Он никогда не получает первый результат запроса swap(T1, T2).

Answer 5

До тех пор пока нет изменений в процедуре свопинга, продолжайте меняться. Если изменений в swap не было, то вы отсортировали список.

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 6

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