The analysis of the expected running time of randomized Quicksort assumes that all element values are distinct. In this problem, we examine what happens when they are not, i.e., there exist same-valued elements in the array to be sorted. The Quicksort algorithm relies on the following partition algorithm, which finds a pivot randomly, and then put all the numbers less than or equal to the pivot in the left, and put all the numbers greater than the pivot in the right, and then return the pivot location, as well as the left and right sublists for recursive calls. In this algorithm, the list to be sorted is A, and we use p and r to denote the left-most and right-most indices of the currently processing subarray, respectively. For example, in the initial call of the Quicksort algorithm, we will let p = 0 and r = n−1, which correspond to the whole original array. The PARTITION(A, p, r) procedure returns an index q such that each element of A[p : q −1] is less than or equal to A[q] and each element of A[q + 1 : r] is greater than A[q]. (a) Suppose there are n elements and all element values are equal. What would be randomized Quicksort’s running time in this case? (b) Modify the Partition procedure to produce a procedure Partition′(A, p, r), which permutes the elements of A[p : r] and returns two indices q and t, where p ≤q ≤t ≤r, such that: i. all elements of A[q : t] are equal, ii. each element of A[p : q −1] is less than A[q], and iii. each element of A[t + 1 : r] is greater than A[q] Like Partition, your Partiton′procedure should take O(r −p) time. (c) Now you have a Partition′(A, p, r) algorithm, based on this algorithm, provide the pseudocode of a Quicksort′(A) algorithm which calls Partition′(A, p, r) as a subroutine, so that it recurses only on partitions of elements not known to be equal to each other. [Hint: it will looks very similar to our Quick-sort pseudocode in the lecture slides, you only need to make minor modifications to recurse on the partitions produced by Partition′(A, p, r).]
The analysis of the expected running time of randomized Quicksort assumes that all element values are distinct. In this problem, we examine what happens when they are not, i.e., there exist same-valued elements in the array to be sorted.
The Quicksort
In this algorithm, the list to be sorted is A, and we use p and r to denote the left-most and right-most indices of the currently processing subarray, respectively. For example, in the initial call of the Quicksort algorithm, we will let p = 0 and r = n−1, which correspond to the whole original array. The PARTITION(A, p, r) procedure returns an index q such that each element of A[p : q −1] is less than or equal to A[q] and each element of A[q + 1 : r] is greater than A[q].
(a) Suppose there are n elements and all element values are equal. What would be randomized Quicksort’s running time in this case?
(b) Modify the Partition procedure to produce a procedure Partition′(A, p, r), which permutes the elements of A[p : r] and returns two indices q and t, where p ≤q ≤t ≤r, such that:
i. all elements of A[q : t] are equal,
ii. each element of A[p : q −1] is less than A[q], and
iii. each element of A[t + 1 : r] is greater than A[q]
Like Partition, your Partiton′procedure should take O(r −p) time.
(c) Now you have a Partition′(A, p, r) algorithm, based on this algorithm, provide the pseudocode of a Quicksort′(A) algorithm which calls Partition′(A, p, r) as a subroutine, so that it recurses only on partitions of elements not known to be equal to each other. [Hint: it will looks very similar to our Quick-sort pseudocode in the lecture slides, you only need to make minor modifications to recurse on the partitions produced by Partition′(A, p, r).]
![### Algorithm 2: Partition \((A, p, r)\)
1. \( q = \text{RANDOM}(p, r); \)
- *Generate a random number in the range of \([p, r]\).*
2. \( L = \text{empty list}, R = \text{empty list}; \)
3. *For each element* \( a \) *in* \( A \) *except* \( A[q]: \)
4. \( \text{if } a \leq A[q]: \)
5. \(*append* \( a \) *to* \( L; \))
6. \( \text{else append } a \text{ to } R; \)
7. \( A = \text{append}(L, A[q], R); \)
8. \(\text{return } A, q;\)
**Explanation:**
This algorithm describes a partitioning process, commonly used in quicksort algorithms. Here's a breakdown:
- **Line 1:** A random index \( q \) is selected between the indices \( p \) and \( r \).
- **Line 2:** Two lists, \( L \) and \( R \), are initialized as empty. These lists are used to hold elements that are less than or equal to, and greater than the pivot element \( A[q] \), respectively.
- **Lines 3-6:** The algorithm iterates through each element \( a \) in the array \( A \), except for the pivot element \( A[q] \). If \( a \) is less than or equal to the pivot element \( A[q] \), it is added to list \( L \). Otherwise, it is added to list \( R \).
- **Lines 7-8:** The array \( A \) is reconstructed by appending each of the lists \( L \), the pivot element \( A[q] \), and \( R \) in order. Finally, the modified array \( A \) and the pivot index \( q \) are returned.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F8e7c73f8-c8bf-45ac-bc1a-a820f54adb9a%2F6ad50289-6c5b-48d8-82e2-b7a1fff49ffb%2Fyh1euf_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
