Quick-Sort
Question 1 |
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.
T(n) = 2T(n/2) + cn
| |
T(n) = T(n – 1) + T(1) + cn | |
T(n) = 2T(n – 1) + cn
| |
T(n) = T(n/2) + cn
|
Question 1 Explanation:
When the pivot is the smallest (or largest) element at partitioning on a block of size n the result yields one empty sub-block, one element (pivot) in the correct place and sub block of size n-1.
Hence recurrence relation T(n) = T(n - 1) + T(1) + cn.
Hence recurrence relation T(n) = T(n - 1) + T(1) + cn.
Question 2 |
Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
t1=5 | |
t1 | |
t1>t2 | |
t1=t2 |
Question 2 Explanation:
[1, 2, 3, 4, 5] [4, 1, 5, 3, 2]
Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2nd array through not in sorted manner.
Hence t1> t2.
Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2nd array through not in sorted manner.
Hence t1> t2.
Question 3 |
Which of the following algorithm design techniques is used in the quicksort algorithm?
Dynamic programming | |
Backtracking | |
Divide and conquer | |
Greedy method |
Question 3 Explanation:
In quick sort, we use divide and conquer technique.
Question 4 |
Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…..n] are to be sorted, give an input for which Quicksort takes maximum time.
O(n^2) |
Question 4 Explanation:
For n distinct elements the algorithm will take maximum time when:
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
There are 4 questions to complete.