Beginning Java Data Structures and Algorithms

Implementing Bubble Sort Improvement

We need to improve the bubble sort algorithm by reducing the number of passes.

The steps to do this are as follows:

1. Change the bubble sort method so that it stops sorting if the array is untouched after an inner loop pass.
2. The solution can be developed easily if the outer for loop is changed into a while loop and a flag is kept to indicate if any elements have been swapped while going through the array. This is shown in the following code snippet:

public void sortImprovement2(int[] numbers) {  int i = 0;  boolean swapOccured = true;  while (swapOccured) {     swapOccured = false;     i++;     for (int j = 0; j < numbers.length - i; j++) {          if (numbers[j] > numbers[j + 1]) {              swap(numbers, j, j + 1); swapOccured = true; ...