Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.

How does Bubble Sort Work?

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)

1. Starting from the first index, compare the first and the second elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the second and the third elements. Swap them if they are not in order.
4. The above process goes on until the last element

Below is the implementation of the bubble sort. It can be optimized by stopping the algorithm if the inner loop didn’t cause any swap.

#include <stdio.h>
int main()
{
int arr[100], size, i, j, swap;

printf(“Enter Array size: “);
scanf(“%d”, &size);

printf(“Enter %d integers: “, size);

for (i=0; i<size; i++){
scanf(“%d”, &arr[i]);
}
for (i=0 ; i<size-1; i++)
{
for (j=0; j<size-i-1; j++)
{
if (arr[j] > arr[j+1])
{
swap = arr[j];
arr[j] = arr[j+1];
arr[j+1] = swap;
}
}
}
printf(“\nSorted list in ascending order: \n”);
for (i=0; i<size; i++)
printf(“%d “, arr[i]);

return 0;
}

Complexity Analysis of Bubble Sort:

Time Complexity: O(n²)
Auxiliary Space: O(1)

Advantages of Bubble Sort:

• Bubble sort is easy to understand and implement.
• It does not require any additional memory space.
• It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the sorted output.

Disadvantages of Bubble Sort:

• Bubble sort has a time complexity of O(n²) which makes it very slow for large data sets.
• Bubble sort is a comparison-based sorting algorithm, which means that it requires a comparison operator to determine the relative order of elements in the input data set. It can limit the efficiency of the algorithm in certain cases.