Bubble Sort 

The following example shows bubble sort implementation.

• Best case time complexity of bubble sort is O(n)
• Worst case time complexity of bubble sort is O(n²)
• Average case time complexity of bubble sort is O(n²)

File Name  :   com/bethecoder/tutorials/ds/sort/BubbleSort.java  Author  :   Sudhakar KV Email  :   [email protected]

package com.bethecoder.tutorials.ds.sort; import java.util.Arrays; public class BubbleSort {   /**    * @param args    */   public static void main(String[] args) {     int[] list = { 6, 5, 1, 8, 3, 9, 4, 0, 2, 7 };     System.out.println("Before sort : " + Arrays.toString(list));     double timeTaken = bubbleSortTimeTaken(list);     System.out.println("After sort : " + Arrays.toString(list));     System.out.println("Time taken for BubbleSort : " + timeTaken + " milliseconds.");   }   /**    * In each iteration the minimum element is bubbled out.    * After Step1 the minimum element in array [0..n-1] occupies first place    * After Step2 the minimum element in rest of the array [1..n-1] occupies second place.     * After Step3 the minimum element in rest of the array [2..n-1] occupies third place.    * So on..    * @param list    */   public static void bubbleSort(int[] list) {          for (int i = 0 ; i < list.length - 1 ; i ++) {       for (int j = i + 1 ; j < list.length ; j ++) {         if (list[i] > list[j]) {           list[i] = list[i] + list[j] - (list[j] = list[i]);         }       }              System.out.println("Step " + (i+1) + " : " + Arrays.toString(list));     }   }      /**    * Sorts and returns the time taken in milliseconds.    *     * @param list    * @return    */   public static double bubbleSortTimeTaken(int[] list) {     long startTime = System.nanoTime();     bubbleSort(list);     long timeTaken = System.nanoTime() - startTime;     return timeTaken * Math.pow(10, -6);   } }

Before sort : [6, 5, 1, 8, 3, 9, 4, 0, 2, 7]
Step 1 : [0, 6, 5, 8, 3, 9, 4, 1, 2, 7]
Step 2 : [0, 1, 6, 8, 5, 9, 4, 3, 2, 7]
Step 3 : [0, 1, 2, 8, 6, 9, 5, 4, 3, 7]
Step 4 : [0, 1, 2, 3, 8, 9, 6, 5, 4, 7]
Step 5 : [0, 1, 2, 3, 4, 9, 8, 6, 5, 7]
Step 6 : [0, 1, 2, 3, 4, 5, 9, 8, 6, 7]
Step 7 : [0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
Step 8 : [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
Step 9 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
After sort : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Time taken for BubbleSort : 0.626895 milliseconds.