Home / Expert Answers / Computer Science / prolog-programming-project-on-sorting-in-this-project-you-will-implement-3-different-prolog-predic-pa789

(Solved): Prolog Programming Project on Sorting In this project, you will implement 3 different Prolog predic ...




Prolog Programming Project on Sorting
In this project, you will implement 3 different Prolog predicates that take as input a
split/3
split( \( X, X L, X R) \) : split original list into two equal length sublists \( X L \) and \( X R \). Calculate the
merge/3
merge \( (X L, X R, X) \) : merge two sorted lists \( X L \) and \( X R \) into one larger sorted list \( X \)
Compar
Also note the base cases. When merging a list with the empty list then the result is the other list.
merge \( [x, I, X] \). m
Dont confuse merge and mergesort. Merge merely merges two sorted lists, while mergesort performs a complete sort that uses s
Prolog Programming Project on Sorting In this project, you will implement 3 different Prolog predicates that take as input a list of random numbers, and as output produce a list of the same numbers in sorted (non-descending) order. Prolog is not a language optimized for this type of problem, but sorting is a good problem domain to use for writing Prolog code for practice. Each sorting predicate comes with a series of helper functions to help with testing and to divide the tasks into smaller parts. 1. badsort/2 This sort takes a list of numbers, generates permutations of the list, then succeeds when it finds a permutation whose values are in order. It doesn't actually do any sorting but merely recognizes when a sequence of values is already sorted. Not a good sorting algorithm, but reveals some important properties about Prolog backtracking. 2. selsort/2 This sort implements selection sort. Steps are performed for the original list for indexes 0 through length-2. For each step, the location of the smallest remaining element in the list is located, and it is then swapped into the current step index. \( O\left(n^{2}\right) \) because we check \( O(n) \) positions and for each position we check \( O(n) \) for the minimum. 3. mergesort/2 This sort recursively splits the list into smaller and smaller lists until it reaches lists of size 1 . Then pairs of lists are merged into a combined list that is sorted. Once the recursion returns to the original split list, the splits are recursively sorted then merged, giving the result list as a sorted version of the original. \( O \) (nlogn) because the splits form a tree of sublists, number of sublists is \( O(\log \mathrm{n}) \), while merging all the lists is \( \mathrm{O}(\mathrm{n}) \). Implementation Divide predicates into the three exercises as indicated below. Don't move to the next exercise until the current exercise is completed and tested. split/3 split( \( X, X L, X R) \) : split original list into two equal length sublists \( X L \) and \( X R \). Calculate the length of \( X / / 2 \), use append/3, to split the list with \( 1^{1 H} \) and \( 2^{\text {nd }} \) arguments as outputs, \( 3^{\text {rt }} \) argument as input, plus use length/2 as extra constraint. If the length of the original is an odd number, the length of the two split lists will differ by one, which is not a problem. Use "//" for "integer divide". E) Using the idea in the last example, define split/3 in terms of append/3. Example Usage: ?- split( \( [1,2,3,4,5], A, 8) \). \( A=[1,2] \), \( B=[3,4,5] \). merge/3 merge \( (X L, X R, X) \) : merge two sorted lists \( X L \) and \( X R \) into one larger sorted list \( X \) Compare the first element in each input list. If the element from XL is smaller, call merge recursively on remainder of \( \mathrm{XL} \), and original \( \mathrm{XR} \) unchanged, to get a new list. Append head of \( \mathrm{XL} \) as a list to the merged list to get the result list \( X \). If the element from \( X R \) is smaller, modify the instructions appropriately. Look at the following traces (these are not definitions, just illustrations of the trace): The two cases will require either two clauses, or one clause using the if-else predicate. For example, suppose you want to define your own predicate my_abs/2 to compute absolute value. There is already a built-in abs/1, but suppose you write your own. 7. my_abs(-5,x). \( x=5 \). ?.-my_abs(5,x). \( x=5 \). One way to write it is to provide two separate rules for two cases on the value of the input. Because of backtracking. Prolog will pick one of the rules to satisfy a query. If the rule fails, Prolog will automatically try the other. Another way is to use the Prolog if-else command \( (->;) \). This one is not hard but you must get the syntax right. If we use if-else we can rewrite the predicate with one rule that contains if-else for the two different cases. You will need if-else logic for writing merge/3, so use one or the other of these ideas. Also note the base cases. When merging a list with the empty list then the result is the other list. merge \( [x, I, X] \). merge \( ([1, X, X) \). To test merge/3, use randlist/3 and sort/2 built-in and add the following test predicate to your file: te You cannot use the sort/2 built in when writing your sort predicates, but it's okay to use it as part of your testing. When testing, remember that the input lists must already be sorted, it doesn't merge unsorted lists. mergesort mergesort \( (X, Y) \) : take initial list \( X \) and produce sorted result list \( Y \). Split original list \( X \) into two halves, recursively mergesort the two halves, then merge the sorted halves together to form result list \( Y \). Note that mergesort calls split then calls itself recursively. This recursive process will break down the lists and sublists into smaller and smaller pieces. Add a base case so that mergesort stops recursion if length of \( \mathrm{X} \) is 1 . mergesortl\( [x, X):- \) length \( (X, 1) \). mergesort(X,Y) :- length \( (x, X \) len \( ) \), Xlen \( >1 \), Don't confuse merge and mergesort. Merge merely merges two sorted lists, while mergesort performs a complete sort that uses split, merge, and mergesort recursively. Use the following predicate to test mergesort mergesorttest(N,R) :- writeln("mergesort test"), randist( \( N, R, X) \), mergesort(X,Y), writeln \( (X) \), writeln(Y). \% generate random value list, \( X \) is output \( X \) sort it, \( X \) is input, \( Y \) is output \( X \) print out original and sorted result


We have an Answer from Expert

View Expert Answer

Expert Answer


(self, new_capacity: int) -> None: """ TODO: Write this implement
We have an Answer from Expert

Buy This Answer $5

Place Order

We Provide Services Across The Globe