Code showing state progress of insertion sort based on Ajax: The Definitive Guide O'Reilly 2008 p 267
package sort;
public class InsertionSort {
public static void main(String[] args) {
int[] nums = new int[] {9, 5, 3, 7, 3};
int[] res = new InsertionSort().insertionSort(nums);
printState(res, " the end", true);
}
public int[] insertionSort(int[] dataArray) {
int j, index;
for (int i = 0, il = dataArray.length; i < il; i++) {
index = dataArray[i];
j = i;
printState(dataArray, " ...before while: i=" + i + ", j="+j, false);
if (j == 0) {
System.out.println(" j==0 ");
} else {
System.out.println(" ...comparing " + dataArray[j - 1] + " > " + index);
}
while ((j > 0) && (dataArray[j - 1] > index)) {
dataArray[j] = dataArray[j - 1];
printState(dataArray, " ...in while: i=" + i + ", j="+j, false);
j -= 1;
if (j == 0) {
System.out.println(" j==0 ");
} else {
System.out.println(" ...comparing " + dataArray[j - 1] + " > " + index);
}
}
dataArray[j] = index;
printState(dataArray, " ...after while: i=" + i + ", j="+j, true);
}
return (dataArray);
}
private static void printState(int[] res, String msg, boolean endLine) {
for (int i =0, j=res.length; i < j; i++) {
System.out.print(res[i] + ((i<j-1)? ", ":""));
}
if (endLine)
System.out.println(msg);
else
System.out.print(msg);
}
}
Output:
9, 5, 3, 7, 3 ...before while: i=0, j=0 j==0
9, 5, 3, 7, 3 ...after while: i=0, j=0
9, 5, 3, 7, 3 ...before while: i=1, j=1 ...comparing 9 > 5
9, 9, 3, 7, 3 ...in while: i=1, j=1 j==0
5, 9, 3, 7, 3 ...after while: i=1, j=0
5, 9, 3, 7, 3 ...before while: i=2, j=2 ...comparing 9 > 3
5, 9, 9, 7, 3 ...in while: i=2, j=2 ...comparing 5 > 3
5, 5, 9, 7, 3 ...in while: i=2, j=1 j==0
3, 5, 9, 7, 3 ...after while: i=2, j=0
3, 5, 9, 7, 3 ...before while: i=3, j=3 ...comparing 9 > 7
3, 5, 9, 9, 3 ...in while: i=3, j=3 ...comparing 5 > 7
3, 5, 7, 9, 3 ...after while: i=3, j=2
3, 5, 7, 9, 3 ...before while: i=4, j=4 ...comparing 9 > 3
3, 5, 7, 9, 9 ...in while: i=4, j=4 ...comparing 7 > 3
3, 5, 7, 7, 9 ...in while: i=4, j=3 ...comparing 5 > 3
3, 5, 5, 7, 9 ...in while: i=4, j=2 ...comparing 3 > 3
3, 3, 5, 7, 9 ...after while: i=4, j=1
3, 3, 5, 7, 9 the end
