Java

# Bubble Sort with Java

Bubble sort is the simplest sorting algorithm: Assume that there are elements in a row that are not sorted. Bubble sort scans the row from the left, swapping any adjacent pair of elements that are not in the correct order. This scanning of the whole row is repeated repeatedly until the whole row is sorted. If the sorting is to be ascending, then the adjacent pair is swapped to make the element on the left less than the element on the right. If the sorting is to be descending, then the adjacent pair is swapped to make the element on the left greater than the element on the right.

## Bubble Sort Illustration without Code

Consider the following unsorted row list of characters of the alphabet:

Q  W  E  R  T  Y  U  I  O  P

This list will be sorted in ascending order as follows. In the first scan, Q and W are compared; Q is less than W, so there is no swapping. Still, in the first scan, W and E are compared; E is less than W, so there is swapping. The new third element, W, is compared with R; R is less than W, so there is swapping. The new fourth element, W, is compared with T; T is less than W, so there is swapping. The new fifth element, W, is compared with Y; W is less than Y, and there is no swapping. Still, in the first scan, Y is compared with U; U is less than Y, so there is swapping. The new seventh element, Y, is compared with I; I is less than Y, and there is swapping. The new eighth element, Y, is compared with O; O is less than Y, and there is swapping. The new ninth element, Y, is compared with P; P is less than Y, and there is swapping. The first scan ends there. The result for the first scan is,

Q  E  R  T  W  U  I  O  P  Y

Notice that the biggest element is at the end after the first scan. The scanning of all the resulting ten elements, and possible swapping, is repeated once again to have:

E  R  Q  T  U  I  O  P  W  Y

Notice that the next biggest element is now the last-but-one element, and there was no need to compare it with the last element, so a small time would not have been wasted. The scanning of all the resulting ten elements, and possible swapping, is repeated once again to have:

E  Q  R  T  I  O  P  U  W  Y

Notice that the third biggest element towards the end is now at the third position from the end, and there was no need to compare it with the last two elements, and no need to compare the last two elements themselves, and so some small-time would not have been wasted. The scanning of all the resulting ten elements, and possible swapping, is repeated once again to have:

E  Q  R  I  O  P  T  U  W  Y

Notice that the fourth biggest element towards the end is now at the fourth position from the end, and there was no need to compare it with the last three elements, and no need to compare the last three elements themselves, and so some time would not have been wasted. The scanning of all the resulting ten elements, and possible swapping, is repeated once again to have:

E  Q  I  O  P  R  T  U  W  Y

Notice that the fifth biggest element towards the end is now at the fifth position from the end, and there was no need to compare it with the last four elements, and no need to compare the last four elements themselves, and so time would not have been wasted. The scanning of all the resulting ten elements, and possible swapping, is repeated again to have:

E  I  O  P  Q  R  T  U  W  Y

The rest of the scanning results are as follows:

E  I  O  P  Q  R  T  U  W  Y

E  I  O  P  Q  R  T  U  W  Y

E  I  O  P  Q  R  T  U  W  Y

E  I  O  P  Q  R  T  U  W  Y

Notice that no sorting has taken place for these last four results.

The reverse of all the above algorithms can be done for sort descending.

## Optimizing Bubble Sort

From the basic definition of bubble sort, if there are N elements, then there will be N complete scans. One scan is one iteration. So, the above ten elements mean ten complete iterations. The total length of time to bubble sort a list (array) can be reduced for many unsorted lists. This involves bubble sort strategies. Bubble sort is optimized with two strategies.

## First Optimization Strategy

Notice from the above that, after the first complete iteration, the biggest element is at the end, and it would be a waste of time accessing it in the second iteration. After the second iteration, the last two elements are in their right positions, and time should not be wasted accessing them in the third iteration. This means that the second iteration should end at N-1. After the third iteration, the last three elements are in their right positions, and time should not be wasted accessing them in the fourth iteration. This means that the third iteration should end at N-2. After the fourth iteration, the last four elements are in their right positions, and time should not be wasted accessing them in the fifth iteration. This means that the fourth iteration should end at N-3. This continues.

From the basic definition of bubble sort, the iteration has to be done N times. If the counter for the N iterations is at i, then the iteration should access N – i elements to avoid wasting time at the end of the array; and with i beginning from 0. So there has to be two Java for-loops: the outer for-loop iterates N times, and the inner for-loop iterates N – i times, for the array elements, for each of the N times. Iterating an array N – i times is the first strategy.

## Second Optimization Strategy

Should the outer for-loop really iterate N times? Should the outer for-loop for the above list iterate 10 times? – No, because its last four iterations would not change anything (it does not do any sorting). This means the list has been sorted as soon as it is detected; the outer loop should break, so sorting should stop. This will save more time. This can be achieved by having a boolean variable for the outer-loop, which would remain false in the inner-loop when swapping stops taking place.

## Java Code for Bubble Sort

The following class has the method to do the sorting:

class AClass {
static void bubbleSort(char arr[]) {
int N = arr.length;
boolean swapped = false;
for (int i = 0; i < N; i++) {
swapped = false;
for (int j = 1; j < N - i; j++) {
if (arr[j] < arr[j - 1]) {
char temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
swapped = true;
}
}
if (swapped == false) break;
}
}
}

Note the while-condition, “j < N – i;” for the inner for-loop, for the first strategy. Note the use of the boolean variable in the outer for-loop and the inner for-loop for the second strategy.

A suitable main class for this, is:

public class TheClass {
public static void main(String[] args) {
char ar[] = {&#039;Q&#039;, &#039;W&#039;, &#039;E&#039;, &#039;R&#039;, &#039;T&#039;, &#039;Y&#039;, &#039;U&#039;, &#039;I&#039;, &#039;O&#039;, &#039;P&#039;};
AClass.bubbleSort(ar);
for (int i=0; i&lt;ar.length; i++) {
System.out.print(ar[i]); System.out.print(&#039; &#039;);
}
System.out.println();
}
}

The array is passed by reference to the bubbleSort() method in a different class. So its content is modified. The output is:

E I O P Q R T U W Y

## Conclusion

Bubble sort sorts by swapping adjacent elements from the beginning to the end of the list. This procedure is repeated again and again until the whole list is completely sorted. The sorting is either ascending or descending. Bubble sort should be optimized, as explained above. 