Q.1 What is the average case time complexity of Quick Sort?
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - Quick Sort on average divides the array into balanced partitions, leading to O(n log n) time complexity.
Correct answer is: O(n log n)
Q.2 Which of the following is the worst-case time complexity of Quick Sort?
O(n^2)
O(n log n)
O(n)
O(log n)
Explanation - The worst-case occurs when the pivot always results in highly unbalanced partitions, leading to O(n^2).
Correct answer is: O(n^2)
Q.3 What is the best-case time complexity of Quick Sort?
O(n log n)
O(n^2)
O(n)
O(1)
Explanation - In the best case, partitions are evenly balanced each time, leading to O(n log n).
Correct answer is: O(n log n)
Q.4 Which sorting technique is used internally by Quick Sort?
Divide and conquer
Dynamic programming
Greedy method
Backtracking
Explanation - Quick Sort uses the divide and conquer paradigm by partitioning the array around a pivot.
Correct answer is: Divide and conquer
Q.5 What is the auxiliary space complexity of Quick Sort?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - Quick Sort requires O(log n) space on average due to recursive calls.
Correct answer is: O(log n)
Q.6 Which of the following is NOT true about Quick Sort?
It is an in-place algorithm
It is a comparison-based algorithm
It is a stable algorithm
It uses recursion
Explanation - Quick Sort is not stable as equal elements may not maintain their original order.
Correct answer is: It is a stable algorithm
Q.7 Who developed the Quick Sort algorithm?
Edsger Dijkstra
C.A.R. Hoare
Donald Knuth
Tony Hoare
Explanation - Quick Sort was developed by C.A.R. Hoare in 1959.
Correct answer is: C.A.R. Hoare
Q.8 Which element is typically chosen as the pivot in Quick Sort?
First element
Last element
Random element
Any of the above
Explanation - The pivot can be chosen in different ways, such as first, last, middle, or random element.
Correct answer is: Any of the above
Q.9 What happens if the pivot divides the array into two equal halves every time?
Best case
Worst case
Average case
Impossible case
Explanation - If the pivot perfectly balances partitions, Quick Sort runs in its best case O(n log n).
Correct answer is: Best case
Q.10 Which of the following sorting algorithms is similar to Quick Sort in terms of average complexity?
Bubble Sort
Merge Sort
Selection Sort
Insertion Sort
Explanation - Both Quick Sort and Merge Sort have O(n log n) average case time complexity.
Correct answer is: Merge Sort
Q.11 Which operation is key to Quick Sort’s performance?
Merging
Partitioning
Swapping
Heapifying
Explanation - Quick Sort relies heavily on efficient partitioning around a pivot element.
Correct answer is: Partitioning
Q.12 In practice, why is Quick Sort often faster than Merge Sort?
Lower time complexity
Better locality of reference
Uses less memory
It is stable
Explanation - Quick Sort performs better in practice due to cache efficiency and in-place partitioning.
Correct answer is: Better locality of reference
Q.13 How can the worst-case of Quick Sort be avoided?
Always choose the first element as pivot
Always choose the last element as pivot
Use randomized pivot selection
Avoid recursion
Explanation - Randomizing pivot selection reduces the chances of highly unbalanced partitions, avoiding O(n^2).
Correct answer is: Use randomized pivot selection
Q.14 What is the main drawback of Quick Sort?
Not in-place
High memory usage
Unstable and poor worst-case
Slow average performance
Explanation - Quick Sort is not stable and has a poor worst-case complexity of O(n^2).
Correct answer is: Unstable and poor worst-case
Q.15 Quick Sort is best suited for which type of data?
Small arrays
Linked lists
Large datasets in memory
External sorting
Explanation - Quick Sort is highly efficient for large arrays stored in memory due to in-place partitioning.
Correct answer is: Large datasets in memory
Q.16 What happens if all elements in the array are equal?
Quick Sort runs in O(n log n)
Quick Sort runs in O(n^2)
Quick Sort runs in O(n)
Quick Sort cannot run
Explanation - If all elements are equal, each partition will be unbalanced, leading to worst-case O(n^2).
Correct answer is: Quick Sort runs in O(n^2)
Q.17 Which algorithm is usually faster for smaller arrays?
Quick Sort
Merge Sort
Insertion Sort
Heap Sort
Explanation - For small arrays, insertion sort is faster due to lower overhead than recursive Quick Sort.
Correct answer is: Insertion Sort
Q.18 What is the role of recursion in Quick Sort?
To merge arrays
To repeatedly partition arrays
To choose pivots
To sort linked lists
Explanation - Recursion is used to apply Quick Sort to subarrays after partitioning.
Correct answer is: To repeatedly partition arrays
Q.19 Which of the following is true about Quick Sort?
It is stable
It is always faster than Merge Sort
It is in-place
It cannot be randomized
Explanation - Quick Sort is an in-place algorithm as it does not require additional significant memory.
Correct answer is: It is in-place
Q.20 What is the time complexity of Quick Sort when the array is already sorted and pivot is chosen as first element?
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - If the array is already sorted and first element is pivot, partitions are unbalanced, leading to O(n^2).
Correct answer is: O(n^2)
Q.21 What is the average case number of comparisons in Quick Sort?
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - On average, Quick Sort performs O(n log n) comparisons for partitioning.
Correct answer is: O(n log n)
Q.22 What does Quick Sort’s partition function do?
Divides array into sorted halves
Rearranges array around pivot
Merges sorted arrays
Counts inversions
Explanation - Partitioning arranges elements smaller than pivot to the left and greater elements to the right.
Correct answer is: Rearranges array around pivot
Q.23 Which variant of Quick Sort is commonly used in practice?
Three-way partitioning
Binary partitioning
Merge partitioning
Heap partitioning
Explanation - Three-way partitioning is used in practice to handle duplicate keys efficiently.
Correct answer is: Three-way partitioning
Q.24 Is Quick Sort adaptive?
Yes
No
Only in best case
Only for small arrays
Explanation - Quick Sort is not adaptive since it doesn’t take advantage of existing order in input.
Correct answer is: No
Q.25 Which of these is an application of Quick Sort?
Database indexing
Graph traversal
Shortest path algorithms
String matching
Explanation - Quick Sort is used in database indexing where efficient in-memory sorting is required.
Correct answer is: Database indexing