This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Stooge Sort”.
1. Which one of the following sorting algorithm requires recursion?
a) odd even sort
b) stooge sort
c) selection sort
d) counting sort
View Answer
Explanation: Stooge sort requires the use of recursion for implementing its algorithm. On the other hand, the sorting algorithms given in the remaining options use iterative methods.
2. What is the recurrence relation for stooge sort?
a) T(n) = 2T(2/3n) + O(n)
b) T(n) = 2T(2/3n) + O(1)
c) T(n) = 3T(2/3n) + O(n)
d) T(n) = 3T(2/3n) + O(1)
View Answer
Explanation: In stooge sort recursion is applied to 2/3 part of the array 3 times. Rest of the portion of code has a constant time complexity. So the overall recurrence relation becomes T(n) = 3T(2/3n) + O(1).
3. In which of the following case stooge sort is most efficient (in terms of time complexity)?
a) when input array is already sorted
b) when input array is reverse sorted
c) when input array is large
d) it has the same time complexity in any case
View Answer
Explanation: Stooge sort has the same time complexity under any case. It is given by the recurrence relation T(n) = 3T(2/3n) + O(1).
4. What is the space complexity of stooge sort?
a) O(n)
b) O(1)
c) O(log n)
d) O(n log n)
View Answer
Explanation: The space complexity of the stooge sort is O(n). It is used to store the input array.
5. What is the first step in the algorithm of stooge sort(after base case)?
a) apply stooge sort on first 2/3 elements of array
b) apply stooge sort on last 2/3 elements of array
c) apply stooge sort on first 1/3 elements of array
d) compare first and last element of the array
View Answer
Explanation: The first step in the algorithm of stooge sort is to compare the first and last element of the array and switch them if found out of order. In the second step stooge sort is applied on the first 2/3 elements of the array.
6. Stooge sort is a comparison based sorting algorithm.
a) true
b) false
View Answer
Explanation: Stooge sort is an example of a comparison based sorting algorithm. This is because it compares the value of elements present in a list in order to sort them.
7. Stooge sort is a stable sorting algorithm.
a) true
b) false
View Answer
Explanation: Stooge sort is not a stable sorting algorithm. It is because the elements with identical values do not appear in the same order in the output array as they were in the input array.
8. What is the average time complexity of stooge sort?
a) O(n2)
b) O(n3)
c) O(n2.6)
d) O(n2.7)
View Answer
Explanation: The recurrence relation of stooge sort is given as T(n) = 3T(2/3n) + O(1). It is found to be equal to O(n2.7) using the master’s theorem.
9. How many recursive statements are used in the algorithm of stooge sort?
a) 0
b) 1
c) 2
d) 3
View Answer
Explanation: The algorithm of stooge sort uses 3 recursive statements in its algorithm. The first and third recursive statement applies stooge sort to the first 2/3 elements of the array and the second recursive statement applies stooge sort to last 2/3 elements of the array.
10. Which of the following sorting algorithm has the same time complexity in every case?
a) stooge sort
b) strand sort
c) quick sort
d) bubble sort
View Answer
Explanation: Stooge sort has the same time complexity of O(n2.7) in any case. This also shows that it is not an adaptive sorting algorithm.
11. Which of the following sorting algorithm is worst in terms of time complexity?
a) bubble sort
b) selection sort
c) insertion sort
d) stooge sort
View Answer
Explanation: Stooge sort has a time complexity of O(n2.7) which is the worst out of the given options. This shows that stooge sort is even less efficient than bubble sort which is itself considered to be a very inefficient sort.
12. Which of the following is not an adaptive sorting algorithm?
a) insertion sort
b) strand sort
c) stooge sort
d) bubble sort
View Answer
Explanation: Stooge sort is not an adaptive sorting algorithm. This is because it does not perform better in the case when the array is already/almost sorted.
13. Choose the correct function for stooge sort?
a)
void stooge_sort(int arr[], int l, int r) { if (l >= r) return; if (arr[l] > arr[r]) swap(arr[l], arr[h]); if (r - l + 1 > =3) { int p = (r - l + 1) / 3; stooge_sort(arr, l, r - p); stooge_sort(arr, l + p, r); stooge_sort(arr, l, r - p); } }
b)
void stooge_sort(int arr[], int l, int r) { if (l >= r) return; if (arr[l] < arr[r]) swap(arr[l], arr[h]); if (r - l + 1 >=3) { int p = (r - l + 1) / 3; stooge_sort(arr, l, r - p); stooge_sort(arr, l + p, r); stooge_sort(arr, l, r - p); } }
c)
void stooge_sort(int arr[], int l, int r) { if (l >= r) return; if (arr[l] > arr[r]) swap(arr[l], arr[h]); if (r - l + 1 > =3) { int p = (r - l + 1) / 3; stooge_sort(arr, l, r - p); stooge_sort(arr, l, r - p); stooge_sort(arr, l + p, r); } }
d)
void stooge_sort(int arr[], int l, int r) { if (l >= r) return; if (arr[l] > arr[r]) swap(arr[l], arr[h]); if (r - l + 1 >=3) { int p = (r - l + 1) / 3; stooge_sort(arr, l + p, r); stooge_sort(arr, l, r - p); stooge_sort(arr, l, r - p); } }
Explanation: Stooge sort compare first and last element of the array and switch them if found out of order. Then it has 3 recursive statements. The first and third recursive statement applies stooge sort to the first 2/3 elements of the array and the second recursive statement applies stooge sort to last 2/3 elements of array.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Programming Books
- Check Design and Analysis of Algorithms Books
- Practice Data Structure MCQ
