/*
* Chimomo's Blog: https://blog.csdn.net/chimomo/
*/
package chimomo.learning.java.algorithm.sort;
/**
*
* @author Chimomo
*
* <p>
* Bubble sort is a kind of simple sort algorithm in computer science. It
* repeatedly visit the sequence to be sorted, compare two elements each time,
* swap them if their order is wrong, until no elements need to be swapped. The
* bigger element will rise to top by swapping like bubble, so it names.
* </p>
*
* The bubble sort algorithm designed as following:
* <li>
* 1. Compare the two adjacent elements as a pair, from the first pair to last
* pair, swap the two if the first one is bigger than the second one. Then, the
* last element must be the biggest, remove the biggest one from unordered
* region.
* </li>
* <li>
* 2. Repeat step1 on the elements in the unordered region until no element pair
* need to be compared.
* </li>
*
* The time complexity of bubble sort is O(n^2).
*
* <p>
* Stability: Bubble sort is swapping bigger element backward. Comparing is
* comparing the adjacent two elements, swapping is also in the adjacent two
* elements. So, if the two adjacent elements equal, you will not swap them. And
* if the two equal elements are not adjacent, even though they are adjacent by
* swapping the front other elements, you still will not swap them. The equal
* elements order are not changed in sorting, so bubble sort is stable.
* </p>
*/
public class BubbleSort {
/**
* The bubble sort.
* @param a The array to be sorted
*/
public static void sort(int[] a) {
System.out.println("In Bubble Sort:");
// The outer loop: Limit the count of elements in each bubble sort comparison.
for (int i = a.length - 1; i >= 1; i--) {
// The inner loop: Comparing the elements which subscript from 0 to i-1.
for (int j = 0; j <= i - 1; j++) {
// The sorting process.
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
System.out.println(String.format("Round {0}: ", a.length - i));
for (int e : a) {
System.out.print(e + " ");
}
System.out.println();
}
}
}
