Bubblesort

Bubble sort based on en.wikipedia.org. This algorithm is O(n^2) because the inner loop has O(n) comparisons and the outer loop runs O(n) times.  The inner loop can be optimized to reduce by 1 each time.  Also, when no swaps are made, it can exit.  This is O(n^2/2 - k^2/2) = O(n^2).

--------
-------
------
-----
----

package algorithm;

public class bubblesort {
 public static void main(String[] args) {
  System.out.println("Case I");
  int[] numbers = new int[] {3, 7, 8, 5, 2, 1, 9, 5, 4};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  bubblesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
  
  System.out.println("Case II");
  numbers = new int[] {9, 8, 7, 6, 5, 4, 3, 2, 1};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  bubblesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case III");
  numbers = new int[] {5, 5, 5, 5, 5, 5, 5, 5, 5};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  bubblesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");

  System.out.println("Case IV");
  numbers = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
  printArray(0, numbers.length - 1, numbers, "pre_sort");
  bubblesort(numbers);
  printArray(0, numbers.length - 1, numbers, "post_sort");
 }

 private static void printArray(int start, int end, int[] numbers, String text) {
  String out = "{";
  String del = "";
  for(int i=start; i < end + 1; i++) {
   out = out + del + numbers[i] + "";
   del = ",";
  }
  out = out + "}";
  System.out.println(text+":"+out);
 }
 
 // O(n^2)
 private static void bubblesort(int[] numbers) {
  int n = numbers.length; // First optimization is that nth largest number is put in place on nth iteration, so no need to check last n after n iterations
  boolean swapped = false; // Second optimization is that if no swap occurs, the array is already sorted, so can exit
  
  // O(n)
  for(int i=0; i < numbers.length; i++) {
   swapped = lookForSwaps(numbers, n);
   
   if(!swapped) {
    return;
   }
   n = n - 1;
  }
 }

 private static boolean lookForSwaps(int[] numbers, int n) {
  int first = numbers[0]; 
  boolean swapped = false;
  
  // O(n) on inner loop - Though n decreases
  for(int j=1; j < n; j++) {
   int second = numbers[j];
   if(first > second) {
    swap(numbers, j, first, second);
    swapped = true;
   } else {
    first = second;
   }
  }
  
  return swapped;
 }

 private static void swap(int[] numbers, int j, int first,
   int second) {
  numbers[j-1] = second;
  numbers[j] = first;
  printArray(0, numbers.length - 1, numbers, "swapped");
 }
}

Output

Case I
pre_sort:{3,7,8,5,2,1,9,5,4}
swapped:{3,7,5,8,2,1,9,5,4}
swapped:{3,7,5,2,8,1,9,5,4}
swapped:{3,7,5,2,1,8,9,5,4}
swapped:{3,7,5,2,1,8,5,9,4}
swapped:{3,7,5,2,1,8,5,4,9}
swapped:{3,5,7,2,1,8,5,4,9}
swapped:{3,5,2,7,1,8,5,4,9}
swapped:{3,5,2,1,7,8,5,4,9}
swapped:{3,5,2,1,7,5,8,4,9}
swapped:{3,5,2,1,7,5,4,8,9}
swapped:{3,2,5,1,7,5,4,8,9}
swapped:{3,2,1,5,7,5,4,8,9}
swapped:{3,2,1,5,5,7,4,8,9}
swapped:{3,2,1,5,5,4,7,8,9}
swapped:{2,3,1,5,5,4,7,8,9}
swapped:{2,1,3,5,5,4,7,8,9}
swapped:{2,1,3,5,4,5,7,8,9}
swapped:{1,2,3,5,4,5,7,8,9}
swapped:{1,2,3,4,5,5,7,8,9}
post_sort:{1,2,3,4,5,5,7,8,9}
Case II
pre_sort:{9,8,7,6,5,4,3,2,1}
swapped:{8,9,7,6,5,4,3,2,1}
swapped:{8,7,9,6,5,4,3,2,1}
swapped:{8,7,6,9,5,4,3,2,1}
swapped:{8,7,6,5,9,4,3,2,1}
swapped:{8,7,6,5,4,9,3,2,1}
swapped:{8,7,6,5,4,3,9,2,1}
swapped:{8,7,6,5,4,3,2,9,1}
swapped:{8,7,6,5,4,3,2,1,9}
swapped:{7,8,6,5,4,3,2,1,9}
swapped:{7,6,8,5,4,3,2,1,9}
swapped:{7,6,5,8,4,3,2,1,9}
swapped:{7,6,5,4,8,3,2,1,9}
swapped:{7,6,5,4,3,8,2,1,9}
swapped:{7,6,5,4,3,2,8,1,9}
swapped:{7,6,5,4,3,2,1,8,9}
swapped:{6,7,5,4,3,2,1,8,9}
swapped:{6,5,7,4,3,2,1,8,9}
swapped:{6,5,4,7,3,2,1,8,9}
swapped:{6,5,4,3,7,2,1,8,9}
swapped:{6,5,4,3,2,7,1,8,9}
swapped:{6,5,4,3,2,1,7,8,9}
swapped:{5,6,4,3,2,1,7,8,9}
swapped:{5,4,6,3,2,1,7,8,9}
swapped:{5,4,3,6,2,1,7,8,9}
swapped:{5,4,3,2,6,1,7,8,9}
swapped:{5,4,3,2,1,6,7,8,9}
swapped:{4,5,3,2,1,6,7,8,9}
swapped:{4,3,5,2,1,6,7,8,9}
swapped:{4,3,2,5,1,6,7,8,9}
swapped:{4,3,2,1,5,6,7,8,9}
swapped:{3,4,2,1,5,6,7,8,9}
swapped:{3,2,4,1,5,6,7,8,9}
swapped:{3,2,1,4,5,6,7,8,9}
swapped:{2,3,1,4,5,6,7,8,9}
swapped:{2,1,3,4,5,6,7,8,9}
swapped:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}
Case III
pre_sort:{5,5,5,5,5,5,5,5,5}
post_sort:{5,5,5,5,5,5,5,5,5}
Case IV
pre_sort:{1,2,3,4,5,6,7,8,9}
post_sort:{1,2,3,4,5,6,7,8,9}