Question

C2

4. List four popular ways for selecting pivot. Is any of these definitely better

than the others to generate balanced partitioning?

5. When the array is almost or already sorted, which way for selecting pivot is the best

and which way is the worst?

6. Describe a worst-case scenario in which the quicksort with specific way for selecting

pivot leads to a quadratic sorting algorithm, i.e, the running time is O(n²).

7. What is the advantage of using a random element as pivot?

Answer 1

Answer - 4

Some of the most common/ popular ways of selecting pivot are as follows -

1. Selecting the first/last element as pivot. This is the one of the most popular ways and in most of the cases, it works well.

2. Selecting middle element is also fine and is used in some cases.

3. Selecting random elements as pivot. This minimises the probability of the time complexity becoming O(n²).

4. This method is also used sometimes. In this way we select the median of data/ array as pivot while applying quick sort.

Answer - 5

When array is sorted or almost sorted, then you should certainly avoid choosing first element or the last element as the pivot, as this will lead to O(n²) time complexity. This can certainly be avoided by choosing random element, middle element or median element as pivot, as these might reduce the complexity for O(n²) but cannot eliminate it completely.

Answer - 6

Suppose you array is almost sorted or sorted, and you are choosing the first element or the last element as pivot element. Now, every time you would be partitioning, then you would be left with two subarray, one of size 1 and other of size n-1 where n is the number of elements. This will result in time complexity being -

(n-1) + (n-2) + .... + 1 = n*(n-1)/2 = O(n²) Time complexity.

Hence, this is one of the worst cases of quick sort.

Answer - 7

If we choose/select a random element of the array in quick sort, then the probability that the time complexity might become O(n²) is reduced drastically. It becomes favourable for us because we want to avoid the time complexity of O(n²) while applying quick sort.