# Bubble Sort and Optimized Bubble Sort- Java Implementation

In this article we will discuss about what is bubble sort, why it is considered as one of the simplest sorting algorithm, what its complexity, how we can improve the bubble sort algorithm.

What is bubble sort??

• Bubble sort is one of the simplest sorting algorithms.
• Bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order.
• The pass through the list is repeated until no swaps are needed, that means array is sorted.
• As the name indicates, the lighter elements (smaller) ‘bubble up’ to the top.
• Bubble sort is also known as sinking sort (heavy or bigger elements settles down at the bottom of the list after each iteration).

Time Complexity: O(N2)

Let’s walk through on example:

• Pros: Bubble sort algorithm is considered as very simple sorting technique since all you need to do is compare all the adjacent elements and swap them if they are in wrong order.
• Cons: Main drawback of bubble sort is its time complexity which is O(N2) since all the pairs are compared, even when the original array is sorted.

Java Code for Bubble Sort:

 import java.util.Arrays; public class BubbleSort { static void sort(int [] arrA){ if(arrA==null || arrA.length==0) return; System.out.println("Original Array: " + Arrays.toString(arrA)); int size = arrA.length; for (int i = 0; i arrA[j+1]){ //swap the elements int temp = arrA[j]; arrA[j] = arrA[j+1]; arrA[j+1] = temp; } } } System.out.println("Sorted Array: " + Arrays.toString(arrA)); } public static void main(String[] args) { int [] arrA = {5, 1, 9, 3, 2, 10}; sort(arrA); } }

view raw
BubbleSort.java
hosted with ❤ by GitHub

Output:

```Original Array: [5, 1, 9, 3, 2, 10]
Sorted Array: [1, 2, 3, 5, 9, 10]
```

How we can improve Bubble sort:

• As see in the program above, bubble sort compares all the pairs in the array, even when original array is sorted or partially sorted. This is where we can do some improvements.
• During any iteration, if there are no swaps then we can claim that our array is already sorted.

Java code for Optimized Bubble Sort:

 import java.util.Arrays; public class OptimizedBubbleSort { static void sort(int [] arrA){ if(arrA==null || arrA.length==0) return; System.out.println("Original Array: " + Arrays.toString(arrA)); boolean isSwapped; int size = arrA.length; for (int i = 0; i arrA[j+1]){ //swap the elements int temp = arrA[j]; arrA[j] = arrA[j+1]; arrA[j+1] = temp; isSwapped = true; } } //check if any swapping occurred in last iteration //if yes then break the loop, array is sorted at this point if(isSwapped==false) break; } System.out.println("Sorted Array: " + Arrays.toString(arrA)); } public static void main(String[] args) { int [] arrA = {5, 1, 9, 3, 2, 10}; sort(arrA); System.out.println("——————————"); arrA = new int []{1, 2, 4, 6, 8, 10}; sort(arrA); } }

Output:

```Original Array: [5, 1, 9, 3, 2, 10]
Sorted Array: [1, 2, 3, 5, 9, 10]
------------------------------
Original Array: [1, 2, 4, 6, 8, 10]
Sorted Array: [1, 2, 4, 6, 8, 10]
```

Reference: Wiki