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:

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

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:

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^{2}.

The worst-case time complexity for the previous function is given as,

O(n^{2})

The big O followed by its parentheses with n^{2} 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^{2} = 64, is what would be given for the time complexity.

A suitable C main function for the previous code is:

**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:

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_{2} 8 = log_{2} 2^{3}

= 3

8 x 3 = 8xlog_{2} 2^{3}

= 24

which is close to 28. Let n = 8. The last-but-one right operand expression above, becomes n.log_{2} 2^{3}, = n.log_{2} 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_{2}(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:

_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:

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:

F J R S U V X Z

for an input list of,

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^{2})

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)