# Bubble Sort

Harshit Jindal Feb 21, 2021 Jan 28, 2021

Bubble sort is a simple sorting algorithm. It works by repeated comparison of adjacent elements and swapping them if they are in the wrong order. The repeated comparisons bubble up the smallest/largest element towards the end of the array, and hence this algorithm is named bubble sort. Although inefficient, it still represents the foundation for sorting algorithms.

## Bubble Sort Algorithm

Let us assume that we have an unsorted array `A[]` containing n elements.

• ##### Repeat the above steps `(n-2)` times for the remaining iterations. Reduce the array size by one each time as the last element is already sorted. The smallest/largest element in this iteration moves to the rightmost position.

Step 1 in the above algorithm is also called a pass. To sort an array of size n, `n-1` passes are required.

## Bubble Sort Algorithm Example

Suppose we have the array: `(5,3,4,2,1)`. We will sort it using the bubble sort algorithm.

• First Pass:
(5 3 4 2 1) (3 5 4 2 1) (3 < 5 swapped)
(3 5 4 2 1) (3 4 5 2 1) (4 < 5 swapped)
(3 4 5 2 1) (3 4 2 5 1) (2 < 5 swapped)
(3 4 2 5 1) (3 4 2 1 5) (1 < 5 swapped)
• Second Pass:
(3 4 2 1 5) (3 4 2 1 5)
(3 4 2 1 5) (3 2 4 1 5) (2 < 4 swapped)
(3 2 4 1 5) (3 2 1 4 5) (1 < 4 swapped)
• Third Pass:
(3 2 1 4 5) (2 3 1 4 5) (2 < 3 swapped)
(2 3 1 4 5) (2 1 3 4 5) (1 < 3 swapped)
• Fourth Pass:
(2 1 3 4 5) (1 2 3 4 5) (1 < 2 swapped)

We get the sorted array after the fourth pass - `(1 2 3 4 5)`

## Bubble Sort Algorithm Implementation

``````#include<iostream>

using namespace std;
void bubble_sort(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]);
}
}
}
}
int main() {

int n = 5;
int arr = {5, 3, 4, 2, 1};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bubble_sort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
``````

## Bubble Sort Algorithm Complexity

### Time Complexity

• Average Case

On average, `n-i` comparisons are made in the `ith` pass of bubble sort. So if there are n passes, then the average time complexity can be given by

``````(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2
``````

Hence the time complexity is of the order of O(n2).

• Worst Case

The worst case occurs when the array is reversely sorted, and the maximum number of comparisons and swapping has to be performed.

The worst case time complexity is O(n2).

• Best Case

The best-case occurs when the array is already sorted, and then only N comparisons are required.

The best-case time complexity is `O(n)`.

### Space Complexity

Space Complexity for this algorithm is `O(n)` because no extra memory other than a temporary variable is required.