CODEWITHSUNDEEP
prologbubble-sort
tech-ref
tech-ref

Reputation: 279

Bubble sort in Prolog language

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?

Upvotes: 3

Views: 15997

Answers (7)

Frank Schwidom
Frank Schwidom

Reputation: 146

Another version of bubble sort is:

bs(L1,L2) :- true
, ( append(X,[A,B|Y],L1), A > B)
    -> ( append(X,[B,A|Y],T), bs(T,L2) )
    ; L1 = L2
.

A short test:

?- permutation( [1, 2, 3, 4], L), bs( L, X), writeln( L - X), false.
[1,2,3,4]-[1,2,3,4]
[1,2,4,3]-[1,2,3,4]
[1,3,2,4]-[1,2,3,4]
[1,3,4,2]-[1,2,3,4]
[1,4,2,3]-[1,2,3,4]
[1,4,3,2]-[1,2,3,4]
[2,1,3,4]-[1,2,3,4]
[2,1,4,3]-[1,2,3,4]
[2,3,1,4]-[1,2,3,4]
[2,3,4,1]-[1,2,3,4]
[2,4,1,3]-[1,2,3,4]
[2,4,3,1]-[1,2,3,4]
[3,1,2,4]-[1,2,3,4]
[3,1,4,2]-[1,2,3,4]
[3,2,1,4]-[1,2,3,4]
[3,2,4,1]-[1,2,3,4]
[3,4,1,2]-[1,2,3,4]
[3,4,2,1]-[1,2,3,4]
[4,1,2,3]-[1,2,3,4]
[4,1,3,2]-[1,2,3,4]
[4,2,1,3]-[1,2,3,4]
[4,2,3,1]-[1,2,3,4]
[4,3,1,2]-[1,2,3,4]
[4,3,2,1]-[1,2,3,4]
false.

This works with swi-prolog.

Upvotes: 0

Peetu--p2
Peetu--p2

Reputation: 9


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

Upvotes: 0

T.Dilak
T.Dilak

Reputation: 11

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

Upvotes: 0

ppeczek
ppeczek

Reputation: 51

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

Upvotes: 5

Yau-Hsien Huang
Yau-Hsien Huang

Reputation: 11

The problem was caused by recursive querying. When querying bubblesort(T1, T2), it queries bubblesort(swap(T1, T2), T2), then, by second clause of bubblesort/2, bubblesort(swap(swap(T1, T2), T2'), T2) and T2 is unified as T2, and then loop. It never get the first result of swap(T1, T2) query.

Upvotes: 1

salva
salva

Reputation: 10242

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

Upvotes: 2

user206428
user206428

Reputation:

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

  1. Traverse the list, 'swapping' each pair of elements if they are not 'in order' (inner loop).
  2. 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!)

Upvotes: 1

Related Questions