Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Bubble Sort

1 - Question

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’

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

2 - Question

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’

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

3 - Question

What is the worst case complexity of bubble sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

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

4 - Question

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)

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

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

5 - Question

What is the average case complexity of bubble sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

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 - Question

Which of the following is not an advantage of optimised bubble sort over other sorting techniques in case of sorted elements?
a) It is faster
b) Consumes less memory
c) Detects whether the input is already sorted
d) Consumes less time

Explanation: Optimised 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. It is faster than other in case of sorted array and consumes less time to describe whether the input array is sorted or not. It consumes same memory than other sorting techniques. Hence it is not an advantage.

7 - Question

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

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

8 - Question

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 - Question

What is the best case efficiency of bubble sort in the improvised version?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

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

10 - Question

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