Bubble Sort

Intro

Bubble sort - one of the slowest sorting algorithms. But let's see why.

It has a time complexity of O(n^2) (n squared). Why?
Because to implement it, we need to use a nested loop. It means we will have a loop inside another loop. That's because, in bubble sort, we need to compare one element with every (almost every) other element and swap them if necessary.

Bubble sort - how does it work?

Using this sorting algorithm, we start by picking the first element in the array, and then we start comparing it with every other element on its right, and we check if the current element is greater than the element we are comparing it to. If yes, we swap them. If no, we stop comparing that element, and pick the next element - the element that we determined is greater than the previous element, and start comparing it to the other elements on the right.

With this approach, after every iteration, we will move the largest element we have found to the right - to the end of the array. 

In the next iteration, we will move the largest element we have found (which is now the second largest) to the n - 2, to be next to the previous element that we put at the end. And so on...

Let's code it

Below is the Java code of the Bubble sort

public class BubbleSort {

public void sort(int[] arr) { // O(n^2)

for (int i = 0; i < arr.length; i++) {
boolean swapped = false; // in case the array is sorted, it will remain false
for (int j = 0; j < arr.length - i -1; j++) {
if(arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}

if(!swapped) { // if swapped == false - it means, the array is already sorted
break;
}
}
}
}

In the nested loop, we are not iterating until we hit the arr.length - 1,  we added also the -i part, because we know that we have already put some elements at the end, so we don't need to go through them again.

Note: When we know that we need to compare each element with every other element, we always need to use the nested loops.

Bubble sort - analysis

With this algorithm, both the average and worst time complexity is O(n^2). But the best time complexity can be O(n).

Worst case O(n^2) - when the input array is sorted in reverse order. That means we would need to swap every element with all other elements to get it to the end of the array because the largest element is now at the beginning of the array.

Average time O(n^2) - when the array is not sorted, or partially sorted.

Best time O(n) - when the array is already sorted (ASC) - that means after the first iteration - we stop with traversing because the value of the swapped will remain false, and we don't want to continue with iteration since we know we got an array that is already sorted.

Space complexity is always O(1) - because we are not creating any data structure, hence no additional memory will be taken.