Moving along in the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne, I experimented with the Insertion sort algorithm. Visit the https://en.wikipedia.org/wiki/Insertion_sort web site to view an animation of the algorithm. As you can see, it resembles a person arranging playing cards for a game of bridge.
The way the authors described the API to the sorting algorithms allow this one to be quite elegant and compact.
Following is the contents of the c:\temp\numbers.txt file:
C:\Temp> type numbers.txt
6 5 3 1 8 7 2 4
The file contains eight numbers.
Let’s take a look at the output in the console of the Eclipse IDE:
readStrings <<< al.size: 8
show <<< a: 6 5 3 1 8 7 2 4
show <<< a: 5 6 3 1 8 7 2 4
show <<< a: 3 6 5 1 8 7 2 4
show <<< a: 1 6 5 3 8 7 2 4
show <<< a: 1 6 5 3 8 7 2 4
show <<< a: 1 6 5 3 8 7 2 4
show <<< a: 1 6 5 3 8 7 2 4
show <<< a: 1 6 5 3 8 7 2 4
show <<< a: 1 6 5 3 8 7 2 4
show <<< a: 1 5 6 3 8 7 2 4
show <<< a: 1 3 6 5 8 7 2 4
show <<< a: 1 3 6 5 8 7 2 4
show <<< a: 1 3 6 5 8 7 2 4
show <<< a: 1 2 6 5 8 7 3 4
show <<< a: 1 2 6 5 8 7 3 4
show <<< a: 1 2 6 5 8 7 3 4
show <<< a: 1 2 5 6 8 7 3 4
show <<< a: 1 2 5 6 8 7 3 4
show <<< a: 1 2 5 6 8 7 3 4
show <<< a: 1 2 3 6 8 7 5 4
show <<< a: 1 2 3 6 8 7 5 4
show <<< a: 1 2 3 6 8 7 5 4
show <<< a: 1 2 3 6 8 7 5 4
show <<< a: 1 2 3 6 8 7 5 4
show <<< a: 1 2 3 5 8 7 6 4
show <<< a: 1 2 3 4 8 7 6 5
show <<< a: 1 2 3 4 8 7 6 5
show <<< a: 1 2 3 4 7 8 6 5
show <<< a: 1 2 3 4 6 8 7 5
show <<< a: 1 2 3 4 5 8 7 6
show <<< a: 1 2 3 4 5 8 7 6
show <<< a: 1 2 3 4 5 7 8 6
show <<< a: 1 2 3 4 5 6 8 7
show <<< a: 1 2 3 4 5 6 8 7
show <<< a: 1 2 3 4 5 6 7 8
show <<< a: 1 2 3 4 5 6 7 8
readStrings <<< al.size: 8
show <<< a: 5 6 3 1 8 7 2 4
show <<< a: 5 3 6 1 8 7 2 4
show <<< a: 3 5 6 1 8 7 2 4
show <<< a: 3 5 1 6 8 7 2 4
show <<< a: 3 1 5 6 8 7 2 4
show <<< a: 1 3 5 6 8 7 2 4
show <<< a: 1 3 5 6 7 8 2 4
show <<< a: 1 3 5 6 7 2 8 4
show <<< a: 1 3 5 6 2 7 8 4
show <<< a: 1 3 5 2 6 7 8 4
show <<< a: 1 3 2 5 6 7 8 4
show <<< a: 1 2 3 5 6 7 8 4
show <<< a: 1 2 3 5 6 7 4 8
show <<< a: 1 2 3 5 6 4 7 8
show <<< a: 1 2 3 5 4 6 7 8
show <<< a: 1 2 3 4 5 6 7 8
The Selection sort seems to take more steps than the Insertion sort 
algorithm. Both run on average O(n ^ 2). When using the larger file the difference becomes obvious as illustrated by the following console output:
readStrings <<< al.size: 4411
main <<< Selection elapsed: 366 ms
readStrings <<< al.size: 4411
main <<< Insertion elapsed: 109 ms
The test code in Java follows:
package john.canessa.sort;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class Sort {
/*
* read strings from the specified file
*/
static String[] readStrings(String fileName) throws FileNotFoundException {
File file = new File(fileName);
if ((!file.exists()) || (file.isDirectory())) {
throw new FileNotFoundException(“readStrings <<< fileName ==>” + fileName + “fileName”);
}
Scanner sc = new Scanner(file);
ArrayList<String> al = new ArrayList<String>();
while (sc.hasNext()) {
al.add(sc.next().toLowerCase());
}
sc.close();
System.out.println(“readStrings <<< al.size: ” + al.size());
String[] a = new String[al.size()];
// System.out.print(“readStrings <<< a: “);
// for (String s : al) {
// System.out.print(s + ” “);
// }
// System.out.println();
return a = al.toArray(a);
}
/*
* test
*/
public static void main(String[] args) throws Exception {
final String fileName = “c:\\temp\\document.txt”;
// final String fileName = “c:\\temp\\numbers.txt”;
boolean done = false;
int i = 0;
do {
switch (i++) {
case 0:
// **** read the array of strings ****
String[] a = readStrings(fileName);
// **** allocate the Selection sort object ****
Selection selection = new Selection();
// **** sort the array ****
long begin = System.currentTimeMillis();
selection.sort(a);
long end = System.currentTimeMillis();
// **** determine if the array is not sorted ****
if (!selection.isSorted(a)) {
throw new Exception(“array not sorted”);
}
// **** show the sorted array ****
// selection.show(a);
System.out.println(“main <<< Selection elapsed: ” + (end – begin) + ” ms”);
break;
case 1:
// **** read the array of strings ****
a = readStrings(fileName);
// **** allocate the Insertion sort object ****
Insertion insertion = new Insertion();
// **** sort the array ****
begin = System.currentTimeMillis();
insertion.sort(a);
end = System.currentTimeMillis();
// **** determine if the array is not sorted ****
if (!insertion.isSorted(a)) {
throw new Exception(“array not sorted”);
}
// **** show the sorted array ****
// insertion.show(a);
System.out.println(“main <<< Insertion elapsed: “ + (end – begin) + ” ms”);
break;
default:
done = true;
break;
}
} while(!done);
}
}
Following is the code for the Insertion sort:
package john.canessa.sort;
public class Insertion {
/*
* constructor
*/
public Insertion() {
}
/*
* sort array
*/
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = i; (j > 0) && less(a[j], a[j – 1]); j–) {
exch(a, j, j – 1);
// show(a);
}
}
}
/*
* exchange the elements in array
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/*
* show the array
*/
public static void show(Comparable[] a) {
System.out.print(“show <<< a: “);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ” “);
}
System.out.println();
}
/*
* determine if v is less than w
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/*
* determine if the array is sorted or not
*/
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i – 1])) {
return false;
}
}
return true;
}
/*
* test code
*/
public static void main(String[] args) {
}
}
Look at the simplicity and elegance used to implement the sort() method.
I started from scratch on the code for Insertion sort. Put in the methods specified in the API. Then I implemented them making some mistakes. Eventually all worked. I strongly suggest you do the same to fully understand the algorithm and the approach suggested by the authors of the book.
If you have comments or questions, please do not hesitate send me a message via email.
John
john.canessa@gmail.com