tl  tr
  Home | Tutorials | Articles | Videos | Products | Tools | Search
Open Source | Tag Cloud | Follow Us | Bookmark | Contact   
 
 Data Structures > Sort > Bubble Sort

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(n2)
  • Average case time complexity of bubble sort is O(n2)

File Name  :  
com/bethecoder/tutorials/ds/sort/BubbleSort.java 
Author  :  Sudhakar KV
Email  :  kvenkatasudhakar@gmail.com
   
package com.bethecoder.tutorials.ds.sort;

import java.util.Arrays;

public class BubbleSort {

  /**
   @param args
   */
  public static void main(String[] args) {

    int[] list = 651839402};
    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 = ; i < list.length - ; i ++) {
      for (int j = i + ; 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);
  }
}
   

It gives the following output,
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.


                    Print

   



Books Recommendation

 
 
bl  br