Bubble Sort

Why it is called bubble sort ?

Bubble Sort is nothing but a comparison algorithm where -

• At the end of first iteration, largest element in the array get placed at last index
• At the end of second iteration, second largest element in the array get placed at second last index and so on…

This way large elements are moving towards the last indexes and hence small elements are moving towards the starting indexes which is also termed as smaller elements “bubble” to the top of the list that is why it is called bubble sort.

Step-by-step example

Let us take the array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

First Pass:

( 5 1 4 2 8 ) —— ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) —— ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) —— ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) —— ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

( 1 4 2 5 8 ) —— ( 1 4 2 5 8 )

( 1 4 2 5 8 ) —— ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

package com.abc;

public class BubbleSort {

    public static void main(String[] args){
        int[] array = new int[]{5, 1, 12, -5, 16};
        BubbleSort.sort(array);
    }
    
    private static void sort(int[] array){
        int count = 0;
        for(int i = array.length ; i > 0 ; i --, count++){
            for(int j = 0 ; j < array.length-1 ; j++, count++){
                if(array[j] > array[j+1]){
                    swapNumbers(j, j+1, array);
                }
            }
        }
        printNumbers(array, count);
    }
    
    private static void swapNumbers(int i, int j, int[] array) {
        int temp;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    private static void printNumbers(int[] array, int count) {
        System.out.print("Sorted Array : {");
        for(int i : array){
            System.out.print(i + " ");
        }
        System.out.print("}, n : " + array.length + ", comparisons : " + count);
    }
}

Output
Sorted Array : {-5 1 5 12 16 }, n : 5, comparisons : 25

Time Complexity for worst case is O(n²). Algorithm can be further improved :

private static void sort(int[] array){
    int count = 0;
    for(int i = array.length ; i > 0 ; i --, count++){
        for(int j = 0 ; j < i-1 ; j++, count++){
            if(array[j] > array[j+1]){
                swapNumbers(j, j+1, array);
            }
        }
    }
    printNumbers(array, count);
}

Output
Sorted Array : {-5 1 5 12 16 }, n : 5, comparisons : 15