This assignment counts 12 per cent of the total assessment for CP2003.
Aim
To learn about Prolog
Background
The essential idea behind merge sort is to make repeated use of a function that merges two lists, each already in ascending order, to produce a result list that is also arranged in ascending order. Its logic is similar to the method you would use if you were merging two sorted piles of index cards to form a single sorted pile. That is, start with the first card from each pile. Compare them to see which one comes first, transfer that one over to the result pile, and advance to the next card in that pile. repeat the comparison, transfer, and advance operations until one of the piles runs out of cards. At that point, merely move what is left of the remaining pile over to the result pile.
The merge sort algorithm sorts a sequence of length $n > 1$ by splitting it into two subsequences, one of length $n/2$, the other of length $(n+1)/2$. Each subsequence is sorted and then the two sorted sequences are merged into one. However, these halves have to be sorted first which is accomplished by merging the already sorted halves of these halves. This process of dividing arrays into two halves stops when the array has fewer than two elements.
Your task:
(a)
?- divide([4, 88, 5, 45, 1], L1, L2). L1 = [4,5,1], L2 = [88,45][4 Marks]
?- merge([2,4,77,80,95], [21,77,77], L). L = [2,4,21,77,77,77,80,95][4 Marks]
?- merge_sort([2,5,2,0,6,99,43,22], L). L = [0,2,2,5,6,22,43,99][4 Marks]
Answer
divide
%
% --------------------------------------
% Implementation of the divie procedure
% --------------------------------------
%
divide([], [], []). % Divide an empty list
divide([X], [X], []). % Divide a single element list
%
% Otherwise, if the list contains more than one element,
% then put the first two elements int two different lists.
%
divide([X,Y | Z], [X | Z1], [Y | Z2]):-
divide(Z, Z1, Z2).
%
merge
%
% --------------------------------------
% Implementation of the merge procedure
% --------------------------------------
%
merge(List, [], List). % Merge of a list and an empty list
merge([], List, List). % gives the list.
%
% Merge of two non-empty lists gives a list such that the head of the
% obtained list is the smallest value of the heads in those lists.
merge([X | TX], [Y | TY], [X | Tail]):-
X =< Y,
merge(TX, [Y | TY], Tail).
merge([X | TX], [Y | TY], [Y | Tail]):-
X > Y,
merge([X | TX], TY, Tail).
The mege-sort program
%
% MergeSort
%
merge_sort([], []). % Do nothing (empty list)
merge_sort([X], [X]). % Do nothing (single element)
merge_sort(L, SL):- % Otherwise;
divide(L, L1, L2), % split L into two lists, L1 and L2,
merge_sort(L1, SL1), % sort L1 giving SL1,
merge_sort(L2, SL2), % sort L2 giving SL2,
merge(SL1, SL2, SL). % merge SL1 and SL2 giving SL
%
% --------------------------------------
% Implementation of the divie procedure
% --------------------------------------
%
divide([], [], []). % Divide an empty list
divide([X], [X], []). % Divide a single element list
%
% Otherwise, if the list contains more than one element,
% then put the first two elements int two different lists.
%
divide([X,Y | Z], [X | Z1], [Y | Z2]):-
divide(Z, Z1, Z2).
%
% --------------------------------------
% Implementation of the merge procedure
% --------------------------------------
%
merge(List, [], List). % Merge of a list and an empty list
merge([], List, List). % gives the list.
%
% Merge of two non-empty lists gives a list such that the head of the
% obtained list is the smallest value of the heads in those lists.
merge([X | TX], [Y | TY], [X | Tail]):-
X =< Y,
merge(TX, [Y | TY], Tail).
merge([X | TX], [Y | TY], [Y | Tail]):-
X > Y,
merge([X | TX], TY, Tail).