Stooge Sort Multiple Choice Questions and Answers (MCQs)

«
»

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

Answer: b
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.
advertisement

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

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

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

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

Answer: d
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.
advertisement

6. Stooge sort is a comparison based sorting algorithm.
a) true
b) false
View Answer

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

Answer: b
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

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

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

Answer: a
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.
advertisement

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

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

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

advertisement
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); 
	} 
}
View Answer
Answer: a
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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn