Question
* 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.
* 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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started