# Java data structures and alg.

1. QUESTION 1a

Write a recursive "Merge" method meeting this specification:

Inputs: a sorted list L1 and a sorted list L2.

Outputs: a sorted list that is the merging of L1 and L2, and, the number of

times two list elements were compared during the merging process (call it C).

The recursive Merge method returns the merging of L1 and L2 as its result. Thus, after

executing L1 = Merge(L1,L2,Nc,Njs), L1 contains the result of the merge and the 'other'

list has been destroyed. In other words, at this point, (1) either L2 has been destroyed,

or (2) the old L1 has been destroyed and now L1==L2.

(Note: Nc is the total number of times two list elements were compared during the merging

process. Njs is the total number of join and split operations that were performed during the

merging process. Nc and Njs are output values but not input values. 2005-11-16 12:45:32)

2. QUESTION 1b

Write a method "General_Sort" that meets this specification:

Inputs: a list L, and a method "Cut_In_Two" that meets the specification below

Outputs: L is sorted in increasing order, and the integer C defined as follows:

C is the total number of times two list elements were compared during the

sorting process, including the comparisons made by the Merge and Cut_In_Two

methods.

General_Sort must use the "general sorting strategy" (described in detail in class):

1. Use the procedure Cut_In_Two to divide L into two pieces

2. Recursively sort the two pieces

3. Merge the results (use the function written in Question 1a).

The function Cut_In_Two meets this specification:

Input: a list L1 containing at least two elements.

Outputs: non-empty lists L2 and L3 such that L1 = L2+L3 (concatenation), and the

integer C (the number of times two list elements were compared during the

cut_in_two process)

The method Cut_In_Two should "RANDOMLY" cut the list L1 in two pieces. Thus L1

can be split at "ANY" position (between 1 and lenght(L1)-1), not necessarily in the

middle position.

3. QUESTION 1c

Write a method Merge_Sort that implements the "merge sort algorithm" simply by calling

GeneralSort with an appropriate Cut_In_Two method (which you must also write).

Merge_Sort should return the sorted list and the integer C returned by

GeneralSort.

4. QUESTION 1d

Write a method Insertion_Sort that implements the "insertion sort algorithm" simply by

calling GeneralSort with an appropriate Cut_In_Two method (which you must also write).

Insertion_Sort should return the sorted list and the integer C returned by

GeneralSort.

5. QUESTION 2

Choose five different lengths of lists ranging from small (e.g. 10) to large (as large as

you can and still finish executing in a few minutes), with reasonably-spaced intermediate

values. For instance: 10, 100, 1000, 10000, 100000. The lists must be randomly generated.

For each of these list lengths, run the program written for question 1 five times using a

different random number seed each time. Average the results.

Plot the average number of comparisons (C) for the two sorting algorithms (merge sort and

insertion sort) as a function of the length of the list.

Which algorithm is better for sorting short lists?

Which will be better for sorting extremely long lists?

Justify your answers.

6. QUESTION 3

How would you modify the methods above in order to implements the "quick sort algorithm"

by simply calling General_Sort?

https://brainmass.com/computer-science/sorting/java-data-structures-alg-56773

#### Solution Summary

Java data structures and algebra are determined. Recursive "merge" methods meeting the specifications are determined.