The most basic and easy to implement sorting technique is **Bubble Sort**. It works by simply comparing each and every element and gets its name from the way in which the **smaller elements bubble to the starting of the array.**

Every possible pair is compared and swapping is performed if required, that is, if there are ‘n’ elements then n*n comparisons will be done, though it’s time-consuming, it places elements in their correct indexes in the end.

- Read input from user
- for i = 0 to length of Array
- for j = 0 to length of Array - 1
- if
**Array[j]**is greater than**Array[j+1]** - then,
**Swap**vaules at**Array[j]**and**Array[j+1]**

- if
- End inner for loop

- for j = 0 to length of Array - 1
- End outer for loop

Consider an Array : `5 3 4 1 2`

Length of Array = `5`

There will be 5 iterations of the outer loop

```
j = 0
5 will be compared with 3
Since 5 > 3
Swapping will be done
```

Array after swapping will look like:

```
j = 1
Now 5 will be compared with 4
Since 5 > 4
Swapping will be done
```

Array after swapping:

```
j = 2
5 will be compared with 1
Since 5 > 1
Swapping will be done
```

Array after swapping:

```
j = 3
5 will be compared with 2
Since 5 > 1
Swapping will be done
```

Array after swapping:

```
j = 0
3 will be compared 4
Since 3 < 4
Nothing will be done
j = 1
4 will be compared with 1
Since 4 > 1
Swapping will be done
```

Array after swapping:

```
j = 2
4 will be compared with 2
Since 4 > 2
Swapping will be done
```

Array after swapping:

```
j = 3
4 will be compared with 5
Since 4 < 5
Nothing will be done
```

```
j = 0
3 will be compared with 1
Since 3 > 1
Swapping will be done
```

Array after swapping:

```
j = 1
3 will be compared with 2
Since 3 > 2
Swapping will be done
```

Array after swapping:

Now we can see that Array is sorted, although more comparisons will be done, no swapping will be done hereafter.

Let’s look at the Java code for the same.

```
import java.util.Arrays;
public class Sorting {
void bubbleSort(int arr[]) {
int lengthOfArray = arr.length;
int temp; // Temporary variable for swapping
for (int i = 0; i < lengthOfArray; i++) {
for (int j = 0; j < lengthOfArray - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String[] args) {
Sorting sort = new Sorting(); // creating object of class Sorting
int[] arr = { 5, 2, 6, 1, 3 };
sort.bubbleSort(arr); // method call
System.out.println("Array after applying bubble sort : " + Arrays.toString(arr));
}
}
```

Case | Runtime |
---|---|

Best | O(n^2) |

Average | O(n^2) |

Worst | O(n^2) |

Space complexity | O(1) |

**Bubble sort** might be very easy to implement but it has a complexity of n^2 in all three cases.

We can **improve the best case** of bubble sort to **O(n)** by using a **flag** which will indicate if the array is already sorted or not.

Help us improve this content by editing this page on GitHub