Bubble Sort Time Complexity

July 24, 2022 | by Arround The Web | No comments

The simplest sorting algorithm is the bubble sort algorithm. Given an unsorted list, and starting from the left end, the algorithm swaps the first two elements if they are not in order. It swaps the next two elements, one would be from the first swap if swapping took place. It swaps the next two elements, one would be from the previous swap if swapping took place. This continues until the element at the extreme right is addressed. The whole list is re-scanned in that fashion; over and over, until the list is completely sorted.

In this article, sort ascending is considered. This article aims to indicate the relative speed of the bubble sort algorithm. This relative speed is referred to as time complexity. Coding is done in the C computer language.

Article Content

Introduction – see above
Bubble Sort Illustration
Worst-Case Performance
Better Performance for Bubble Sort
Some Interspersed Sequence of elements already Sorted
Perfect Case
Conclusion

Bubble Sort Illustration

Consider the following unsorted list:

R X F S U Z V J

There are 8 elements, which need 8 complete scans, resulting in:

R    F    S    U    X    V    J    Z
F    R    S    U    V    J    X    Z
F    R    S    U    J    V    X    Z
F    R    S    J    U    V    X    Z
F    R    J    S    U    V    X    Z
F    J    R    S    U    V    X    Z
F    J    R    S    U    V    X    Z
F    J    R    S    U    V    X    Z

The final list arrangement is the complete sort.

Worst-Case Performance

The C code to sort the previous eight characters, previously explained is:

#include <stdio.h>

void bubbleSort(char arr[], int n) {
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
if (arr[j] < arr[j - 1]) {
char temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
counter+=1;
}
}
printf("%i\n", counter);
}

The code for swapping is in the inner nested for-loop. The counter counts the number of basic operations. The outer for-loop loops from 0 to 7, i.e., 8 times. The inner for-loop loops from 1 to 7, i.e., 7 times. The total number of basic operations (inner for-loop) is 8 x 7 = 56. The counter output is 56.

If the inner for-loop looped from 0 to 7, then the total number of basic operations would have been 8 x 8 = 64. This is the maximum number of basic operations for this nesting for-loops. Let 8 be n. Then, the maximum number of such nesting for-loops is n².

The worst-case time complexity for the previous function is given as,
O(n²)

The big O followed by its parentheses with n² is called the big-O notation. It indicates the relative speed of the code. Though in the previous code, the number of basic operations is 56, the maximum possible number of operations, 8² = 64, is what would be given for the time complexity.

A suitable C main function for the previous code is:

int main(int argc, char **argv)
{
int n = 8;
char arr[] = {'R', 'X', 'F', 'S', 'U', 'Z', 'V', 'J'};
bubbleSort(arr, n);
for (int i=0; i<n; i++)
printf("%c ", arr[i]);
printf("\n");

return 0;
}

Better Performance for Bubble Sort

Notice in the previous illustration for the bubble sort; after the first scan, the highest element is at the right end. After the second scan, the highest two elements are at the right end, in order. After the third scan, the highest three elements are at the right end, in order, and so on. Operations on these extreme-right elements as they grow can be omitted in coding. This would increase overall speed (time for complete sorting). The following modified code illustrates this:

void bubbleSort(char arr[], int n) {
int counter = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < n-i; j++) {
if (arr[j] < arr[j - 1]) {
char temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
counter+=1;
}
}
printf("%i\n", counter);
}

This time, the counter output is 28. The number of basic operations is 28, slightly less than half of 64, which is 32. The inner for-loop loops from 1 to n – i. In its first scan, i is zero, and n – i = 8.

Now,

log₂ 8 = log₂ 2³
= 3

8 x 3 = 8xlog₂ 2³
= 24

which is close to 28. Let n = 8. The last-but-one right operand expression above, becomes n.log₂ 2³, = n.log₂ 8, generally written as, n log n.

When the time complexity is within some middle range, 20 to 40, in this case, it is expressed as:
O(n log n)

Where n is the number of elements in the list. So, the time complexity for the improved performance of bubble sort is n log n, meaning n x log₂(n).

Some Interspersed Sequence of Elements Already Sorted

There are eight scans for the previous bubble sort illustration. Notice that by the sixth scan, the list was completely already sorted. The last two rows are repetitions of the sixth row. For this particular unsorted list, the previous two scans were not necessary. This happens when the given unsorted list has some already sorted interspersed sequences. If the given list is completely unsorted, then the last row would be the final sorted list (it would not be a repetition of the previous).

The last rows like the last two above can be omitted in the sorting, and so improve performance (speed). The following code illustrates this:

void bubbleSort(char arr[], int n) {
_Bool swapped = 0;
for (int i = 0; i < n; i++) {
swapped = 0;
for (int j = 1; j < n-i; j++) {
if (arr[j] < arr[j - 1]) {
char temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
swapped = 1;
}
}
if (swapped == 0)
break;
}
}

Perfect Case

Perfect performance occurs when the given list is already completely sorted. The code to test this is:

void bubbleSort(char arr[], int n) {
int counter = 0;
_Bool swapped = 0;
for (int i = 0; i < n; i++) {
swapped = 0;
for (int j = 1; j < n-i; j++) {
if (arr[j] < arr[j - 1]) {
char temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
swapped = 1;
}
counter+=1;
}
if (swapped == 0)
break;
}
printf("%i\n", counter);
}

The output is:

7
F J R S U V X Z

for an input list of,

F J R S U V X Z

The 7 is from the inner for-loop. However, for time complexity, a maximum of 8 is considered. The time complexity for perfect performance is expressed as:
O(n)

Conclusion

In this article, we discussed the bubble sort time complexity and emphasized the following:

The worst-case time complexity for bubble sort is:
O(n²)

With the improvement of code, the time complexity becomes:
O(n log n)

When the given list is already completely sorted, the time complexity is:
O(n)

Source: linuxhint.com