Sunday, 1 March 2015

Bubble Sort in java

Bubble sort is a comparison sort in which each element is compared with its adjacent element and swapped if they are in wrong order.
While iterating through the  array if there are no swaps then we can stop the loop, since no swap will mean array is sorted.
Following program implements Bubble sort in java.

/**
 * @author vikky.agrawal
 *
 */
public class BubbleSort {
    
    int[] arr;

    BubbleSort() {
        arr = new int[] { 5, 3, 1, 2, 9, 8 };
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        
        BubbleSort obj = new BubbleSort();
        obj.operate();
        
    }
    
    public void operate(){
        System.out.println("Array before sorting : ");
        printArray();
        
        bubbleSort(arr);
        
        System.out.println("Sorted array : ");
        printArray();
    }
 
    /**
     * stable sort
     * O(n^2)
     */
    
    public void bubbleSort(int[] arr){
        
        int length=arr.length;
        for(int i=0; i < length; i++){
          boolean swap=false;
            for(int j=(length-1); j&gt;i;j-- ){
                if(arr[j] < arr[j-1]){
                    int temp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                    swap=true;
                }
            }
            if(!swap){
                //If there is not even a single swap then break the loop;
                //Since each element is being compared and if no swapping then it means, array is sorted now.
                break;
            }            
        }
        
    }
    
    public void printArray(){
        for (int a : arr) {
            System.out.print(a + "");
        }
        System.out.println();
    }
}

Complexity analysis:
Complexity of Bubble sort is O(n^2), since array is iterated and for each iteration elements compared with adjacent elements.
For the first element n-1 element compared,for second n-2 elements compared and so on.
So total time taken : (n-1)+(n-2)+(n-3)+.....1 = O(n^2)(worst case)

In case array already sorted then loop only iterates once,
hence taking total time =O(n) (Best case).