Lab 5: More sorting and algorithm analysis

Task 1: Practice algorithm analysis

Your work for this lab should go on the piece of paper that we give you. Please show your paper to a staff member before you leave the lab.

Consider the following code fragment:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2*n; j++) {
        methodA();

        for (int k = 0; k < n + 1; k++) {
            methodB();
        }
    }

    for (int j = 0; j < i; j++) {
        methodC();
    }

    if (i % 2 == 0) {
        methodD();
    }
}

For each of the following, find the function that expresses the number of times each part of the code is executed for a given value of n, and then determine the corresponding big-O expression.

1. the number of times methodA() is called
2. the number of times methodB() is called
3. the number of times methodC() is called
4. the number of times methodD() is called

Task 2: Deriving big-O expressions from experimental data

In Problem Set 4, you are asked to take some experimental data regarding the execution of an algorithm, and to infer the big-O time complexity from the experimental data. Here is an example of this process.

The main method for the SortCount class that we’ve given you runs the various sort algorithms on either a random, almost-sorted, or fully-sorted array, and it prints the number of comparisons and moves performed by each algorithm.

Below are some sample results from SortCount for one of the sorting algorithms. For each of three array sizes (100, 200, and 300), we:

• performed three runs, each of which started with a different random array of that size
• recorded the number of comparisons and number of moves performed by the algorithm in question during each run

1. What do you notice about the number of comparisons and number of moves performed for random arrays of a given size?

2. What happens when n doubles from 100 to 200?

3. What happens when n quadruples from 200 to 800?

4. Based on these experimental results, what are the suggested big-O expressions for the number of comparisons and the number of moves performed by this algorithm?

5. Given these observations, what sorting algorithm do we think this is?

6. Does it make sense that the number of comparisons and moves is the same regardless of the initial values in the array?

It is worth noting that this is not the case for all of our sorting algorithms. For example, here is some sample output from SortCount showing comparisons while running insertion sort:

The average number of comparisons is 2,721 for an input size of 100, and 10,384 for an input size of 200.

7. In this case, the number of comparisons varies as we try different arrays of the same size. Why does this make sense?

8. What happens to the average number of comparisons as n doubles from 100 to 200? Does this agree with what we know about insertion sort?

Task 3: Practice with sorting

In this task, we will practice some of the algorithms from our Sort class.

Consider the following array:

1. Trace insertion sort on the above array.
   Show what the array looks like after each iteration of the outer loop of the algorithm (i.e., after each element is considered for insertion and either left alone or inserted).

2. Trace Shell sort on the above array.

   1. Begin with the initial phase of the algorithm, in which an increment of 3 would be used to divide up the array into subarrays. Show what the array looks like after each element is considered for insertion and either left alone or inserted.

   2. Next trace the second and final phase, in which an increment of 1 is used.

3. Recall that quicksort begins by partitioning the array with respect to a pivot value. Let’s first trace through the initial partitioning of the array shown above.

4. Now let’s complete the trace of quicksort on this array by filling in the diagram below.

   

Task 4: Show us your work

You should show the paper with your work to the teaching assistant.

Don’t worry if you didn’t finish all of the tasks. You should just show us whatever work you were able to complete during lab.