Recursive Selection Sort Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Recursive Selection Sort”.

1. Which of the following sorting algorithm has best case time complexity of O(n2)?
a) bubble sort
b) selection sort
c) insertion sort
d) stupid sort
View Answer

Answer: b
Explanation: Selection sort is not an adaptive sorting algorithm. It finds the index of minimum element in each iteration even if the given array is already sorted. Thus its best case time complexity becomes O(n2).

2. Which of the following is the biggest advantage of selection sort?
a) its has low time complexity
b) it has low space complexity
c) it is easy to implement
d) it requires only n swaps under any condition
View Answer

Answer: d
Explanation: Selection sort works by obtaining least value element in each iteration and then swapping it with the current index. So it will take n swaps under any condition which will be useful when memory write operation is expensive.

3. What will be the recurrence relation of the code of recursive selection sort?
a) T(n) = 2T(n/2) + n
b) T(n) = 2T(n/2) + c
c) T(n) = T(n-1) + n
d) T(n) = T(n-1) + c
View Answer

Answer: c
Explanation: Function to find the minimum element index takes n time.The recursive call is made to one less element than in the previous call so the overall recurrence relation becomes T(n) = T(n-1) + n.
advertisement
advertisement

4. Which of the following sorting algorithm is NOT stable?
a) Selection sort
b) Brick sort
c) Bubble sort
d) Merge sort
View Answer

Answer: a
Explanation: Out of the given options selection sort is the only algorithm which is not stable. It is because the order of identical elements in sorted output may be different from input array.

5. What will be the best case time complexity of recursive selection sort?
a) O(n)
b) O(n2)
c) O(log n)
d) O(n log n)
View Answer

Answer: b
Explanation: Selection sort’s algorithm is such that it finds the index of minimum element in each iteration even if the given array is already sorted. Thus its best case time complexity becomes O(n2).
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Recursive selection sort is a comparison based sort.
a) true
b) false
View Answer

Answer: a
Explanation: In selection sort we need to compare elements in order to find the minimum element in each iteration. So we can say that it uses comparisons in order to sort the array. Thus it qualifies as a comparison based sort.

7. What is the average case time complexity of recursive selection sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer

Answer: c
Explanation: The overall recurrence relation of recursive selection sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2). It is unvaried throughout the three cases.
advertisement

8. What is the bidirectional variant of selection sort?
a) cocktail sort
b) bogo sort
c) gnome sort
d) bubble sort
View Answer

Answer: a
Explanation: A bidirectional variant of selection sort is called cocktail sort. It’s an algorithm which finds both the minimum and maximum values in the array in every pass. This reduces the number of scans of the array by a factor of 2.

9. Choose correct C++ code for recursive selection sort from the following.
a)

advertisement
#include <iostream> 
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == 0) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] < a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 
 
	if (index == n) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x == index) 
	{	    
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]);  
	recursiveSelectionSort(arr, n); 	
	return 0; 
}

b)

#include <iostream> 
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] < a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 
 
	if (index == n) 
        return; 	 
	int x = minIndex(a, index, n-1);	 
	if (x != index) 
	{
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]);  
	recursiveSelectionSort(arr, n); 	
	return 0; 
}

c)

#include <iostream> 
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 
	return (a[i] > a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 	
	if (index == n) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x != index) 
	{	    
	    	swap(a[x], a[index]);
	} 
	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
        recursiveSelectionSort(arr, n); 
	return 0; 
}

d)

 #include <iostream> 
using namespace std; 
int minIndex(int a[], int i, int j) 
{ 
	if (i == j) 
		return i; 	
	int k = minIndex(a, i + 1, j); 	
	return (a[i] > a[k])? i : k; 
} 
void recursiveSelectionSort(int a[], int n, int index = 0) 
{ 	
	if (index == 0) 
	return; 	 
	int x = minIndex(a, index, n-1); 	 
	if (x == index) 
	{	    
	    	swap(a[x], a[index]);
	}
 	recursiveSelectionSort(a, n, index + 1); 
}  
int main() 
{ 
	int arr[] = {5,3,2,4,1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	recursiveSelectionSort(arr, n); 
        return 0; 
}
View Answer
Answer: b
Explanation: Using the function recursiveSelectionSort() we find the element that needs to be placed at the current index. For finding the minimum element index we use another function minIndex(). After finding the minimum element index the current element is swapped with this element in the function recursiveSelectionSort().
 
 

10. What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort?
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: c
Explanation: The first swap takes place between 1 and 5. The second swap takes place between 3 and 2 which sorts our 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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). 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!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.