Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

How Bubble Sorting Works

/** Created by Ali on 9/1/2016.

  * Bubble Sort that works by repeatedly swapping the adjacent elements 

  * if they are in wrong order.
  */

public class BubbleSort {

    public static void main(String str[]){
        int[] arr = new int[]{10,54,2,100,200,121,99,150,51,181};
        BubbleSort obj = new BubbleSort();
        int[] sortedArray = obj.bubbleSort(arr);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.print(sortedArray[i] + " ");
        }
    }

    private int[] bubbleSort(int[] unsortedArray) {
        int length = unsortedArray.length;
        for (int i = 0; i < length-1; i++) {
            for(int j = 0; j < length-i-1; j++) {
                if(unsortedArray[j] > unsortedArray[j+1]) {
                    swap(unsortedArray, j , j+1);
                }
            }
        }
        return unsortedArray;
    }

    // An optimized version of Bubble Sort    

    private int[] bubbleSortOptimized(int unsortedArray[]) {
        int i, j;
        int length = unsortedArray.length;
        boolean swapped;
        for (i = 0; i < length-1; i++) {
            swapped = false;
            for (j = 0; j < length-i-1; j++) {
                if (unsortedArray[j] > unsortedArray[j+1]) {
                    swap(unsortedArray, j , j+1);
                    swapped = true;
                }
            }
            // IF no two elements were swapped by inner loop, then break            if (swapped == false)
                break;
        }
        return unsortedArray;
    }

    private void swap(int[] array, int i1, int i2) {
        int temp;
        temp = array[i1];
        array[i1] = array[i2];
        array[i2] = temp;
    }
}

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.

Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

Auxiliary Space: O(1)