# Bubble Sort

Bubble sort is a sorting algorithm which repeatedly loops through the list to be sorted, and compares each pair of adjacent items and swaps them if they are in the wrong order. This happens until everything is in the right order. This is very simple, but would be very bad on big arrays / lists.

How I implemented this in Java is by having a loop that loops through the array:

public int[] bubbleSort(int[] array) {

if (array.length < 1) return array;

for (int i = 0; i < array.length; i++) {

}

return array;

}

Then implementing another loop that is nested in the first loop which is forwarded by 1 (so we can compare that number to the other number):

public int[] bubbleSort(int[] array) {

if (array.length < 1) return array;

for (int i = 0; i < array.length; i++) {

for (int j = 1; j < (array.length - i); j++) {

}

}

return array;

}

Now we have two numbers to compare to each other, so lets create a variable where we can store temporary numbers:

public int[] bubbleSort(int[] array) {

if (array.length < 1) return array;

int temp;

for (int i = 0; i < array.length; i++) {

for (int j = 1; j < (array.length - i); j++) {

}

}

return array;

}

Now lets check if j is smaller then whats to the left of it (look at the gif above if this does not make sense):

public int[] bubbleSort(int[] array) {

if (array.length < 1) return array;

int temp;

for (int i = 0; i < array.length; i++) {

for (int j = 1; j < (array.length - i); j++) {

if (array[j - 1] > array[j]) {

}

}

}

return array;

}

If it is smaller then we must swap them:

public int[] bubbleSort(int[] array) {

if (array.length < 1) return array;

int temp;

for (int i = 0; i < array.length; i++) {

for (int j = 1; j < (array.length - i); j++) {

if (array[j - 1] > array[j]) {

temp = array[j - 1];

array[j - 1] = array[j];

array[j] = temp;

}

}

}

return array;

}

The O notation for this algorithms worst case is the same as insertion and selection sort, 0(n²). This is very slow and what makes these algorithms not good for large arrays. But in its best case it can be 0(n) which is not amazing but it is defiantly faster then o(n²). This algorithms space complexity (memory usage) is good, it is 0(1) which means the algorithm is constant.