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

1.3 Inserting an Element in Place
Insertion sort uses the idea of adding a new element to an already sorted list so that the list remains sorted. We can
treat this as a problem in its own right (nothing to do with insertion sort). Specifically, given a sorted list of items from
list[m] to list[n] , we want to add a new item ( newItem , say) to the list so that list[m] to list[n+1] are sorted.
Adding a new item increases the size of the list by 1. We assume that the array has room to hold the new item.
We write the function insertInPlace to solve this problem.
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
Using insertInPlace , we can rewrite insertionSort (calling it insertionSort2 ) as follows:
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
We can test insertionSort2 with Program P1.2b.
Program P1.2b
import java.util.*;
public class InsertSort2Test {
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);
}