Bubble Sort

By | August 11, 2017

Bubble Sort is the simplest of all sorting algorithms. It is based on the idea of repeatedly comparing pairs of adjacent (next to each other) elements and then swapping their positions if they exist in the wrong order.

In simpler terms, in bubble sort algorithm, we traverse from first to last element. Current element is being compared with its next element, and if the element is greater than next, we swap it. Considering that we are sorting array in ascending order.

At the end of one full iteration, we can see that we have positioned maximum array element in the very end of the array.

We repeat the full iteration again, ( 1 less iteration each time, since we have already made max element to go at last in our first iteration).

These iterations are repeated n-1 times. And finally the array is sorted.

Eplaination with Example:

Let us say, we want to sort array in ascending order

Array :  [ 7 2 4 3 1 9 ]

First Iteration:
7 2 4 3 1 9 –> 2 7 4 3 1 9  |  First index is chosen and is being compared with second, and finally swapper since 7>2.
2 7 4 3 1 9 –> 2 4 7 3 1 9  | we are swapping 7 with 4 since 7>4
2 4 7 3 1 9 –> 2 4 3 7 1 9  | since, 7>3 , hence swapped.
2 4 3 7 1 9 –> 2 4 3 1 7 9  | since, 7>1, hence swapped.
2 4 3 1 7 9 –> 2 4 3 1 7 9  | no action, since elements involved are in order.

Second Iteration:
2 4 3 1 7 9 –> 2 4 3 1 7 9  | no action.
2 4 3 1 7 9 –> 2 3 4 1 7 9  | 3 <–> 4  (swapped.)
2 3 4 1 7 9 –> 2 3 1 4 7 9  | 4 <–> 1
2 3 1 4 7 9 –> 2 3 1 4 7 9  | no action
2 3 1 4 7 9 –> 2 3 1 4 7 9  | no action

Third Iteration:
2 3 1 4 7 9 –> 2 3 1 4 7 9  | no action.
2 3 1 4 7 9 –> 2 1 3 4 7 9  | 1 <–> 3
2 1 3 4 7 9 –> 2 1 3 4 7 9   | no action
2 1 3 4 7 9 –> 2 1 3 4 7 9  | no action
2 1 3 4 7 9 –> 2 1 3 4 7 9  | no action

Forth Iteration:
2 1 3 4 7 9 –> 1 2 3 4 7 9  | 2 <–> 1
1 2 3 4 7 9 –> 1 2 3 4 7 9  | no action
1 2 3 4 7 9 –> 1 2 3 4 7 9  | no action
1 2 3 4 7 9 –> 1 2 3 4 7 9  | no action
1 2 3 4 7 9 –> 1 2 3 4 7 9  | no action

Fifth Iteration:

Fifth Iteration will have no swaps, since all were sorted in Forth iteration itself. It will be just element checking.

Notice that after each iteration, at least one value moves at the end. So, if first time we are making n comparisons, next time we need to make 1 less comparison.

Bubble Sort has a complexity of Ο(n2).

public class p2 {
    public static void main(String[] args) {
        p2 ob = new p2();
        int arr[] = {1, 21, 4, 5, 23,234,54,0};
        ob.bubble(arr);
        System.out.println("Sorted");
        ob.printarray(arr);
    }

    private void bubble(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n-1 ; i++)
            for (int j = 0; j < n - i- 1; j++) { // (n-i-1) is for ignoring comparisons of elements which have already // been compared in earlier iterations if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
           }
    }
     private void printarray(int arr[]) {
        for (int anArr : arr) {
            System.out.print(anArr + ", ");
        }
    }
}

Output
bubble sort