import java.util.Comparator; class BubbleSort1 { public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void sort(int[] data) { // does n passes; invariant: at the end of each loop, // the max element found is placed into "the right spot," to the // left of the numSorted elements of the sorted part of the array. for (int numSorted = 0; numSorted < data.length; numSorted++) { // does n-1 swaps for (int i = 1; i < data.length; i++) { if (data[i-1] > data[i]) { swap(data, i-1, i); } } // The line below shows that the biggest element // is in "the right spot" at the end of each iteration // of the outermost loop. In other words, that the // loop invariant is always true. System.out.println("biggest is: " + data[data.length-numSorted-1]); } } }