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 n

^{2}.

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(n^{2})

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(n

^{2}).

8. What is the best case time complexity of recursive bubble sort?

a) O(n)

b) O(n log n)

c) O(n^{2})

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(n^{2})

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(n

^{2}).

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(n^{2})

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__.