| Quicksort |
About This Exercise
The objective of this exercise is to ensure that you understand the QuickSort algorithm well enough to be able to describe this algorithm, trace its execution by hand on small examples, and accurately describe its worst-case and expected performance.
Students should read through and try to solve the problems on this exercise before attending the tutorial.
Expected Background
This is based on the lecture on QuickSort. Additional information about this sorting algorithm is available on the Wikipedia page on this topic.
Warmup Problems — To Check That You Understand the Basics
It is expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, and attended the lecture in which QuickSort was discussed (reviewing the onine notes, as needed).
These warmup problems will not be discussed in the tutorial; students who do have difficulty with them should contact the course instructor to get extra help.
-
Briefly describe what each of the following algorithms are supposed to do, as well as how they do it.
- Deterministic Partitioning — DPartition
- Deterministic Quicksort — Quicksort
- Randomized Partitioning — RPartition
- Randomized Quicksort — RQuicksort
-
Consider the following array.
-
Trace the execution of the “Deterministic Partitioning” algorithm on this input. That is, trace the execution of the program after the call
DPartition(A, 0, 7)
if A is the array that is shown above.
-
Notice that this is the first stage of the application of the deterministic Quicksort algorithm to sort the above array.
Trace the rest of the application of this algorithm to sort this array. In order to answer this question you should list each of the following.
- the calls that are made to DPartition after this
- the array before each of these calls is made
- the array after each of these calls is completed
-
-
Repeat the above question, using the following array instead of the one that is shown above.
What is notable (and unfortunate) about the lengths of arrays that must be recursively sorted as this algorithm proceeds?
-
Repeat the first question, using the following array instead of the ones that are shown above.
What is notable about the lengths of arrays that must be recursively sorted this time?
What would happen if the randomized version of Quicksort was applied to this array? Why?
To Be Discussed in the Tutorial
-
If you completed the above questions then you may have noticed the following: Neither the deterministic nor the randomized algorithms that have been described in class and in the textbook work particularly well on arrays that include many copies of the same input entry.
-
Modify the DPartition algorithm so that it reorders the input algorithm in much the same way as before. However, the algorithm should now move all copies of the pivot element x into the middle of the part of the array that is being processed, and it should return a pair of integers i and j, on inputs A, p, and r, such that the following properties are satisfied.
-
p ≤ i < j ≤ r+1.
-
For an integer h, if p ≤ h < i then A[h] < x.
-
For an integer h, if i ≤ h < j then A[h] = x.
-
For an integer h, if j ≤ h ≤ r then A[h] > x.
Then modify the proof of correctness and efficiency of the DPartition algorithm to show that your new algorithm is correct and efficient as well.
-
-
Describe a modified version of the deterministic Quicksort algorithm that uses your new partitioning algorithm, and that has better performance when the input array includes many copies of the same algorithm.
-
Make similar modifications to the randomized algorithm. Explain why the resulting algorithm can be expected to perform well on all input arrays.
-
|
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial18.html |