This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Introsort”.
1. Why is heap sort preferred over merge sort for introsort implementation?
A) Because heap sort is faster
B) Because heap sort requires less space
C) Because heap sort is easy to implement
D) Because heap sort is easy to understand
Explanation: The time complexity of heap sort and merge sort is the same. However, heap sort is an in-place sorting algorithm, while merge sort necessitates O(n) auxiliary space, making heap sort the better option.
2. Why is insertion sort preferred over other sorting algorithms (like selection sort, bubble sort etc.) for introsort implementation?
A) Because insertion sort is faster and adaptive
B) Because insertion sort requires less space
C) Because insertion sort is easy to implement
D) Because insertion sort is easy to understand
Explanation: When it comes to sorting small arrays, insertion sort is the best choice. It’s also adaptive, so it outperforms most when the list is entirely or partially sorted.
3. What is the cut-off for switching from quick sort to insertion sort in the implementation of introsort?
Explanation: When small arrays need to be sorted, insertion sort is the most efficient method. Introsort moves to insertion sort when the partition size is less than 16. This value was calculated by experimentation.
4. What is the cut-off for switching from quick sort to heap sort in the implementation of introsort?
C) n log(n)
D) 2 log (n)
Explanation: Quicksort has an O(n2) worst-case time complexity, which is not ideal. When the depth is greater than 2 log, introsort switches to heap sort to prevent the worst case of quicksort (n). This value was calculated by experimentation.
5. Which of the following sorting algorithm will be preferred when the size of partition is between 16 and 2 log(n) while implementing introsort?
A) quick sort
B) insertion sort
C) heap sort
D) merge sort
Explanation: Because of its low space and time complexity, Quicksort is the best sorting algorithm for mid-sized arrays. When the partition size is between 16 and 2 log, simple sort is preferred (n).