# MCQ IN COMPUTER SCIENCE & ENGINEERING

## COMPUTER SCIENCE AND ENGINEERING

### ALGORITHMS

 Question [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Quick sort running time depends on the selection of ____
 A Size of array B Pivot element C Sequence of values D None of the above
Explanation:

Detailed explanation-1: -The running time of Quicksort will depend on how balanced the partitions are. If you are unlucky and select the greatest or the smallest element as the pivot, then each partition will separate only one element at a time, so the running time will be similar to Insertion Sort .

Detailed explanation-2: -The running time of quicksort depends on whether the partitioning is balanced or unbalanced, and this in turn depends on which elements are used for partitioning. If the partitioning is balanced, the algorithm runs asymptotically as fast as merge sort.

Detailed explanation-3: -It depends on your requirements. Choosing a pivot at random makes it harder to create a data set that generates O(N^2) performance. ‘Median-of-three’ (first, last, middle) is also a way of avoiding problems.

Detailed explanation-4: -Choice of pivot element affects the efficiency of algorithm: If it is the median of the array then the array is divided into two halves every time and results in best or average case scenario with O(n logn )time complexity.

Detailed explanation-5: -You should choose the pivot randomly. Another way is to choose the median value from the first, the last, and the middle element of the array. Say we have 8 1 6 9 6 3 5 2 7 0 And 6 is chosen as the pivot.

There is 1 question to complete.