Sorting Technique - Bubble Sort
- abhijitsathe
- Oct 4
- 3 min read
Updated: Oct 4
Q.1) What are the critical operations for Bubble Sort?
Comparison and Swapping are two critical operations for sorting. Bubble sort requires both comparison and swapping , hence it is least efficient.
Q.2) What is the basic idea of Bubble Sort ? (How it sorts?)
The bubble sort passes through the file(or array) sequentially several times. Each pass consists of comparing each element in the file with its successor (x[i] with x[i+1]) and interchanging the two elements if they are not in proper order.
Q.3) Sort following integers using Bubble Sort in ascending order: 25,57,48,37,12,92,86,33
ORIGINAL FILE 25 57 48 37 12 92 86 33
PASS 1 25 48 37 12 57 86 33 92
PASS 2 25 37 12 48 57 33 86 92
PASS 3 25 12 37 48 33 57 86 92
PASS 4 12 25 37 33 48 57 86 92
PASS 5 12 25 33 37 48 57 86 92
PASS 2 12 25 33 37 48 57 86 92
PASS 2 12 25 33 37 48 57 86 92
Q.4) What can be said about efficiency of Bubble Sort?
For unimproved Bubble Sort, (n-1) passes and (n-1) comparisons in each pass , which means (n-1)X(n-1) comparisons , which is O(n-square). The number of interchanges depends on the original order of the file. The number of interchanges (swappings) cannot be greater than number of comparisons. In other words, Interchanges takes more time than comparisons.
For an improved version, the time complexity remains same O(n-square) but constant multiplier is smaller than unimproved version. It means, lesser comparisons and interchanges than unimproved version.
The space complexity of bubble sort is O(n) for n elements and one additional space for interchanging elements.
Q.5) What are the improvement possible for Bubble Sort
Q.6) What are the best case, average case and worst case of Bubble Sort?
Best Case - Sorted or partially sorted file ( applicable only for improved version).
Average Case - Elements are unsorted.
Worst Case - Elements are oppositely sorted.
Q.7) What is the best case, average case and worst case efficiency of Bubble Sort?
Best Case - Partially Sorted - O(n)
Average Case - Unsorted - O(n-square)
Worst Case - Oppositely Sorted O(n-square) - more comparisons than average case
Q.8) Write a C function to implement Bubble Sort (Improved) ?
#define MAXSZ 10
enum boolean { FALSE = 0, TRUE = 1 };
void bubble_sort(int a[], int n)
{
int hold;
enum boolean swapped = TRUE;
int pass, j;
for (pass=1;pass < n && swapped == TRUE; pass++)
{
swapped = FALSE;
for (j=0;j<=n-pass-1;j++)
{
if (a[j] > a[j+1])
{
swapped = TRUE;
hold = a[j];
a[j] = a[j+1];
a[j+1] = hold;
}
}
}
}
Q.9) What are the limitations of Bubble Sort?
Q.10) What are the advantages of Bubble Sort?
Generally people has a perception that Bubble Sort is not advantageous. But, following are some features of Bubble Sort which makes it useful when data set is small (usually 25-50 records).
Want to read more?
Subscribe to questionbankos.com to keep reading this exclusive post.