Bubble Sort
by Isai Damier, Android Engineer @ Google

/****************************************************************************
 * Author: Isai Damier
 * Title: Bubblesort
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a disordered list of integers (or any other items),
 *   rearrange the integers in natural order.
 *
 * Sample Input: {8,5,3,1,9,6,0,7,4,2,5}
 * Sample Output: {0,1,2,3,4,5,5,6,7,8,9}
 *
 *Time Complexity of Solution:
 *   Best O(n^2); Average O(n^2); Worst O(n^2).
 *
 * Approach:
 *   Bubblesort is an elementary sorting algorithm. The idea is to imagine
 *   bubbling the smallest elements of a (vertical) array to the top; then
 *   bubble the next smallest; then so on until the entire array is sorted.
 *   Bubble sort is worse than both insertion sort and selection sort. It
 *   moves elements as many times as insertion sort (bad) and it takes as
 *   long as selection sort (bad). On the positive side, bubble sort is easy
 *   to understand. Also there are highly improved variants of bubble sort.
 *
 *   1] For each element at index i from 0 to n, loop
 *   2] For each element at index k, from n to i exclusive, loop
 *   3] If the element at k is less than that at k-1, swap them.
 *
 ***************************************************************************/ 
 public void bubblesort(int[] A) {
  for (int i = 0, k; i < A.length - 1; i++) {
    for (k = A.length - 1; k > i; --k) {
      if (A[k] < A[k - 1]) {
        swap(A, k, k - 1);
      }
    }
  }
}

private void swap(int[] input, int a, int b) {
  int tmp = input[a];
  input[a] = input[b];
  input[b] = tmp;
}
import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {

  /**
   * Test of bubblesort method, of class Sorting.
   */
  @Test
  public void testBubblesort() {
    System.out.println(""bubblesort"");
    int[] A = {8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5};
    Sorting instance = new Sorting();
    instance.bubblesort(A);
    for (int i = 1; i < A.length; i++) {
      if (A[i - 1] > A[i]) {
        fail(""bubblesort method fails."");
      }
    }
  }
}