Bubble Sort in Java

Background

 In bubble sort the largest elements goes to the end of the array and the remaining array (0 - array.length-i) is sorted again. It's like a bubble where on each iteration largest element goes to the end.

Code : 

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/2/14
 * Time: 8:29 PM
 */
public class BubbleSort {

    public void sort(int[] array) {

        int arrayLength = array.length;
        for(int i=0;i<arrayLength;i++){
            for( int j=0;j<arrayLength-i-1;j++){
                if(array[j] > array[j+1]){
                    Swapper.inMemorySwap(array,j,j+1);
                }
            }
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new BubbleSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));

    }

}

Complexity

Bubble sort has worst-case and average complexity both O(n2), where n is the number of items being sorted.

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]

 As we know that bubble sort runs in O(N^2) time complexity. If this question is asked(mostly in the 1st round to make sure you know basic sorting algorithms)  then it will mostly be followed by a counter question. How can you optimize bubble sort ?

Bubble Sort Optimization

If you notice we iterate over all the indexes and for each outer iteration we bubble out the largest number to the end. Now if at some index the array is completely sorted we need to proceed iterating on further indexes. That is precisely what we are going to do. Keep a boolean flag denoting if array is completely sorted or not. At the outer loop initialize it to true and make it false if any iteration of inner for loop happens denoting array is not completely sorted yet. When inner loop does not execute it means array is completely sorted and there is no need to proceed. In this case flag will be true which we initialized in outer loop. If such condition happens i.e if flag is true than break from the loops and print the sorted array.

Code :

package Sorts;

import java.util.Arrays;

/**
 * Created by Aniket on 2/19/14.
 */
public class BubbleSort {

    public void sort(int[] array) {

        int arrayLength = array.length;
        for(int i=0;i<arrayLength;i++){
            boolean isSorted = true;
            for( int j=0;j<arrayLength-i-1;j++){
                if(array[j] > array[j+1]){
                    isSorted = false;
                    Swapper.inMemorySwap(array,j,j+1);
                }
            }
            if(isSorted){
                System.out.println("Breaking at index : " + i);
                break;
            }
        }
    }

    public static void main(String args[]){
        int[] array = new int[]{2,7,5,9,4,7,1,0,1,2,3,};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new BubbleSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));
    }


}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0, 1, 2, 3]
Breaking at index : 7
Array after Sort : [0, 1, 1, 2, 2, 3, 4, 5, 7, 7, 9]


NOTE :  Swapper.inMemorySwap in a normal swap function where data at two indexes are swapper. You can choose to use a temporary variable or not (see swapping of variables in related links section).

Sample method could be -

    public void swap(int[] array, int x, int y) {
         array[x] = array[x] + array[y];
        array[y] = array[x] - array[y];
        array[x] = array[x] - array[y];
    }

Related Links

• Swapping two numbers without using temporary variable
• Bubble Sort(Wiki)