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

//n numbers are stored from num[0] to num[n-1]
insertionSort2(num, 0, n-1);
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 insertionSort2(int list[], int lo, int hi) {
//sort list[lo] to list[hi] in ascending order
for (int h = lo + 1; h <= hi; h++)
insertInPlace(list[h], list, lo, h - 1);
} //end insertionSort2
public static void insertInPlace(int newItem, int list[], int m, int n) {
//list[m] to list[n] are sorted
//insert newItem so that list[m] to list[n+1] are sorted
int k = n;
while (k >= m && newItem < list[k]) {
list[k + 1] = list[k];
--k;
}
list[k + 1] = newItem;
} //end insertInPlace
} //end class InsertSort2Test
1.4 Sorting a String Array
Consider the problem of sorting a list of names in alphabetical order. In Java, a name is stored in a String variable,
and we'll need a String array to store the list. For the most part, we can work with String as if it were a primitive
type, but it is sometimes useful to remember that, strictly speaking, it is a class. Where necessary, we will point out
the distinction.
One difference that concerns us here is that we cannot use the relational operators ( == , < , > , and so on) to
compare strings. We must use functions from the String class (or write our own). Common functions include equals ,
equalsIgnoreCase , compareTo , and compareToIgnoreCase . We write a function to sort an array of strings using
insertion sort. We call it insertionSort3 .
public static void insertionSort3(String[] list, int lo, int hi) {
//sort list[lo] to list[hi] in ascending order
for (int h = lo + 1; h <= hi; h++) {
String key = list[h];
int k = h - 1; //start comparing with previous item
while (k >= lo && key.compareToIgnoreCase(list[k]) < 0) {
list[k + 1] = list[k];
--k;
}
list[k + 1] = key;
} //end for
} //end insertionSort3