We need to improve the bubble sort algorithm by reducing the number of passes.
The steps to do this are as follows:
- Change the bubble sort method so that it stops sorting if the array is untouched after an inner loop pass.
- 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;
}
}
}
}
Snippet 2.4: Bubble sort improvement 2. Source class name: BubbleSort
In this section, we have seen some simple tricks on how to improve the bubble sort algorithm. In the following sections, we shall look at some other sorting techniques that perform much faster than bubble sort.