This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Recursive Bubble Sort”.
1. Which of the following is an advantage of recursive bubble sort over its iterative version?
a) it has better time complexity
b) it has better space complexity
c) it is easy to implement
d) it has no significant advantage
View Answer
Explanation: Recursive bubble sort has no significant advantage over iterative bubble sort. It is just a different way to implement the same.
2. Bubble sort is also known as ___________
a) stupid sort
b) ship sort
c) sinking sort
d) shell sort
View Answer
Explanation: Bubble sort is also referred to as sinking sort. It continuously compares the value of adjacent elements as it traverses through an array and swaps the elements which are out of order.
3. What will be the recurrence relation of the code of recursive bubble 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
Explanation: The recurrence relation of the code of recursive bubble sort is T(n) = T(n-1) + n. It can be solved by the method of substitution and is found to be equal to n2.
4. Which of the following sorting algorithm is stable?
a) Selection sort
b) Quick sort
c) Bubble sort
d) Heap sort
View Answer
Explanation: Out of the given options bubble sort is the only algorithm which is stable. It is because the elements with identical values appear in the same order in the output array as they were in the input array.
5. Which of the following is a variation of bubble sort?
a) selection sort
b) odd even sort
c) cocktail sort
d) stupid sort
View Answer
Explanation: Odd even sort is a variation of bubble sort. But unlike bubble sort, odd even sort traverses the array in two phases- odd phase and even phase.
6. Recursive bubble sort is a comparison based sort.
a) true
b) false
View Answer
Explanation: In bubble 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 bubble sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The overall recurrence relation of recursive bubble sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2).
8. What is the best case time complexity of recursive bubble sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The best case time complexity of recursive bubble sort is O(n). It occurs in the case when the input is already/almost sorted.
9. What is the worst case time complexity of recursive bubble sort?
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
View Answer
Explanation: The overall recurrence relation of recursive bubble sort is given by T(n) = T(n-1) + n. It is found to be equal to O(n2).
10. What are the number of swaps required to sort the array arr={1, 2, 4, 3, 7, 5, 6} using recursive bubble sort?
a) 0
b) 1
c) 2
d) 3
View Answer
Explanation: The first swap takes place between 4 and 3 then the second swap takes place between 7 and 5 and then finally 6 and 7 are swapped which sorts our array.
11. What will be the base case for the code of recursive bubble sort?
a)
if(n < 1) return;
b)
if(n == 0) return;
c)
if(n == 1) return;
d)
If(n == 2) return;
Explanation: The most appropriate condition for the base case of recursive bubble sort is when n equal 1 then return. It is because we know that an array with only 1 element is always sorted.
12. What is the auxiliary space complexity of recursive bubble sort?
a) O(n)
b) O(1)
c) O(n log n)
d) O(n2)
View Answer
Explanation: The auxiliary space required by recursive bubble sort is O(1). So it qualifies as an in-place sorting algorithm.
13. Bubble sort is an adaptive sorting algorithm.
a) true
b) false
View Answer
Explanation: Bubble sort is an adaptive algorithm. It is because the time complexity of the algorithm improves when the input array is almost sorted.
14. Which of the following sorting algorithm is in place?
a) recursive bubble sort
b) merge sort
c) radix sort
d) counting sort
View Answer
Explanation: Out of the given options recursive bubble sort is the only algorithm which is in place. It is because the auxiliary space required by recursive bubble sort is O(1).
15. Choose the correct function for recursive bubble sort?
a)
void rec_bubbleSort(int arr[], int n) { if (n == 1) return; for (int i=0; i<n-1; i++) if (arr[i] > arr[i+1]) { swap(arr[i], arr[i+1]); } rec_bubbleSort(arr, n-1); }
b)
void rec_bubbleSort(int arr[], int n) { if (n == 2) return; for (int i=0; i<n-1; i++) if (arr[i] > arr[i+1]) { swap(arr[i], arr[i+1]); } rec_bubbleSort(arr, n-1); }
c)
void rec_bubbleSort(int arr[], int n) { if (n == 1) return; for (int i=0; i<n-1; i++) if (arr[i] < arr[i+1]) { swap(arr[i], arr[i+1]); } rec_bubbleSort(arr, n-1); }
d)
void rec_bubbleSort(int arr[], int n) { if (n == 2) return; for (int i=0; i<n-1; i++) if (arr[i] < arr[i+1]) { swap(arr[i], arr[i+1]); } rec_bubbleSort(arr, n-1); }
Explanation: The base case of the recursive bubble sort should be 1 when equal 1 then return. It is because we know that an array with only 1 element is always sorted. Also, we need to swap the adjacent elements which are out of order.
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]
- Practice Programming MCQs
- Check Programming Books
- Practice Computer Science MCQs
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
