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

list[k + 1] = key;
} //end for
} //end insertionSort
} //end class InsertSortTest
The program requests up to ten numbers (as defined by MaxNumbers ), stores them in the array num , calls
insertionSort , and then prints the sorted list.
The following is a sample run of the program:
Type up to 10 numbers followed by 0
57 48 79 65 15 33 52 0
The sorted numbers are
15 33 48 52 57 65 79
Note that if the user enters more than ten numbers, the program will recognize this and sort only the first ten.
We could easily generalize insertionSort to sort a portion of a list. To illustrate, we rewrite insertionSort
(calling it insertionSort1 ) to sort list[lo] to list[hi] where lo and hi are passed as arguments to the function.
Since element lo is the first one, we start processing elements from lo+1 until element hi . This is reflected in the
for statement. Also now, the lowest subscript is lo , rather than 0 . This is reflected in the while condition k >= lo .
Everything else remains the same as before.
public static void insertionSort1(int list[], int lo, int hi) {
//sort list[lo] to list[hi] in ascending order
for (int h = lo + 1; h <= hi; h++) {
int key = list[h];
int k = h - 1; //start comparing with previous item
while (k >= lo && key < list[k]) {
list[k + 1] = list[k];
--k;
}
list[k + 1] = key;
} //end for
} //end insertionSort1
We can test insertionSort1 with Program P1.2a.
Program P1.2a
import java.util.*;
public class InsertSort1Test {
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();
}