Lab 6: Sorting and algorithm analysis

• You are welcome and encouraged to work with a partner during labs, but please remember to be checked off individually.

Task 0: Review and Analyze Bubblesort

In lecture, you have begun to learn about some of the many algorithms that are available for sorting arrays of values.

We did an in class demonstration of how one of these sorting algorithms works. Now let’s take a closer look at Bubble sort. Recall that on eachpass, the algorithm proceeds from left to right, swapping adjacent elements if they are out of order. As a result, larger elements “bubble up” to the end of the array.

For example, consider the following array:

First pass Bubble sort compares elements 0 and 1 (the 28 and 24), and because they are out of order, it swaps them:

It then compares elements 1 and 2 (the 28 in its new position and 27), and because they are out of order, it swaps them:

Finally, it compares elements 2 and 3 (the 28 in its new position and 18), and because they are out of order, it swaps them:

Note that the largest element (the 28) has bubbled up to its final position, so we don’t need to consider it on the next pass.

Second pass Bubble sort compares the elements 0 and 1 (the 24 and 27), and because they are in order, it leaves them alone:

It then compares elements 1 and 2 (the 27 and 18), and because they are out of order, it swaps them:

And the second pass ends there.

Note that the second largest element (the 27) has bubbled up to its final position, so we don’t need to consider it on the next pass.

Third pass Bubble sort compares elements 0 and 1 (the 24 and 18), and because they are out of order, it swaps them:

And the third pass ends there.

Note that the third largest element (the 27) has bubbled up to its final position, so we don’t need to consider it on the next pass.

And because there is only one remaining element that hasn’t been bubbled up, the algorithm ends, and the array is sorted.

1. Trace bubble sort on the following array:

   7

   39

   20

   11

   16

   5

   Show what the array looks like after each swap that occurs.

2. Here is the implementation of bubble sort from our Sort class:

   public static void bubbleSort(int[] arr) {
       for (int i = arr.length - 1; i > 0; i--) {
           for (int j = 0; j < i; j++) {
               if (arr[j] > arr[j+1]) {   // how many comparisons?
                   swap(arr, j, j+1);
               }
           }
       }
   }
   

   Note that:

   • The inner loop performs a single pass.

   • The outer loop governs the number of passes, and the ending point of each pass.

   Let’s determine a formula for the number of comparisons of array elements that bubble sort performs when operating on an array of length n.

   To do so, it can help to begin by filling in a table like this one:

   pass #       # of comparisons
   ------       ----------------
      1              n - 1
   

   1. Fill in the next few rows of this table, and see if you notice a pattern.

   2. How can we take the pattern revealed by the table and use it to derive an exact formula for the number of comparisons?

   3. Given that formula, what is the big-O expression for the number of comparisons performed by bubble sort?

   4. The number of moves performed by bubble sort depends on the contents of the array. How many are performed as a function of n:

      • in the best case?
      • in the worst case?
      • in the average case?

   5. What is the big-O expression for the overall running time of bubble sort?

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. 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.

3. 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.