Bubble Sort – Data Structure Questions and Answers

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

1. What is the average case complexity of bubble sort?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: Except in the most common case, bubble sort works by beginning with the first element and swapping elements as required in each iteration.

2. 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: The Optimised Bubble Sort is one of the most basic sorting strategies, with the benefit of being able to detect whether the input has already been sorted. In the case of a sorted array, it is faster than the others, and it takes less time to define whether the input array is sorted or not. It uses the same amount of memory as other sorting methods. As a result, it is not a gain.

3. 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: Bubble sort requires four iterations to sort the given array, even though the first two elements are already sorted.

4. 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: The boolean variable ‘swapped’ specifies if any swapping took place in a given iteration; if no swapping took place, the given array is sorted, and no further iterations are needed.

5. 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: If the list is sorted, several iterations can be skipped, increasing efficiency to O. (n).

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

Explanation: Only two elements in the specified array are not sorted, so sorting them takes only two iterations.

7. 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: External sorting algorithms, as the name implies, use external memory such as tape or disc.

8. 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: Internal sorting algorithm uses internal main memory, as the name implies.

9. What is the worst case complexity of bubble sort?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: Each iteration of bubble sort begins with the first element and swaps the elements as required.

10. 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 track of the number of iterations, while the inner loop determines whether swapping is needed.

Bubble sort, also known as sinking sort, is a basic sorting algorithm that iterates through a list, comparing adjacent elements and swapping them if they are out of order. The list is passed over again and again until it is sorted. The comparison sort algorithm is named for the way that smaller or larger elements “bubble” to the top of the list. This basic algorithm performs poorly in real-world situations and is mainly used as a teaching aid. The sorting libraries built into common programming languages like Python and Java use more powerful algorithms like quicksort, timsort, or merge sort.