MCQ on QuickSort: Quicksort Multiple Choice Questions and Answers (MCQs)

Let P be a QuickSort Program to sort numbers in ascending order using the first element as 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?

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

Which one of the following in place sorting algorithms needs the minimum number of swaps?

Which sorting algorithms is most efficient to sort string consisting of ASCII characters?

Given an array where numbers are in range from 1 to n6, which sorting algorithm can be used to sort these number in linear time?

A machine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately

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.

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort? (A) \theta(n) (B) \theta(nLogn) (C) \theta(n^2) (D) \theta(n^2 log n)

Which of the following sorting algorithms has the minimum running time complexity in the best and average case?

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

Which of the following is true about merge sort?

Which is the correct order of the following algorithms with respect to their time Complexity in the best case ?

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

RECURSIVE ALGORITHM		RECURRENCE RELATION
P.	Binary search	I.	T(n) = T(n-k) + T(k) + cn
Q.	Merge sort	II.	T(n) = 2T(n-1) + 1
R.	Quick sort	III.	T(n) = 2T(n/2) + cn
S.	Tower of Hanoi	IV.	T(n) = T(n/2) + 1

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

Which of the following is not a stable sorting algorithm in its typical implementation.

Which of the following changes to typical QuickSort improves its performance on average and are generally done in practice.

1) Randomly picking up to make worst case less 
   likely to occur.
2) Calling insertion sort for small sized arrays 
   to reduce recursive calls.
3) QuickSort is tail recursive, so tail call 
   optimizations can be done.
4) A linear time median searching algorithm is used 
   to pick the median, so that the worst case time 
   reduces to O(nLogn)

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot,

(i) 1, 2, 3,......., n
(ii) n, n-1, n-2,......, 2, 1 

Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2  5  1  7  9  12  11  10 

Which statement is correct?

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

What is the best sorting algorithm to use for the elements in array are more than 1 million in general?

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort? <pre> (A) theta(n) (B) theta(nLogn) (C) theta(n^2) (D) theta(n^2 log n) </pre>

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

Quick sort is run on 2 inputs shown below to sort in ascending order

A. 1, 2, 3……n
B. n, n – 1, n – 2 …… 1

Let C1 and C2 be the number of comparisons made for A and B respectively. Then