Please help with exercise 6.9 Exercise 6.9. In randomized QuickSort (Algorithm 1
ID: 3729573 • Letter: P
Question
Please help with exercise 6.9
Exercise 6.9. In randomized QuickSort (Algorithm 13), given an elementx in the input array: 1. What is the maximum number of comparisons thatx is involved (i.e., the number of times is compared with other elements) during the 2. What is the minimum number of comparisons that a is involved 3. What is the average number of comparisons thatx is involved during course of the algorithm? during the course of the algorithm? the course of the algorithm? Justify your answers.Explanation / Answer
In randomized QuickSort.
if the input array size is 'n'.
1. Maximum number of comparisons that 'x' is involved:-
O(n-1) or O(n) time.
example:
if 'x' is a pivot element.
arr[] = {15, 85, 30, 150, 40, 50, 75}
Indexes: 0 1 2 3 4 5 6
here x=75,n=7;
low = 0, high = 6, pivot = arr[h] = 75
Initialize index of smaller element, i = -1
Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0
arr[] = {15, 85, 30, 150, 40, 50, 75} // No change as i and j
// are same
j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]
j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {15, 30, 85, 150, 40, 50, 75} // We swap 85 and 30
j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]
j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {15, 30, 40, 150, 85, 50, 75} // 85 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i = 3
arr[] = {15, 30, 40, 50, 85, 150, 75} // 150 and 50 Swapped
arr[i+1] and arr[high] (or pivot)
arr[] = {15, 30, 40, 50, 75, 150, 85} // 85 and 75 Swapped
here we have seen that 75 was compared with 6 other elements of array(that is n).
2. Minimum number of comparisons that 'x' is involved:-
O(log n) time.
let array is:
arr[] = {15, 30, 40, 50, 75, 85, 150}
Indexes: 0 1 2 3 4 5 6
here x=15,n=7;
and 50 is a pivot element.
here we have seen that 15 was compared with 3(30,40,50) other elements of array(that is n).
3. Average number of comparisons that 'x' is involved:-
It takes O(n) time complexity.