## Friday, November 13, 2020

### Bubble Sort Program in Java

In this post we’ll see how to write Bubble sort program in Java. Out of the three simpler sorting algorithms Bubble sort, Insertion sort and Selection sort, Bubble sort is considered the simplest sorting algorithm and the slowest too because of a proportionally large number of swaps along with the comparisons.

### How Bubble sort works

In bubble sort you start by comparing the first two elements (index 0 and index 1). If element at index 0 is greater than the element at index 1 then those two elements are swapped, if it is not then you do nothing. Then the next 2 elements are compared (index 1 and index 2) and elements are swapped based on the same logic.

So the steps for bubble sort are as follows-

2. If element at the left is greater than the element at the right then swap the elements.
3. Move one position right.

You continue doing that until you reach the last element, by then you have the greatest element at the right. Since the biggest elements bubble up to the top end thus the name “Bubble sort”.

This is the first pass, in the next iteration again you start from the two leftmost elements and compare the elements and swap if required. Since the rightmost element is already in its sorted position so this iteration runs till (N-1) elements.

For example if you have an array [5, 2, 6, 1] then in the first iteration-

1. Initially 5 is compared with 2, since 5 (element at left) is greater than 2 (element at right), elements are swapped making the array [2, 5, 6, 1].
2. Move over one position and compare 5 and 6, since 5 is not greater than 6 so nothing is done and array remains [2, 5, 6, 1].
3. Again move over one position and compare 6 and 1, since 6 is greater than 1 elements are swapped giving us the array as [2, 5, 1, 6].

In the next iteration last element is not included in the comparison as it is already at its final position.

### Bubble Sort Java program

```public class BubbleSort {

public static void main(String[] args) {
int[] intArr = {47, 85, 62, 34, 7, 10, 92, 106, 2, 54};
int[] sortedArray = bubbleSort(intArr);
System.out.println("Sorted array is- ");
for(int num : sortedArray){
System.out.print(num + " ");
}
}

private static int[] bubbleSort(int[] intArr){
// right to left
for(int i = intArr.length; i > 1; i--){
for(int j = 0; j < i - 1; j++){
//if greater swap elements
if(intArr[j] > intArr[j+1]){
swapElements(j, intArr);
}
}
}
return intArr;
}

private static void swapElements(int index, int[] intArr){
int temp = intArr[index];
intArr[index] = intArr[index+1];
intArr[index+1] = temp;
}
}
```

Output

```Sorted array is-
2 7 10 34 47 54 62 85 92 106
```

### Time and Space complexity of Bubble sort

For bubble sort there are two loops that go through the elements that makes it a complexity of N*N i.e. O(N2). In bubble sort the number of swaps is also high which makes it slow.

Bubble sort is an in place sorting algorithm so there is no auxiliary space requirement. Thus the space complexity of Bubble sort is O(1).

That's all for this topic Bubble Sort Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!