Lab 7: All about Sorting Analysis
In this lab, we will practice some of the sorting algorithms from our Sort class.
Task 1: 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.
Now let’s take a closer look at Bubble sort. Recall that on each pass, 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:
| 28 | 24 | 27 | 18 |
First pass Bubble sort compares elements 0 and 1 (the 28 and 24), and because they are out of order, it swaps them:
| 24 | 28 | 27 | 18 |
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:
| 24 | 27 | 28 | 18 |
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:
| 24 | 27 | 18 | 28 |
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:
| 24 | 27 | 18 | 28 |
It then compares elements 1 and 2 (the 27 and 18), and because they are out of order, it swaps them:
| 24 | 18 | 27 | 28 |
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:
| 18 | 24 | 27 | 28 |
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.
-
Trace bubble sort on the following array:
7 39 20 11 16 5 Show what the array looks like after each swap that occurs.
-
Here is the implementation of bubble sort from our
Sortclass: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.
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
-
Fill in the next few rows of this table, and see if you notice a pattern.
-
How can we take the pattern revealed by the table and use it to derive an exact formula for the number of comparisons?
-
Given that formula, what is the big-O expression for the number of comparisons performed by bubble sort?
-
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?
-
What is the big-O expression for the overall running time of bubble sort?
-
What changes to the algorithm would be required to optimize it such that the algorithm can run
O(n)in the best case?
-
Task 2: More practice with sorting
Consider the following array:
| 7 | 39 | 20 | 11 | 16 | 5 |
-
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). -
Recall that quicksort begins by partitioning the array with respect to a pivot value. Trace through the initial partitioning of the array shown above.
-
Now complete the trace of quicksort on this array by filling in the diagram below.
Task 3: Practice merge sort
Like quicksort, merge sort uses a recursive, divide-and-conquer approach. However, whereas quicksort does all of its work during the divide stage (before making the recursive calls), merge sort instead does all of its work after a given set of recursive calls have returned, as it merges sorted subarrays.
-
Trace through mergesort on the following array:
----------------------------------------- | 7 | 39 | 20 | 11 | 16 | 5 | 9 | 28 | ----------------------------------------- split / \ --------------------- --------------------- | | | | | | | | | | --------------------- --------------------- split split / \ / \ ----------- ----------- ----------- ----------- | | | | | | | | | | | | ----------- ----------- ----------- ----------- split split split split / \ / \ / \ / \ ------ ------ ------ ------ ------ ------ ------ ------ | | | | | | | | | | | | | | | | ------ ------ ------ ------ ------ ------ ------ ------ \ / \ / \ / \ / merge merge merge merge ----------- ----------- ----------- ----------- | | | | | | | | | | | | ----------- ----------- ----------- ----------- \ / \ / merge merge --------------------- --------------------- | | | | | | | | | | --------------------- --------------------- \ / ----------------------------------------- | | | | | | | | | ----------------------------------------- -
What major advantage does merge sort have over quicksort with respect to time complexity?
-
What major disadvantage does merge sort have compared to quicksort with respect to space complexity?