* Problem 13: Write a predicate bubblesort(X,Y) that succeeds if Y is X, sorted from least to greatest. Items do not need to be unique.

The implementation of bubblesort should be based on the bubble sort algorithm

Hint: It might be helpful to define a helper relation bubble, in addition to bubblesort itself */

bubble(X, [], [X]). bubble(X, [Y|Ys], [X,Y|Ys]) :- X =< Y, !. bubble(X, [Y|Ys], [Y|Zs]) :- X > Y, bubble(X, Ys, Zs).

bubblesort([], []). bubblesort([X|Xs], Sorted) :- bubblesort(Xs, SortedTail), bubble(X, SortedTail, Sorted).

/* Problem 13 Test: */ %:- bubblesort([],[]). % SUCCEED %:- bubblesort([4, 3, 2, 1],[1, 2, 3, 4]). % SUCCEED %:- bubblesort([4, 3, 2, 1, 4],[1, 2, 3, 4, 4]). % SUCCEED

%:- bubblesort([4, 3, 2, 1],[1, 2, 4, 3]) -> fail ; true. % FAIL

/* Problem 14: Write a predicate merge(A,B,M) that succeed if the list M has all the items from lists A and B in increasing order. Items do not need to be unique.

Hint: You may use predicates defined in previous problems or write helper predicates to aid in solving this problem. */

/* Problem 14 Test: */ %:- merge([10,3,2],[11,5,2],[2,2,3,5,10,11]) . % SUCCEED %:- merge([0],[],[0]). % SUCCEED %:- merge([],[3],[3]). % SUCCEED

%:- merge([3,4],[3],[3]) -> fail ; true. % FAIL