for a given array of numbers 101 71 15 31 92 213 122 81 24 25
Alternatively we can code this as:
The implementation will iterate thru' the array switching and ordering numbers in the following manner:
Here is the iteration output for 10 number worst case array (reverse sorted array)
package net.study.algorithms;
public class InsertionSortImpl {
private static int[] intArray = {101, 71, 15, 31, 92, 213, 122, 81,24, 25};
//private static int[] intArray = {10,9,8,7,6,5,4,3,2,1}; //worst case
private static String note = "";
public static void main(String[] args) {
for (int i:intArray) {
System.out.print(i + " ");
}
for (int i=0; i<intArray.length; i++) {
for (int j=1;j<intArray.length; j++) {
if (intArray[j] < intArray[j-1]) {
int a = intArray[j-1];
intArray[j-1] = intArray[j];
intArray[j] = a;
}
else {
break; // break out of non-essential iterations
}
}
}
for (int i:intArray) {
System.out.print(i + " ");
}
}
}
Alternatively we can code this as:
package net.study.algorithms;
public class InsertionSortImpl {
private static int[] intArray = {101, 71, 15, 31, 92, 213, 100, 81,24, 25};
//private static int[] intArray = {10,9,8,7,6,5,4,3,2,1}; //worst case
private static String note = "";
public static void main(String[] args) {
for (int j=1; j< intArray.length;j++) {
int key = intArray[j];
int i = j-1;
System.out.println(i + " > " + 0 + " and " + intArray[i] +" > "+ key);
while (i>=0 && intArray[i] > key) {
System.out.println("intArray["+ (i+1) + "]" + " = " + intArray[i]);
intArray[i+1] = intArray[i];
i=i-1;
}
intArray[i+1] = key;
}
for (int x:intArray) {
System.out.print(+ x + " ");
}
}
}
The implementation will iterate thru' the array switching and ordering numbers in the following manner:
71 101 15 31 92 213 122 81 24 25 (1.1) switching 101 and 71 71 15 101 31 92 213 122 81 24 25 (1.2) switching 101 and 15 71 15 31 101 92 213 122 81 24 25 (1.3) switching 101 and 31 71 15 31 92 101 213 122 81 24 25 (1.4) switching 101 and 92 71 15 31 92 101 213 122 81 24 25 (1.5) no change for 101 and 213 71 15 31 92 101 122 213 81 24 25 (1.6) switching 213 and 122 71 15 31 92 101 122 81 213 24 25 (1.7) switching 213 and 81 71 15 31 92 101 122 81 24 213 25 (1.8) switching 213 and 24 71 15 31 92 101 122 81 24 25 213 (1.9) switching 213 and 25 15 71 31 92 101 122 81 24 25 213 (2.1) switching 71 and 15 15 31 71 92 101 122 81 24 25 213 (2.2) switching 71 and 31 15 31 71 92 101 122 81 24 25 213 (2.3) no change for 71 and 92 15 31 71 92 101 122 81 24 25 213 (2.4) no change for 92 and 101 15 31 71 92 101 122 81 24 25 213 (2.5) no change for 101 and 122 15 31 71 92 101 81 122 24 25 213 (2.6) switching 122 and 81 15 31 71 92 101 81 24 122 25 213 (2.7) switching 122 and 24 15 31 71 92 101 81 24 25 122 213 (2.8) switching 122 and 25 15 31 71 92 101 81 24 25 122 213 (2.9) no change for 122 and 213 15 31 71 92 101 81 24 25 122 213 (3.1) no change for 15 and 31 15 31 71 92 101 81 24 25 122 213 (3.2) no change for 31 and 71 15 31 71 92 101 81 24 25 122 213 (3.3) no change for 71 and 92 15 31 71 92 101 81 24 25 122 213 (3.4) no change for 92 and 101 15 31 71 92 81 101 24 25 122 213 (3.5) switching 101 and 81 15 31 71 92 81 24 101 25 122 213 (3.6) switching 101 and 24 15 31 71 92 81 24 25 101 122 213 (3.7) switching 101 and 25 15 31 71 92 81 24 25 101 122 213 (3.8) no change for 101 and 122 15 31 71 92 81 24 25 101 122 213 (3.9) no change for 122 and 213 15 31 71 92 81 24 25 101 122 213 (4.1) no change for 15 and 31 15 31 71 92 81 24 25 101 122 213 (4.2) no change for 31 and 71 15 31 71 92 81 24 25 101 122 213 (4.3) no change for 71 and 92 15 31 71 81 92 24 25 101 122 213 (4.4) switching 92 and 81 15 31 71 81 24 92 25 101 122 213 (4.5) switching 92 and 24 15 31 71 81 24 25 92 101 122 213 (4.6) switching 92 and 25 15 31 71 81 24 25 92 101 122 213 (4.7) no change for 92 and 101 15 31 71 81 24 25 92 101 122 213 (4.8) no change for 101 and 122 15 31 71 81 24 25 92 101 122 213 (4.9) no change for 122 and 213 15 31 71 81 24 25 92 101 122 213 (5.1) no change for 15 and 31 15 31 71 81 24 25 92 101 122 213 (5.2) no change for 31 and 71 15 31 71 81 24 25 92 101 122 213 (5.3) no change for 71 and 81 15 31 71 24 81 25 92 101 122 213 (5.4) switching 81 and 24 15 31 71 24 25 81 92 101 122 213 (5.5) switching 81 and 25 15 31 71 24 25 81 92 101 122 213 (5.6) no change for 81 and 92 15 31 71 24 25 81 92 101 122 213 (5.7) no change for 92 and 101 15 31 71 24 25 81 92 101 122 213 (5.8) no change for 101 and 122 15 31 71 24 25 81 92 101 122 213 (5.9) no change for 122 and 213 15 31 71 24 25 81 92 101 122 213 (6.1) no change for 15 and 31 15 31 71 24 25 81 92 101 122 213 (6.2) no change for 31 and 71 15 31 24 71 25 81 92 101 122 213 (6.3) switching 71 and 24 15 31 24 25 71 81 92 101 122 213 (6.4) switching 71 and 25 15 31 24 25 71 81 92 101 122 213 (6.5) no change for 71 and 81 15 31 24 25 71 81 92 101 122 213 (6.6) no change for 81 and 92 15 31 24 25 71 81 92 101 122 213 (6.7) no change for 92 and 101 15 31 24 25 71 81 92 101 122 213 (6.8) no change for 101 and 122 15 31 24 25 71 81 92 101 122 213 (6.9) no change for 122 and 213 15 31 24 25 71 81 92 101 122 213 (7.1) no change for 15 and 31 15 24 31 25 71 81 92 101 122 213 (7.2) switching 31 and 24 15 24 25 31 71 81 92 101 122 213 (7.3) switching 31 and 25 15 24 25 31 71 81 92 101 122 213 (7.4) no change for 31 and 71 15 24 25 31 71 81 92 101 122 213 (7.5) no change for 71 and 81 15 24 25 31 71 81 92 101 122 213 (7.6) no change for 81 and 92 15 24 25 31 71 81 92 101 122 213 (7.7) no change for 92 and 101 15 24 25 31 71 81 92 101 122 213 (7.8) no change for 101 and 122 15 24 25 31 71 81 92 101 122 213 (7.9) no change for 122 and 213 15 24 25 31 71 81 92 101 122 213 (8.1) no change for 15 and 24 15 24 25 31 71 81 92 101 122 213 (8.2) no change for 24 and 25 15 24 25 31 71 81 92 101 122 213 (8.3) no change for 25 and 31 15 24 25 31 71 81 92 101 122 213 (8.4) no change for 31 and 71 15 24 25 31 71 81 92 101 122 213 (8.5) no change for 71 and 81 15 24 25 31 71 81 92 101 122 213 (8.6) no change for 81 and 92 15 24 25 31 71 81 92 101 122 213 (8.7) no change for 92 and 101 15 24 25 31 71 81 92 101 122 213 (8.8) no change for 101 and 122 15 24 25 31 71 81 92 101 122 213 (8.9) no change for 122 and 213 15 24 25 31 71 81 92 101 122 213 (9.1) no change for 15 and 24 15 24 25 31 71 81 92 101 122 213 (9.2) no change for 24 and 25 15 24 25 31 71 81 92 101 122 213 (9.3) no change for 25 and 31 15 24 25 31 71 81 92 101 122 213 (9.4) no change for 31 and 71 15 24 25 31 71 81 92 101 122 213 (9.5) no change for 71 and 81 15 24 25 31 71 81 92 101 122 213 (9.6) no change for 81 and 92 15 24 25 31 71 81 92 101 122 213 (9.7) no change for 92 and 101 15 24 25 31 71 81 92 101 122 213 (9.8) no change for 101 and 122 15 24 25 31 71 81 92 101 122 213 (9.9) no change for 122 and 213 15 24 25 31 71 81 92 101 122 213 (10.1) no change for 15 and 24 15 24 25 31 71 81 92 101 122 213 (10.2) no change for 24 and 25 15 24 25 31 71 81 92 101 122 213 (10.3) no change for 25 and 31 15 24 25 31 71 81 92 101 122 213 (10.4) no change for 31 and 71 15 24 25 31 71 81 92 101 122 213 (10.5) no change for 71 and 81 15 24 25 31 71 81 92 101 122 213 (10.6) no change for 81 and 92 15 24 25 31 71 81 92 101 122 213 (10.7) no change for 92 and 101 15 24 25 31 71 81 92 101 122 213 (10.8) no change for 101 and 122 15 24 25 31 71 81 92 101 122 213 (10.9) no change for 122 and 213
Here is the iteration output for 10 number worst case array (reverse sorted array)
9 10 8 7 6 5 4 3 2 1 (1.1) switching 10 and 9 9 8 10 7 6 5 4 3 2 1 (1.2) switching 10 and 8 9 8 7 10 6 5 4 3 2 1 (1.3) switching 10 and 7 9 8 7 6 10 5 4 3 2 1 (1.4) switching 10 and 6 9 8 7 6 5 10 4 3 2 1 (1.5) switching 10 and 5 9 8 7 6 5 4 10 3 2 1 (1.6) switching 10 and 4 9 8 7 6 5 4 3 10 2 1 (1.7) switching 10 and 3 9 8 7 6 5 4 3 2 10 1 (1.8) switching 10 and 2 9 8 7 6 5 4 3 2 1 10 (1.9) switching 10 and 1 8 9 7 6 5 4 3 2 1 10 (2.1) switching 9 and 8 8 7 9 6 5 4 3 2 1 10 (2.2) switching 9 and 7 8 7 6 9 5 4 3 2 1 10 (2.3) switching 9 and 6 8 7 6 5 9 4 3 2 1 10 (2.4) switching 9 and 5 8 7 6 5 4 9 3 2 1 10 (2.5) switching 9 and 4 8 7 6 5 4 3 9 2 1 10 (2.6) switching 9 and 3 8 7 6 5 4 3 2 9 1 10 (2.7) switching 9 and 2 8 7 6 5 4 3 2 1 9 10 (2.8) switching 9 and 1 8 7 6 5 4 3 2 1 9 10 (2.9) no change for 9 and 10 7 8 6 5 4 3 2 1 9 10 (3.1) switching 8 and 7 7 6 8 5 4 3 2 1 9 10 (3.2) switching 8 and 6 7 6 5 8 4 3 2 1 9 10 (3.3) switching 8 and 5 7 6 5 4 8 3 2 1 9 10 (3.4) switching 8 and 4 7 6 5 4 3 8 2 1 9 10 (3.5) switching 8 and 3 7 6 5 4 3 2 8 1 9 10 (3.6) switching 8 and 2 7 6 5 4 3 2 1 8 9 10 (3.7) switching 8 and 1 7 6 5 4 3 2 1 8 9 10 (3.8) no change for 8 and 9 7 6 5 4 3 2 1 8 9 10 (3.9) no change for 9 and 10 6 7 5 4 3 2 1 8 9 10 (4.1) switching 7 and 6 6 5 7 4 3 2 1 8 9 10 (4.2) switching 7 and 5 6 5 4 7 3 2 1 8 9 10 (4.3) switching 7 and 4 6 5 4 3 7 2 1 8 9 10 (4.4) switching 7 and 3 6 5 4 3 2 7 1 8 9 10 (4.5) switching 7 and 2 6 5 4 3 2 1 7 8 9 10 (4.6) switching 7 and 1 6 5 4 3 2 1 7 8 9 10 (4.7) no change for 7 and 8 6 5 4 3 2 1 7 8 9 10 (4.8) no change for 8 and 9 6 5 4 3 2 1 7 8 9 10 (4.9) no change for 9 and 10 5 6 4 3 2 1 7 8 9 10 (5.1) switching 6 and 5 5 4 6 3 2 1 7 8 9 10 (5.2) switching 6 and 4 5 4 3 6 2 1 7 8 9 10 (5.3) switching 6 and 3 5 4 3 2 6 1 7 8 9 10 (5.4) switching 6 and 2 5 4 3 2 1 6 7 8 9 10 (5.5) switching 6 and 1 5 4 3 2 1 6 7 8 9 10 (5.6) no change for 6 and 7 5 4 3 2 1 6 7 8 9 10 (5.7) no change for 7 and 8 5 4 3 2 1 6 7 8 9 10 (5.8) no change for 8 and 9 5 4 3 2 1 6 7 8 9 10 (5.9) no change for 9 and 10 4 5 3 2 1 6 7 8 9 10 (6.1) switching 5 and 4 4 3 5 2 1 6 7 8 9 10 (6.2) switching 5 and 3 4 3 2 5 1 6 7 8 9 10 (6.3) switching 5 and 2 4 3 2 1 5 6 7 8 9 10 (6.4) switching 5 and 1 4 3 2 1 5 6 7 8 9 10 (6.5) no change for 5 and 6 4 3 2 1 5 6 7 8 9 10 (6.6) no change for 6 and 7 4 3 2 1 5 6 7 8 9 10 (6.7) no change for 7 and 8 4 3 2 1 5 6 7 8 9 10 (6.8) no change for 8 and 9 4 3 2 1 5 6 7 8 9 10 (6.9) no change for 9 and 10 3 4 2 1 5 6 7 8 9 10 (7.1) switching 4 and 3 3 2 4 1 5 6 7 8 9 10 (7.2) switching 4 and 2 3 2 1 4 5 6 7 8 9 10 (7.3) switching 4 and 1 3 2 1 4 5 6 7 8 9 10 (7.4) no change for 4 and 5 3 2 1 4 5 6 7 8 9 10 (7.5) no change for 5 and 6 3 2 1 4 5 6 7 8 9 10 (7.6) no change for 6 and 7 3 2 1 4 5 6 7 8 9 10 (7.7) no change for 7 and 8 3 2 1 4 5 6 7 8 9 10 (7.8) no change for 8 and 9 3 2 1 4 5 6 7 8 9 10 (7.9) no change for 9 and 10 2 3 1 4 5 6 7 8 9 10 (8.1) switching 3 and 2 2 1 3 4 5 6 7 8 9 10 (8.2) switching 3 and 1 2 1 3 4 5 6 7 8 9 10 (8.3) no change for 3 and 4 2 1 3 4 5 6 7 8 9 10 (8.4) no change for 4 and 5 2 1 3 4 5 6 7 8 9 10 (8.5) no change for 5 and 6 2 1 3 4 5 6 7 8 9 10 (8.6) no change for 6 and 7 2 1 3 4 5 6 7 8 9 10 (8.7) no change for 7 and 8 2 1 3 4 5 6 7 8 9 10 (8.8) no change for 8 and 9 2 1 3 4 5 6 7 8 9 10 (8.9) no change for 9 and 10 1 2 3 4 5 6 7 8 9 10 (9.1) switching 2 and 1 1 2 3 4 5 6 7 8 9 10 (9.2) no change for 2 and 3 1 2 3 4 5 6 7 8 9 10 (9.3) no change for 3 and 4 1 2 3 4 5 6 7 8 9 10 (9.4) no change for 4 and 5 1 2 3 4 5 6 7 8 9 10 (9.5) no change for 5 and 6 1 2 3 4 5 6 7 8 9 10 (9.6) no change for 6 and 7 1 2 3 4 5 6 7 8 9 10 (9.7) no change for 7 and 8 1 2 3 4 5 6 7 8 9 10 (9.8) no change for 8 and 9 1 2 3 4 5 6 7 8 9 10 (9.9) no change for 9 and 10 1 2 3 4 5 6 7 8 9 10 (10.1) no change for 1 and 2 1 2 3 4 5 6 7 8 9 10 (10.2) no change for 2 and 3 1 2 3 4 5 6 7 8 9 10 (10.3) no change for 3 and 4 1 2 3 4 5 6 7 8 9 10 (10.4) no change for 4 and 5 1 2 3 4 5 6 7 8 9 10 (10.5) no change for 5 and 6 1 2 3 4 5 6 7 8 9 10 (10.6) no change for 6 and 7 1 2 3 4 5 6 7 8 9 10 (10.7) no change for 7 and 8 1 2 3 4 5 6 7 8 9 10 (10.8) no change for 8 and 9 1 2 3 4 5 6 7 8 9 10 (10.9) no change for 9 and 10
