Engineering Questions with Answers - Multiple Choice Questions
Introsort MCQ’s
1 - Question
Which of the following sorting algorithm is used by C++ internally?
a) quicksort
b) introsort
c) merge sort
d) heap sort
View Answer
Answer: b
Explanation: Introsort is the in built sorting algorithm used by C++. It is an example of a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine.
2 - Question
Which of the following sorting algorithm is not a constituent of introsort?
a) selection sort
b) quicksort
c) insertion sort
d) heap sort
View Answer
Answer: a
Explanation: Introsort is a hybrid sorting algorithm which means it uses more than one sorting algorithm as a routine. It may use quick sort or heap sort or insertion sort depending on the given situation.
3 - Question
Introsort begins sorting the given array by using which of the following sorting algorithm?
a) selection sort
b) quick sort
c) insertion sort
d) heap sort
View Answer
Answer: b
Explanation: Introsort begins sorting any given array by using quick sort. Then it may switch to heap sort or insertion sort or may stick to quick sort depending upon the size of the partition.
Explanation: Introsort begins sorting any given array by using quick sort. Then it may switch to heap sort or insertion sort or may stick to quick sort depending upon the size of the partition.
4 - Question
Which of the following sorting algorithm is NOT stable?
a) Introsort
b) Brick sort
c) Bubble sort
d) Merge sort
View Answer
Answer: a
Explanation: Out of the given options introsort is the only algorithm which is not stable. As it may use quick sort in some case to perform sorting which is itself not stable. Thus stability of introsort is not guaranteed.
5 - Question
Which of the following sorting algorithm is in-place?
a) intro sort
b) merge sort
c) counting sort
d) radix sort
View Answer
Answer: a
Explanation: Introsort may use quick sort or heap sort or insertion sort internally in order to sort the given input. All of the three algorithms are in place, thus making introsort to be an in-place sorting algorithm
6 - Question
Introsort sort is a comparison based sort.
a) true
b) false
View Answer
Answer: a
Explanation: Quicksort, heap sort and insertion sort are comparison based sorts. Thus overall introsort also becomes a comparison based sort.
7 - Question
What is the best case time complexity of introsort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: b
Explanation: Introsort is mainly governed by heap sort and quick sort. As the best case of both heap sort and quick sort is O(n log n) so the best case of introsort also becomes O(n log n).
8 - Question
What is the worst case time complexity of introsort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: b
Explanation: Worst case time complexity of quicksort is avoided when we implement introsort. Introsort switches to heap sort when there is a possibility of crossing the maximum depth limit.
9 - Question
What is the average time complexity of introsort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: b
Explanation: Average time complexity of introsort remains to be O(n log n) as for most of the cases quick sort and heap sort are used which have O(n log n) time complexity for an average case.
10 - Question
What is the auxiliary space requirement of introsort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Answer: d
Explanation: Introsort is a hybrid of quick sort, heap sort and insertion sort. So like quick sort it may use O(log n) auxiliary space in the stack to store call statements.
11 - Question
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
View Answer
Answer: b
Explanation: Both heap sort and merge sort have the same time complexity. But heap sort is an in-place sorting algorithm whereas merge sort requires O(n) auxiliary space which makes heap sort a more preferable option
12 - Question
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
View Answer
Answer: a
Explanation: When small arrays need to be sorted then insertion sort proves to be the best choice. Also it is adaptive so it performs better than others when the given array is fully/partially sorted.
13 - Question
What is the cut-off for switching from quick sort to insertion sort in the implementation of introsort?
a) 4
b) 8
c) 16
d) 32
View Answer
Answer: c
Explanation: When small arrays needs to be sorted then insertion sort proves to be the best choice. So when the size of the partition is less than 16 introsort switches to insertion sort. This particular value has been deduced experimentally.
14 - Question
What is the cut-off for switching from quick sort to heap sort in the implementation of introsort?
a) 16
b) n2
c) n log(n)
d) 2 log (n)
View Answer
Answer: d
Explanation: Quicksort has a worst case time complexity of O(n2) which is not preferable. So in order to avoid worst case of quicksort, introsort switches to heap sort when the depth is greater than 2 log(n). This particular value has been deduced experimentally.
15 - Question
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
View Answer
Answer: a
Explanation: Quicksort proves to be the best sorting algorithm for mid sized arrays as it has low space and time complexity. Thus quick sort is preferred when size of partition is between 16 and 2 log(n).
16 - Question
What will be the output of the given C++ code?
#include <bits/stdc++.h> using namespace std; int main() { int arr[] = {1,3,4,2,5}; int n = sizeof(arr)/sizeof(arr[0]); sort(arr, arr+n, greater<int>()); int a; for (a = 0; a < n; a++) cout << arr[a] << " "; return 0; }
a) 1 2 3 4 5
b) 1 3 4 2 5
c) 5 4 3 2 1
d) errorAnswer: c
Explanation: The given program sorts the input in descending order. It is due to the third parameter i.e. greater() which is passed to the function sort().
View Answer
Answer: c
Explanation: The given program sorts the input in descending order. It is due to the third parameter i.e. greater() which is passed to the function sort().
17 - Question
. What will be the output of the given C++ code?
#include <bits/stdc++.h> using namespace std; int main() { int arr[] = {1, 3,4,2,5}; int n = sizeof(arr)/sizeof(arr[0]); sort(arr, arr+n); int a; for ( a = 0; a< n; a++) cout << arr[a] << " "; return 0; }
a) 1 2 3 4 5
b) 1 3 4 2 5
c) 5 4 3 2 1
d) error
View Answer
Answer: a
Explanation: The given program sorts the input in ascending order. Function sort() uses two parameters in the form of address of the first and last element of the array to sort the array.
18 - Question
What will be the output of the given C++ code?
#include <bits/stdc++.h> using namespace std; int main() { int arr[] = {1, 3,4,2,5}; int n = sizeof(arr)/sizeof(arr[0]); sort(arr+2, arr+n, greater<int>()); int a; for (int a = 0; a < n; a++) cout << arr[a] << " "; return 0; }
a) 1 2 3 4 5
b) 1 5 4 3 2
c) 5 4 3 2 1
d) 1 3 5 4 2
View Answer
Answer: d
Explanation: As the first parameter to function sort() is arr+2 so the sorting begins from the third element i.e. 4. Also as there is a third argument greater () to the function sort() so the sorting will be done in descending order.