CP2003 - Assignment 3

Due 5pm, Friday 5 November 1999

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)

Write a procedure to divide a given list, L, into two lists, L1 and L2, of approximately equal length. For example:

?- divide([4, 88, 5, 45, 1], L1, L2).
L1 = [4,5,1],
L2 = [88,45]

[4 Marks] (b) Write a procedure to merge two sorted lists (with arbitrary lengths) producing a third list. For example:

?- merge([2,4,77,80,95], [21,77,77], L).
L = [2,4,21,77,77,77,80,95]

[4 Marks] (c) Implement the merge_sort program using procedures divide and merge (data items are integer values). For example:

?- merge_sort([2,5,2,0,6,99,43,22], L).
L = [0,2,2,5,6,22,43,99]

[4 Marks]

Submit:

You need to submit three files divide, merge and merge_sort.

Submit paper copies into the CP2003 post-box located in TG128 (Tea Room -- Department of Computer Science). The room is open weekdays 8am to 5pm. You must also email copies of the files to hossein@cs.jcu.edu.au