CLRS BOOK Introduction to ALgorithms Problem 7-2 Quicksort with equal element va
ID: 3591617 • Letter: C
Question
CLRS BOOK Introduction to ALgorithms Problem 7-2 Quicksort with equal element values
The analysis of the expected running time of randomized quicksort in Section 7.4.2
assumes that all element values are distinct. In this problem, we examine what
happens when they are not.
a. Suppose that all element values are equal. What would be randomized quicksort’s running time in this case?
b. The PARTITION 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]. 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
all elements of A [q . . t] are equal,
each element of A [p . . q - 1] is less than A [q], and
each element of A [t + 1 . . r ] is greater than A[q].
Like PARTITION, your PARTITION' procedure should take theta(r - p) time.
c. Modify the RANDOMIZED-QUICKSORT procedure to call PARTITION', and
name the new procedure RANDOMIZED-QUICKSORT0. Then modify the
QUICKSORT procedure to produce a procedure QUICKSORT'(A p r) that calls
RANDOMIZED-PARTITION' and recurses only on partitions of elements not
known to be equal to each other.
d. Using QUICKSORT', how would you adjust the analysis in Section 7.4.2 to
avoid the assumption that all elements are distinct?
Explanation / Answer
void partition(int a[], int l, int r, int &i, int &j) //a is array of elements,l is starting length, r is ending length, i and j are references to divide into sub problems greater than and less than pivot
{
i = l-1, j = r;
int p = l-1, q = r;
int v = a[r]; //last element be the pivot
while (true) //until condition fails
{
// From left, find the first element greater than
// or equal to v. This loop will definitely terminate
// as v is last element
while (a[++i] < v);
// From right, find the first element smaller than or
// equal to v
while (v < a[--j])
if (j == l)
break;
// If i and j cross, then we are done
if (i >= j) break;
// Swap, so that smaller goes on left greater goes on right
swap(a[i], a[j]);
// Move all same left occurrence of pivot to beginning of
// array and keep count using p
if (a[i] == v)
{
p++;
swap(a[p], a[i]);
}
// Move all same right occurrence of pivot to end of array
// and keep count using q
if (a[j] == v)
{
q--;
swap(a[j], a[q]);
}
}
// Move pivot element to its correct index
swap(a[i], a[r]);
// Move all left same occurrences from beginning
// to adjacent to arr[i]
j = i-1;
for (int k = l; k < p; k++, j--)
swap(a[k], a[j]);
// Move all right same occurrences from end
// to adjacent to arr[i]
i = i+1;
for (int k = r-1; k > q; k--, i++)
swap(a[i], a[k]);
}