In this tutorial, we will learn that what is bubble sort in java and how it works. Letβs start

A sorting algorithm can be defined as an algorithm or a procedure to put elements of a collection in a specific order. For instance, if you have a numeric collection like an ArrayList of integers, then you might want to arrange the elements of ArrayList in ascending or descending order.

Similarly, you might want to arrange strings of a string collection in alphabetical or lexicographical order. This is where the sorting algorithms in Java come into the picture.

Bubble sort is the simplest of all sorting techniques in Java. This technique sorts the collection by repeatedly comparing two adjacent elements and swapping them if they are not in the desired order. Thus, at the end of the iteration, the heaviest element gets bubbled up to claim its rightful position.

If there are n elements in list A given by A[0],A[1],A[2],A[3],β¦.A[n-1], then A[0] is compared to A[1], A[1] is compared to A[2] and so on. After comparing if the first element is greater than the second, then the two elements are swapped if they are not in order.

There are many algorithms in java which perform this rearrangement such as java bubble sort, bucket sort, merge sort, radix sort, insertion sort, selection sort, heap sort, quick sort, counting sort, comb sort etc. Java Bubble sorting is one of the simplest sorting algorithms amongst all these. We will traverse the array from the first elements to the last element In this algorithm. we will put the current element in comparison with the next element and swap both if the current one is greater than the next element.

#### Here is a step wise process of how bubble sort is performed; say we have to sort the list in ascending order

**Step 1: **we take a list of unsorted elements or an array

For example the list is: 16, 43, 22,78

**Step 2: **bubble sort takes the first 2 elements **16, 43** and will check for the bigger elements. In this case, 43 is the bigger one and they are already in the sorted locations so the pointer will move forward.

**Step 3: **now we compare 43 and 22 where 22 is smaller than 43 so the positions will be swapped. Now the list becomes 16, 22, 43, 78

**Step 4: **As we compare 43 and 78 now, it is again in the sorted fashion and doesnβt require to be swapped.

**Step 5: **As a result, we get out final list of sorted elements: 16, 22, 43,78

### Algorithm for Bubble Sort

```
Step 1: For i = 0 to N-1 repeat Step 2
Step 2: For J = i + 1 to N β I repeat
Step 3: if A[J] > A[i]
Swap A[J] and A[i]
[End of Inner for loop]
[End if Outer for loop]
Step 4: Exit
```

### Bubble Sort Pseudocode

Bubble sort is a simple algorithm β the pseudocode for it is also pretty simple and short.

Have a look and use it to write your code in a programming language of your choice.

```
bubbleSort(array, size)
for i β 0 to size - 2
for j β 0 to size - 2 - i
If array[j] and array[j + 1] are not in the correct order
Swap array[j] with array[j + 1]
```

### Bubble Sort Program code

```
class DeveloperHelps
{
void bubbleSort(int arr[])
{
int x = arr.length;
for (int i = 0; i < x-1; i++)
for (int j = 0; j < x-i-1; j++)
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
void printArray(int arr[])
{
int x = arr.length;
for (int i=0; i<x; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[])
{
DeveloperHelps obj = new DeveloperHelps();
int arr[] = {100, 300, 200, 500, 220, 601, 90};
obj.bubbleSort(arr);
System.out.println("The sorted array via bubble sort algorithm is");
obj.printArray(arr);
}
}
```

### Output :

```
The sorted array via bubble sort algorithm is
90, 100, 200, 220, 300, 500, 601
```

## Complexities of Bubble Sort

In bubble sort, we compare each adjacent pair. If they are not in the correct order, we swap them. We keep repeating the previous step until no swaps are needed, which indicates all the elements are sorted.

### Time Complexity

- Worse case: O(n2)

When the array is reverse-sorted, we iterate through the array (n – 1) times. In the first iteration, we do (n – 1) swaps, (n – 2) in the second, and so on until in the last iteration where we do only one swap. Thus the total number of swaps sum up to n * (n – 1) / 2.

- Average case: O(n2)

For a completely random array, the total number of swaps averages out to be around n2 / 4, which is again O(n2).

- Best case: O(n)

In the first iteration of the array, if we do not perform any swap, we know that the array is already sorted so stop sorting, therefore the time complexity turns out to be linear

### Space complexity

Since we use only a constant amount of additional memory apart from the input array, the space complexity is O(1).

### Advantages of Bubble Sort

- Is simple to write and easy to understand
- Takes a few lines of code
- Sorts data in place; requires very little additional memory

### Disadvantages of Bubble Sort

- Average time increases quadratically with the number of elements
- Not suitable for a large amount of data

*Thanks for the reading post. I hope you like and understand the post. If you have any doubt regarding this post please comment below.*