Sorting, Searching, and Merging - Advanced Topics in Java: Core Concepts in Data Structures - page 9

We exit the while loop if k is equal to -1 or if key is greater than or equal to list[k] , for some k . In either case,
key is inserted into list[k+1] .
If k is -1 , it means that the current number is smaller than all the previous numbers in the list and must be
inserted in list[0] . But list[k + 1] is list[0] when k is -1 , so key is inserted correctly in this case.
The function sorts in ascending order. To sort in descending order, all we have to do is change < to > in the while
condition, like this:
while (k >= 0 && key > list[k])
Now, a key moves to the left if it is bigger .
We write Program P1.2 to test whether insertionSort works correctly. Only main is shown. Adding the function
insertionSort completes the program.
Program P1.2
import java.util.*;
public class InsertSortTest {
final static int MaxNumbers = 10;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] num = new int[MaxNumbers];
System.out.printf("Type up to %d numbers followed by 0\n", MaxNumbers);
int n = 0;
int v = in.nextInt();
while (v != 0 && n < MaxNumbers) {
num[n++] = v;
v = in.nextInt();
}
if (v != 0) {
System.out.printf("\nMore than %d numbers entered\n", MaxNumbers);
System.out.printf("First %d used\n", MaxNumbers);
}
if (n == 0) {
System.out.printf("\nNo numbers supplied\n");
System.exit(1);
}
//n numbers are stored from num[0] to num[n-1]
insertionSort(num, n);
System.out.printf("\nThe sorted numbers are\n");
for (v = 0; v < n; v++) System.out.printf("%d ", num[v]);
System.out.printf("\n");
} //end main
public static void insertionSort(int list[], int n) {
//sort list[0] to list[n-1] in ascending order
for (int h = 1; h < n; h++) {
int key = list[h];
int k = h - 1; //start comparing with previous item
while (k >= 0 && key < list[k]) {
list[k + 1] = list[k];
--k;
}