This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Bubble Sort”.

1. What is an external sorting algorithm?

a) Algorithm that uses tape or disk during the sort

b) Algorithm that uses main memory during the sort

c) Algorithm that involves swapping

d) Algorithm that are considered ‘in place’

View Answer

Explanation: As the name suggests, external sorting algorithm uses external memory like tape or disk.

2. What is an internal sorting algorithm?

a) Algorithm that uses tape or disk during the sort

b) Algorithm that uses main memory during the sort

c) Algorithm that involves swapping

d) Algorithm that are considered ‘in place’

View Answer

Explanation: As the name suggests, internal sorting algorithm uses internal main memory.

3. What is the worst case complexity of bubble sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

View Answer

Explanation: Bubble sort works by starting from the first element and swapping the elements if required in each iteration.

4. Select the appropriate code that performs bubble sort.

a)

for(int j=arr.length-1; j>=0; j--) { for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; } } }

b)

for(int j=arr.length-1; j>=0; j--) { for(int k=0; k<j; k++) { if(arr[k] < arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; } } }

c)

for(int j=arr.length; j>=0; j--) { for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; } } }

d) None of the mentioned

View Answer

Explanation: The outer loop keeps count of number of iterations, and the inner loop checks to see if swapping is necessary.

5. What is the average case complexity of bubble sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

View Answer

Explanation: Bubble sort works by starting from the first element and swapping the elements if required in each iteration even in the average case.

6. What is the advantage of bubble sort over other sorting techniques?

a) It is faster

b) Consumes less memory

c) Detects whether the input is already sorted

d) All of the mentioned

View Answer

Explanation: Bubble sort is one of the simplest sorting techniques and perhaps the only advantage it has over other techniques is that it can detect whether the input is already sorted.

7. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?

a) 4

b) 2

c) 1

d) 0

View Answer

Explanation: Even though the first two elements are already sorted, bubble sort needs 4 iterations to sort the given array.

8. How can you improve the best case efficiency in bubble sort? (The input is already sorted)

a)

boolean swapped = false; for(int j=arr.length-1; j>=0 && swapped; j--) { swapped = true; for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; swapped = false; } } }

b)

boolean swapped = true; for(int j=arr.length-1; j>=0 && swapped; j--) { swapped = false; for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; } } }

c)

boolean swapped = true; for(int j=arr.length-1; j>=0 && swapped; j--) { swapped = false; for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; swapped = true; } } }

d)

boolean swapped = true; for(int j=arr.length-1; j>=0 && swapped; j--) { for(int k=0; k<j; k++) { if(arr[k] > arr[k+1]) { int temp = arr[k]; arr[k] = arr[k+1]; arr[k+1] = temp; swapped = true; } } }

Explanation: A boolean variable ‘swapped’ determines whether any swapping has happened in a particular iteration, if no swapping has occurred, then the given array is sorted and no more iterations are required.

9. What is the best case efficiency of bubble sort in the improvised version?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

View Answer

Explanation: Some iterations can be skipped if the list is sorted, hence efficiency improves to O(n).

10. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version?

a) 4

b) 2

c) 1

d) 0

View Answer

Explanation: Only 2 elements in the given array are not sorted, hence only 2 iterations are required to sort them.

**Sanfoundry Global Education & Learning Series – Data Structure.**

To practice all areas of Data Structure, __here is complete set of 1000+ Multiple Choice Questions and Answers__.