Data Structures & Algorithms Multiple Choice Questions on “Recursive Bubble Sort”.
1. Which of the following is an advantage of recursive bubble sort over its iterative version? Answer: d 2. Bubble sort is also known as ___________ Answer: c 3. What will be the recurrence relation of the code of recursive bubble sort? 4. Which of the following sorting algorithm is stable? 5. Which of the following is a variation of bubble sort? Answer: b 6. Recursive bubble sort is a comparison based sort. Answer: a 7. What is the average case time complexity of recursive bubble sort? Answer: c 8. What is the best case time complexity of recursive bubble sort? 9. What is the worst case time complexity of recursive bubble sort? 10. What are the number of swaps required to sort the array arr={1, 2, 4, 3, 7, 5, 6} using recursive bubble sort? 11. What will be the base case for the code of recursive bubble sort? b) c) d) View Answer Answer: c 12. What is the auxiliary space complexity of recursive bubble sort? 13. Bubble sort is an adaptive sorting algorithm. Answer: a 14. Which of the following sorting algorithm is in place? Answer: a 15. Choose the correct function for recursive bubble sort? b) c) d) Answer: a
a) it has better time complexity
b) it has better space complexity
c) it is easy to implement
d) it has no significant advantage
Clarification: Recursive bubble sort has no significant advantage over iterative bubble sort. It is just a different way to implement the same.
a) stupid sort
b) ship sort
c) sinking sort
d) shell sort
Clarification: 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.
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
Answer: c
Clarification: 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.
a) Selection sort
b) Quick sort
c) Bubble sort
d) Heap sort
Answer: c
Clarification: 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.
a) selection sort
b) odd even sort
c) cocktail sort
d) stupid sort
Clarification: 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.
a) true
b) false
View Answer
Clarification: 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.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
Clarification: 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).
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
Answer: a
Clarification: The best case time complexity of recursive bubble sort is O(n). It occurs in the case when the input is already/almost sorted.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
Answer: c
Clarification: 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).
a) 0
b) 1
c) 2
d) 3
Answer: d
Clarification: 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.
a)
Clarification: 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.
a) O(n)
b) O(1)
c) O(n log n)
d) O(n2)
Answer: b
Clarification: The auxiliary space required by recursive bubble sort is O(1). So it qualifies as an in-place sorting algorithm.
a) true
b) false
Clarification: Bubble sort is an adaptive algorithm. It is because the time complexity of the algorithm improves when the input array is almost sorted.
a) recursive bubble sort
b) merge sort
c) radix sort
d) counting sort
Clarification: 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).
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);
}
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);
}
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);
}
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);
}
Clarification: 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.