Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have presented Interview Questions on Quick Sort (MCQ) with detailed answers. You must practice this as Quick Sort is the most important topic for Coding Interviews.
If you want to revise Quick Sort once quickly, go through this article. Let us answer Interview Questions on Quick Sort.
Q1. What is the Worst Case Time Complexity of Quick Sort?
O(N^2)
O(N)
O(N logN)
O(N loglogN)
The worst case Time Complexity of Quick Sort is O(N2) and this happens when the partition algorithm selects an element which is always at the extreme of the sorted array. This holds true for the traditional implementation of Quick Sort.
Q2. Is Quick Sort a Stable Sorting algorithm?
No
Yes
Depends on partition
Depends on worst case
Quick Sort is not a stable sorting algorithm that is the relative order of same elements is not preserved in the sorted output.
Q3. In which year was Quick Sort published for the first time?
1961
1978
1959
1974
Quick Sort was published in 1961 by Sir Charles Antony Richard Hoare (popularly known as Tony Hoare) who invented it in 1959. It was published in an article titled "Algorithm 64: Quicksort" in Communications of the ACM (Volume 4, Issue 7).
Q4. What is the Time Complexity of the Partition Algorithm in Quick Sort?
O(N)
O(logN)
O(N logN)
O(loglogN)
Time Complexity of the Partition Algorithm in Quick Sort is O(N). It is same for all partition algorithms and the pivot selected for partition determines the overall Time Complexity of Quick Sort and the number of times the data is partitioned.
Q5. What is the best pivot for Quick Sort?
Median
Mean
Mode
25% percentile
Median is the best pivot for Quick Sort as it divides the array into two equal halves and this minimizes the number of partition calls. This results in O(N logN) time complexity. The challenge is to find the median element efficiently.
Q6. What is the best Time Complexity to find the median of an array?
O(N)
O(N logN)
O(logN)
O(1)
Finding the exact median of an array takes O(N) time complexity at minimum. This is achieved using an algorithm known as PICK. If we use this, then the time complexity of Quick Sort is maintained as O(N) but the run-time performance is worst. The key is to accelerate the algorithm finding the median.
Q7. Median of medians algorithm is frequently used to select pivot in Quick Sort. The median is between what percentile?
30 and 70 percentile
33 and 66 percentile
25 and 75 percentile
20 and 80 percentile
The median found by Median of medians algorithm is approximate that is it is not the correct answer but close to the correct answer. Therefore, the median found is between 30th and 70th percentile.
Q8. Practically, Quick Sort dominates all other Sorting algorithms. By how much % is Quick Sort worse than the best case on average?
39%
0%
16%
50%
On average, Quick Sort is 39% worse than its best case.
Q9. What is the Space Complexity of the original version of Quick Sort?
O(logN)
O(N)
O(1)
O(N logN)
Space Complexity of the original version of in-place Quick Sort is O(logN). The Stack call depth is bounded by O(logN).
Q10. In 2009, Vladimir Yaroslavskiy proposed a variant of Quick Sort using 2 pivots. Which Programming Language uses this variant instead of the heavily researched version of Quick Sort?
Java
Python
Rust
C++
Java uses the variant of Quick Sort by Vladimir Yaroslavskiy. The discussion was initiated by Vladimir in Java's mailing thread and after extensive tests, his variant was choosen to replace the highly optimized version of Quick Sort in Java 7.
Q11. What is the Best Case Time Complexity of Quick Sort?
O(N logN)
O(N)
O(logN)
O(1)
The Best Case Time Complexity of Quick Sort is O(N logN). This is in contrast to many other Sorting Algorithms which achieve O(N) time in the best case. This is because in the Best Case the median is selected as pivot always and O(logN) partitions are done each of O(N) time.
Q12. Is Quick Sort an in-place Sorting Algorithm?
Yes
No
Depends on Pivot selection
Only for specific variants
A original Quick Sort is an in-place Sorting Algorithm that is it sorts the original array and does not require an extra memory to produce output and maintain the original input.
Q13. Which partition scheme in Quick Sort does less number of swaps?
Hoare Partition
Lomuto Partition
Depends on input
Pseudomedian of Nine
Hoare Partition scheme does 3 times less swaps than Lomuto Partition. Lomuto Partition exists because it is simple to implement compared to Hoare Partition.
Q14. In practical implementations of Quick Sort, which Sorting Algorithm is used internally in Quick Sort?
Insertion Sort
Bubble Sort
Merge Sort
Heap Sort
In practical implementations of Quick Sort, Insertion Sort is used in the Median of Median algorithm which is used to select the pivot based on which the input is partitioned. Insertion Sort is used as the requirement is to sort 5 elements and it is the best choice of the size.
Q15. In which category does Quick Sort algorithm classify under?
Divide and Conquer
Greedy Algorithm
Dynamic Programming
Mathematical Algorithm
Quick Sort is a Divide and Conquer algorithm. The input is divided into smaller parts and the parts are in turn sorted using Quick Sort.
Q16. What is the Time Complexity of Quick Sort on Linked List?
O(N logN)
O(N^2)
O(N)
O(N logNlogN)
The Time Complexity of Quick Sort in Linked List is same as in Array that is O(N logN). This is because the disadvantage of accessing element at an index is O(N) instead of O(1) but this is not used in Linked List.
With these questions at OpenGenus, you must have a strong background in Quick Sort.
