Sorting is one of the most essential topics in Data Structure and algorithms. It is used to order the items in a specific manner, and many other algorithms require sorting to function efficiently. There are many sorting algorithms like bubble sort, quick sort, merge sort, insertion sort, etc.

The Bubble Sort algorithm is the most basic among all of these.

In this blog, we will discuss the bubble sort algorithm, starting with the introduction, its uses, implementation, and time & space complexity.

What is the Bubble Sort Algorithm?

Bubble sort is a Sorting algorithm that compares the adjacent elements repeatedly and swaps them if they are out of order until the entire array is sorted.

Have you ever wondered why the name is bubblesort?

Just like the bubbles in water rise up the surface, the elements move towards the end of the array in every iteration. Depending on the order of sorting, i.e., if we want to sort in increasing order, then the larger elements move toward the end, and if it's decreasing order it's the smaller elements.

The bubble sort algorithm is an excellent start for anyone who wants to understand sorting. Let's see the steps you must follow while performing bubble sort.

Consider you want to sort an array arr consisting of N elements in ascending order.

Bubble sort Pseudocode

begin BubbleSort(arr[0…N-1])
for all elements in the array arr
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort

More formally, we can write down the steps as follows:

Use two loops to iterate through the input array.

The outer loop runs from i=0 to i=n-2.

The inner loop runs from j=0 to j=n-i-2;

For every j, compare arr[j] and arr[j+1]. If arr[j]>arr[j+1], then swap them or else move forward.

How does Bubble Sort Work?

Let’s see bubble sort in action.

Consider an unsorted integer array A = [6,5,8,1,2].

Now, we will use the bubble sort algorithm to sort it in ascending order.

Here, the number of elements N = 5, so there will be a total of N-1, i.e., four iterations.

1. First Iteration

Compare A[0] = 6 and A[1] = 5 in [6,5,8,1,2]. Since, 6>5, So we swap them, getting [5,6,8,1,2].

Compare A[1]=6 and A[2]=8 in [5,6,8,1,2]. Since, 6<8, So, no need to swap.

Compare A[2]=8 and A[3]=1 in [5,6,8,1,2]. Since, 8>1, so we need to swap, getting [5,6,1,8,2]

Compare A[3]=8 and A[4]=2 in [5,6,1,8,2]. Since, 8>2, so we get [5,6,1,2,8]

If you observe, you will see that the greatest element(here, 8) has reached the end of the array, which is its correct position in the sorted array. From the next iteration onwards, we will compare the elements only till the second last position, as the last element is already at its correct place.

2. Second Iteration

Compare A[0]=5 and A[1]=6 in [5,6,1,2,8]. Since, 5<6, so, no need to swap; they are in the correct order.

Compare A[1]=6 and A[2]=1 in [5,6,1,2,8]. Since, 6>1, so we swap them, getting [5,1,6,2,8].

Compare A[2]=6 and A[3]=2 in [5,1,6,2,8]. Since, 6>2, so we need to swap, getting [5,1,2,6,8].

Notice that 6 is now in the correct position.

3. Third Iteration

Compare A[0]=5 and A[1]=1 in [5,1,2,6,8]. Since, 5>1, so we swap them, getting [1,5,2,6,8].

Compare A[1]=5 and A[2]=2 in [1,5,2,6,8]. Since 5>2, so we swap them, getting [1,2,5,6,8].

Now, 5 is in its correct place.

4. Fourth Iteration

Compare A[0]=1 and A[1]=2 in [1,2,5,6,8]. Since, 1<2, so there is no need to swap.

The figure below illustrates the steps followed above:

Finally, you can see that the array is sorted.

Implementation of Bubble Sort

In the typical bubble sort algorithm, the outer loop continues to execute even if we don't perform any swap operation in the inner loop. So, essentially, there will be no swapping if the elements are already sorted.

To avoid these unnecessary comparisons, we can keep a flag set to false. If any swap is performed, it is set to true; otherwise, it remains false.

Then at each iteration of the outer loop, we just need to check if the flag is false, we break the loop, or else we continue.

In the next section, we will see the implementation of the bubble sort algorithm along with the space and time complexity.

Implementation in C

C

C

/* C Implementation of Bubble Sort Algorithm */ #include <stdio.h>

/* Function for printing an array of length n */ void printArray(int arr[], int n) { for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); }

void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; }

void bubbleSortAlgorithm(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) swap(&arr[j], &arr[j + 1]); } } }

// Driver code int main() { int arr[] = {6, 5, 8, 1, 2}; int N = sizeof(arr) / sizeof(arr[0]); bubbleSortAlgorithm(arr, N); printf("The array performing the Bubble Sort Algorithm is:\n"); printArray(arr, N); return 0; }

/* C++ Implementation of the Bubble Sort Algorithm */ #include <bits/stdc++.h> using namespace std;

void bubbleSortAlgorithm(int arr[], int n) { int i, j; bool flag; for (i = 0; i < n - 1; i++) { flag = false; for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); flag = true; } }

// If no swapping is performed, then we break the loop if (flag == false) break; } }

// Function for printing an array of length n void printArr(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; }

// Driver Program int main() { int arr[] = {6, 5, 8, 1, 2}; int N = sizeof(arr) / sizeof(arr[0]); bubbleSortAlgorithm(arr, N); cout << "The array performing the Bubble Sort Algorithm is:\n"; printArr(arr, N); return 0; }

Output

The array performing the Bubble Sort Algorithm is:
1 2 5 6 8

Complexity Analysis of Bubble Sort

In this section, we will have a look at the time and space complexities of the bubble sort algorithm.

Time Complexity

Case

Time Complexity

Worst Case

O(n^{2})

Average Case

O(n^{2})

Best Case

O(n)

The time complexity of the bubble sort algorithm is O(n^{2}), where n is the number of elements present in the given array.

You can see that we use two nested loops for sorting. The inner loop can run up to n times, and the outer loop can also run up to n times in the worst case. Hence, the total number of comparisons will be O(n*n); thus, time complexity will be O(n*n) which is O(n^{2}).

The best case occurs when the array is already sorted. So, the best case time complexity is O(n), as we need at least a single pass to know that no swapping has been performed.

The worst case occurs when the array elements are sorted in reverse order, which implies that the algorithm will not finish before O(n^{2}) operations.

Space Complexity

The space complexity of the bubble sort algorithm is O(1).

Since the algorithm uses only a constant amount of space for the loop variables and an extra variable to store the swapping status.

Moreover, bubble sort is an in-place sorting algorithm which implies that it manipulates the original array for sorting.

Applications of Bubble Sort Algorithm

Several applications of Bubble Sort Algorithm are as follows:

Educational Purpose: Bubble Sort is frequently used in computer science classes to teach fundamental sorting algorithms and algorithm analysis.

Small Data Sets: It may be appropriate for sorting small arrays or lists because of its simplicity, which makes it simpler to use and comprehend.

Debugging: Due to its simplicity in implementation and debugging, Bubble Sort can occasionally be used as a stepping stone for troubleshooting more complicated sorting algorithms.

Adaptive Sorting: Bubble Sort is adaptive; it improves in effectiveness when dealing with partially sorted data. It can function reasonably effectively in scenarios when the data is mostly sorted.

Advantages of Bubble Sort Algorithm

Some of the advantages of the bubble sort algorithm are:

It's a very simple algorithm.

Memory efficient.

Detects early when the input is already sorted.

It is very intuitive to understand.

Bubble sort swaps the elements without any extra memory requirements.

Bubble sort code is very small and simple computer program.

Disadvantages of Bubble Sort Algorithm

Some of the disadvantages are:

Time Complexity is high.

It is majorly suitable for academic teaching purposes only.

It does not work well for real-life applications.

Not suitable for larger inputs.

Prims and Kruskal Algorithm

Frequently Asked Questions

What are the 5 steps of bubble sort?

A basic sorting algorithm called Bubble Sort has five steps: comparing nearby entries, swapping them if they are in the wrong order, moving on to the next pair, repeating this process until there are no swaps in a pass, and iterating over all of the elements until the list is sorted.

Why is it called bubble sort algorithm?

Bubble Sort get its name because smaller elements "bubble" to the top of the list during each pass. The smaller values gradually move to the top of the list in each iteration, mimicking bubbles rising to the surface. Adjacent components are compared and swapped if they are out of order.

What is the formula for bubble sort algorithm?

On average, Bubble sort requires n/2 passes and O(n) comparisons for each pass. So, the formula for computing the time complexity of bubble sort is O(n/2*n) = O(n^2), where n is the total number of elements in the list.

Conclusion

In this article, we discussed the bubble sort algorithm from scratch, starting with the introduction followed by the working of the algorithm with the help of an example. We also learned the optimized bubble sort algorithm's implementation and the time and space complexity analysis.

We hope this blog has helped you enhance your knowledge regarding the bubble sort algorithm.