Bubble Sort in Java

Bubble sort is the most simplest form of sorts available. In real lives, the bubbles formed under water tend to come up to the surface. Larger the bubble, faster it will come up. Same way in this sorting technique, we would try to push the larger value up in case of descending or vice versa.

Pros:
1. Simple to implement.
2. Very easy to understand.

Cons:
1. Runs in O(n²) complexity.
2. Severe performance issues if the sample size increases.

The java code for this sorting technique is as follows,

package dsa.sorting;

public class BubbleSort {

 public static int SIZE = 100000;

 public static void main(String args[]) {
  int[] a = new int[SIZE];
  for (int i = 0; i < SIZE; i++) {
   a[i] = (int) (Math.random() * SIZE);
  }
  long start = System.currentTimeMillis();
  BubbleSort mNew = new BubbleSort();
  mNew.sort(a);
  long end = System.currentTimeMillis();
  System.out.println("Time taken to sort a 100000 elements : "
    + (end - start) + " milliseconds");
 }

 public int[] sort(int[] input) {
  int temp;
  for (int i = 0; i < input.length; i++) {
   for (int j = i; j < input.length; j++) {
    if (input[i] > input[j]) {
     temp = input[i];
     input[i] = input[j];
     input[j] = temp;
    }
   }
  }
  return input;
 }
}
// Time taken to sort a 100000 elements : 28554 milliseconds

You may see from the above example that it takes insanely higher time for sorting only a hundred thousand elements. 29 seconds is a very poor outcome. We will look into O(nlogn) sort types on why and how it reduces this running time.

Cheers,
Bragaadeesh.