Bubble sort is a sorting algorithm used in programming. Bubble sort compares the adjacent elements and swaps their positions if they are not in the expected order. The order can be ascending or descending.

**Working of Bubble Sort**

Bubble sort compares each element with the element next to it and if they are not in the required order they are swapped. This goes on till we reach the last element of the array. At the end of loop one, the last element of the array is placed at the correct position. It is taken care of by the inner loop. Each time the inner loop ends, it is called the completion of a **Pass**. For the completion of the bubble sort algorithm, there are n-1 passes, where n is the number of elements in the array. The outer loop moves through each pass.

**Let us consider an example.**

Consider an unsorted array of 5 elements.

The elements are:

28,6,4,2,24

For the given array, there will be four passes in bubble sort.

- For the first pass, we start with the element at the 0
^{th}index of the array. Thus, we compare 28 and 6, and since 28>6, we swap their positions. - Next, we compare 28 and 4 and swap them too.
- The next comparison is between 28 and 2, and their positions are also swapped.
- As there are five elements in the array, the fourth step is the last step of pass 1, and we swap 28 and 24 also.

Thus, we see, at the end of pass one, the largest element of the array has reached the last index.

Similarly, three other passes are run, and they are represented below with the help of a figure.

Thus, after the end of all the passes, the sorted array is

2,4,6,24,28

**Algorithm:**

The algorithm starts at index 0 of the array and runs n-1 times till the entire array is in sorted order. The array can be sorted in either ascending or descending order.

- Start at index zero, compare the element with the next one (arr[0] & arr[1], and swap if arr[0] > arr[1]. Now compare arr[1] & arr[2] and swap if arr[1] > arr[2]. Repeat this process until the end of the array. After doing this, the largest element is present at the end. This whole thing is known as a pass. In the first pass, we process array elements from [0, n-1].
- Repeat step one but process array elements [0, n-2] because the last one, i.e., arr[n-1], is present at its correct position. After this step, the largest two elements are present at the end.
- Repeat this process n-1 times.

bubbleSort(array) for i <- 1 to indexOfLastUnsortedElement-1 if leftElement > rightElement swap leftElement and rightElement end bubbleSort

**Code in C:**

#include <stdio.h> void bubbleSort(int array[], int size) { // run two loops: one for passes // second for comparison of each element for (int i = 0; i < size – 1; i++) { for (int j = 0; j < size – i – 1; j++) { // To sort in descending order, change”>” to “<“. if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf(“%d “, array[i]); } printf(“\n”); } int main() { int arr[] = {38,27,43,3,9,82}; int size = sizeof(arr) / sizeof(arr[0]); printf(“Original array: “); printArray(arr, size); bubbleSort(arr, size); printf(“Sorted array: “); printArray(arr, size); }

**Output:**

**
**

**Optimization of bubble sort**

The algorithm above is not very efficient since its time complexity is O(n^{2}). The number of swaps is very high, and even when the elements at the end are sorted, they are still compared, which increases the execution time of the code. Thus, there is a technique used to optimize the bubble sort algorithm. An extra variable is introduced and it checks if there is no swapping taking place then, there is no need for performing further loops. Thus, we can prevent further iterations.

**The algorithm for optimized bubble sort is**

bubbleSort(array) flag <- false for i <- 1 to indexOfLastUnsortedElement-1 if leftElement > rightElement swap leftElement and rightElement flag <- true end bubbleSort

Thus, the flag variable reduces the extra number of loops that would otherwise have run. This code is also referred to as flagged bubble sort or optimized bubble sort using flag.

**Optimized code for bubble sort**

#include <stdio.h> void bubbleSort(int array[], int size) { for (int i = 0; i < size - 1; i++) { // Swapped keeps track of swapping int flag = 0; for (int j = 0; j < size - i - 1; j++) { // To sort in descending order, change > to < in this line. if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; flag = 1; } } // If there is not swapping in the last swap, then the array is already sorted. if (flag == 0) break; } } void printArray(int array[], int size) { for (int i = 0; i < size; ++i) { printf("%d ", array[i]); } printf("\n"); } int main() { int arr[] = {38,27,43,3,9,82}; int size = sizeof(arr) / sizeof(arr[0]); printf("Original array: "); printArray(arr, size); bubbleSort(arr, size); printf("Sorted array: "); printArray(arr, size); }

**Bubble sort complexity**

**Time Complexities:**

**Worst Case Complexity: O(n**^{2})

If the array is in descending order and we wish to sort it in ascending order, the worst case occurs.

**Average Case Complexity: O(n**^{2})

When an unsorted array is given and the elements are randomly organized. The time complexity is O(n^{2}) because two loops are run.

**Best Case Complexity: O(n)**

When the array is already sorted, the loop is run only one time and the flag will avoid any more loops from running.

**Space Complexity:**

- Space complexity is O (1) because an extra variable is used for swapping. In the optimized algorithm, there is a new variable
**‘flag’**introduced which makes the space complexity O (2).