Bubble Sorting in Data Structure

Bubble Sort:

Bubble Sort can be defined as a comparison-based sort by checking each adjacent pair of items in a list, in turn, swapping the items if necessary and repeating the pass through the list until no swaps are done.

Algorithm for Bubble Sort:

Algorithm fnBubbleSort(P[],n)
{
swap=TRUE;
for(Iteration=1;Iteration {
swap=FALSE;
for(j=0;j<n-Iteration; j++) { if(P[j]>P[j+1])
{
swap=TRUE;
temp=P[j];
P[j]=P[j+1];
P[j+1]=temp;
}
}
}
} // End of Algorithm

Time complexity of Bubble Sort:

1. Best Case: The array is in sorted order. Hence swap will remain false after the first iteration and so the process ends. Therefore the total number of comparisons made will be decided by the inner for the first iteration which is n-1.
T_b(n) = O(n)

2. Average Case: On average the comparison made in the inner loop is (k-1)/2
f(n)=(n-1)/2+(n-2)/2+…..+1/2
=n(n-1)/4
Therefore, T_a(n) = O(n²)

3. Worst Case: The array P[] is in reverse order. So for the first iteration, n-1 comparisons are needed, for the second iteration n-2 comparisons are needed and so on. Hence in the worst case:
f(n)=(n-1)+(n-2)+…..+1
=n(n-1)/2
Therefore, T_w(n) = O(n²)

Space complexity of Bubble Sort:

The space complexity is O(1), just a few scalar variables. Here, we don’t count the size of the array being sorted because that is given, not created specifically for this algorithm.