Bubble sort in java

Let’s learn bubble sort in java.

Bubble sort in java

Bubble sort is a comparison based sorting algorithm, that is, each pair is compared with adjacent elements and swapped till right order.

And while traversing, current element is compared with adjacent element and if current element is greater than the adjacent element, it is swapped.

Now let’s understand bubble sort algorithm with explanation.

Here we have an array of integers by name “Number”. In this array there are six elements with index starting from 0 to 5.

Now to sort above array we need to rearrange the elements in increasing order. To do that we are going to scan the array from left to right.

While scanning above array we will compare each element at particular position with the adjacent element. So, first at 0th index position compare with the element at 1st index position.

If the element at the current position is greater than the element at the next position, swap those two elements.

In our case, 20 is not greater than 70, so, we will not swap those two elements. We will move to next index position 1.

In this case 70 is greater than 40, so, we will swap the position of these two elements. So, 70 will move to index 2 and 40 will move to index 1.

Now we will move to index 2. The number at index 2 at this stage will be 70. Again we compare with the next element, i.e., 10. Now 70 is greater than 10, so we will swap. Next moving on to index 3.

At this stage number at index 3 is 70. Now compare it with 50. Here 70 is greater than 50 we need to swap again.

So, 70 will go to index 4 and 50 will move to index 3 and now we will go to index 4.

As you can see, this whole process is pushing number 70 which is the largest number in the array towards higher index position at each step.

At index position 4, once again element 70 is greater than 30, so we will swap.

At this stage we are done with one pass on the array and what has happened after this one pass is that 70 which is the largest number in the array is at its appropriate position.

So, 70 has kind of bubbled up to the right most position in the array. We are done with first pass. Next second pass, third pass and so on… till elements in array are sorted in ascending order.

Here’s the whole swapping of adjacent elements.

First pass

(20) 70 40 10 50 30 - 20>70? no, don't swap
20 (70) 40 10 50 30 - 70>40? yes, swap.
20 40 (70) 10 50 30 - 70>10? yes, swap.
20 40 10 (70) 50 30 - 70>50? yes, swap.
20 40 10 50 (70) 30 - 70>30? yes, swap.
20 40 10 50 30 (70)

Second pass

(20) 40 10 50 30 70 - 20>40? no, don't swap
20 (40) 10 50 30 70 - 40>10? yes, swap
20 10 (40) 50 30 70 - 40>50? no, don't swap
20 10 40 (50) 30 70 - 50>30? yes, swap
20 10 40 30 (50) 70 - 50>70? no, don't swap

Third pass

(20) 10 40 30 50 70 - 20>10? yes, swap
10 (20) 40 30 50 70 - 20>40? no, don't swap
10 20 (40) 30 50 70 - 40>30? yes, swap
10 20 30 (40) 50 70 - 40>50? no, don't swap
10 20 30 40 (50) 70 - 50>70? no, don't swap
10 20 30 40 50 70 -   sorted array

Final sorted array will be like this.

Here’s bubble sort program in java.

Java program

class DemoBubbleSort 
{
    public static void main(String[] args) 
    {
        int temp;
        int[] arrSort = {65, 35, 25, 15, 23, 14, 95};
        for (int i = 0; i < arrSort.length; i++) 
        {
            for (int j = 0; j < arrSort.length - 1; j++) 
            { 
                if (arrSort[j] > arrSort[j + 1]) 
                {
                    temp = arrSort[j];
                    arrSort[j] = arrSort[j + 1];
                    arrSort[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < arrSort.length; i++)
        {
            System.out.println(arrSort[i] + " ");
        }
    }
}

Output:

14 15 23 25 35 65 95

Bubble sort time complexity

Best case time: O(n) when array is sorted.

Worst and average time: O(n * n) when array is in reverse order.

Auxiliary space: O(1)