Lab 7: More practice with Sorting Algorithms
Task 1: Practice with sorting
In this task, we will practice some of the algorithms from our Sort class.
Consider the following array:
| 7 | 39 | 20 | 11 | 16 | 5 |
-
In case you missed last week’s lab, 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 2: 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?