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

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter17: Linked Lists

Section: Chapter Questions

Problem 16PE

See similar textbooks

Related questions

Concept explainers

Question

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

Algorithm 2: Partition(A, p, r)
1 q=RANDOM(p,r); //generate a random number in the range of [p,r]
2 L=empty list, R=empty list;
3 for each element a in A except A[q]:
if a<A[q]:
5
append a to L;
6
else append a to R;
7 A=append(L,A[q],R);
8 returen A, q;

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Fundamentals of Multithreaded Algorithms

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.