250+ TOP MCQs on Stooge Sort and Answers

Data Structures & Algorithms Multiple Choice Questions 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

Answer: b
Clarification: 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)
Answer: d
Clarification: 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

Answer: d
Clarification: 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)

Answer: a
Clarification: 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

Answer: d
Clarification: 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
Answer: a
Clarification: 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

Answer: b
Clarification: 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(n²)
b) O(n³)
c) O(n^2.6)
d) O(n^2.7)
Answer: d
Clarification: The recurrence relation of stooge sort is given as T(n) = 3T(2/3n) + O(1). It is found to be equal to O(n^2.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

Answer: d
Clarification: 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

Answer: a
Clarification: Stooge sort has the same time complexity of O(n^2.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

Answer: d
Clarification: Stooge sort has a time complexity of O(n^2.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

Answer: c
Clarification: 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); 
	} 
}