Problem 1
The input is a sequence of integers and the problem is to sort this sequence using linked lists.
I want you to use two methods to do this and then compare the two methods using their running time
as a measure.
What do you turn in? Printouts of code for Sort1 and Sort2.
Problem 2
Modify Sort1 and Sort2 so that, rather than read from the keyboard, they pick up
elements one at a time from an apvector in which they are already stored.
So you can assume that the function header for Sort1 and Sort2 are:
node * Sort1(const apvectorThis modifcation will help in the following experiment.& numbers); node * Sort2(const apvector & numbers);
Create an apvector with n randomly generated integers in the range 1 through n. Use the RandGen class to generate the random integers. Call each of the functions Sort1 and Sort2 and time their execution. For a particular value of n, repeat this experiment 10 times (generating afresh the random sequence of integers) and compute the average running time of Sort1 and Sort2 for sorting a sequence of length n. Perform this experiment for n = 1000, 2000, 3000, ..., 10,000. Plot the running times of Sort1 and Sort2 in the same graph and comment on the following:
What do you turn in? The plot showing the running times along with your answers to the above questions.
Problem 3
Start with the functions Sort1 and Sort2 you created for
Problem 2.
Here is another timing experiment comparing the running times of
Sort1 and Sort2.
This differs from the experiment in Problem 2 in how the random
sequence of n elements is generated.
The goal here is to generate a sequence of n elements that is "almost sorted"
in the sense that each element is not too far from its position in a sorted
list.
To do this start with an apvector of n integers and initialize this
to 1, 2, 3, ..., n.
Let block 1 be the first contiguous block of 10 elements in the
apvector,
block 2 be the second contiguous block of 10 elements in the
apvector,
block 3 be the third contiguous block of 10 elements in the
apvector, and so on.
So we have n/10 blocks of elements.
Randomly permute the elements within each block.
The resulting sequence satisfies the property that no element is more than
a "distance" 10 away from its position in a sorted list.
Using this input sequence, perform the experiment you performed in
Problem 2.
The only difference between this experiment and the experiment in
Problem 2 is the way the input sequence is generated.
What do you turn in? The plot showing the running times along with your answers to the above questions.
Problem 4
For the graph given below, show: