Trace Bubblesort

part 1
------
+----+----+----+----+----+----+
| 7  | 39 | 20 | 11 | 16 | 5  |
+----+----+----+----+----+----+

first pass:
+----+----+----+----+----+----+
| 7  | 20 | 39 | 11 | 16 | 5  |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 20 | 11 | 39 | 16 | 5  |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 20 | 11 | 16 | 39 | 5  |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 20 | 11 | 16 | 5  | 39 |
+----+----+----+----+----+----+

second pass:
+----+----+----+----+----+----+
| 7  | 11 | 20 | 16 | 5  | 39 |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 11 | 16 | 20 | 5  | 39 |
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 7  | 11 | 16 | 5  | 20 | 39 |
+----+----+----+----+----+----+

third pass:
+----+----+----+----+----+----+
| 7  | 11 | 5  | 16 | 20 | 39 |
+----+----+----+----+----+----+

fourth pass:
+----+----+----+----+----+----+
| 7  | 5  | 11 | 16 | 20 | 39 |
+----+----+----+----+----+----+

fifth pass:
+----+----+----+----+----+----+
| 5  | 7  | 11 | 16 | 20 | 39 |
+----+----+----+----+----+----+


part 2
------
a) pass #       # of comparisons
   ------       ----------------
      1              n - 1
      2              n - 2
      3              n - 3
     ...              ...
     n - 2             2
     n - 1             1

b) total comparisons = 1 + 2 + ... + (n-1)

   In other words, it is the sum of the arithmetic sequence from 1 to n-1.
   In lecture, we saw that this sum produces the formula (n^2)/2 - n/2

c) O(n^2)

d) best case: the array is sorted to begin, so it performs 0 moves

   worst case: the array is initially in reverse order, so every comparison 
   leads to a swap, and there are 3 moves per swap
     ==> (3n^2)/2 - 3n/2   ==> O(n^2)

   average case: if the array starts out randomly ordered, on average half 
   of the comparisons lead to a swap
     ==> (3n^2)/4 - 3n/4   ==> O(n^2)

e) When we add comparisons and moves together, the fastest-growing term 
   is always an n^2 term, since comparisons are always O(n^2), and 
   moves are at worst O(n^2). Thus, the overall running time is O(n^2).

f) One option is to use a boolean variable that indicates if any swaps have been
   made. This variable could be used in conjunction with the conditional statement
   of the outer loop to control its execution.

   public static void bubbleSort(int[] arr) {
    boolean sorted = false;

    for (int i = arr.length - 1; i > 0 && !sorted; i--) {
        sorted = true; 	// assume data is sorted

        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {   	// compare and swap if necessary
                sorted = false; 	// indicate still not sorted 
                swap(arr, j, j+1);
            }
        }
        // if no swaps were made when the inner loop concludes, 
        // sorted remains true and the conditional check of the outer loop
        // will evaluate to false, stopping the loop
    }
}