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

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]
insertionSort1(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

// insertionSort1 goes here

} //end class InsertSort1Test

1.2.1 Analysis of Insertion Sort
In processing item j , we can make as few as 1 comparison (if num[j] is bigger than num[j-1] ) or as many as j -1
comparisons (if num[j] is smaller than all the previous items). For random data, we would expect to make ½( j -1)
comparisons, on average. Hence, the average total number of comparisons to sort n items is:

∑ n
2

1

{ } ( )

2

( j −= + + +− = − ≈ 1) ½ 1 2 ... n 1 ¼ nn 1 ¼ n

2

j =

We say insertion sort is of order O(n 2 ) (“big O n squared”). The constant ¼ is not important as n gets large.
Each time we make a comparison, we also make an assignment. Hence, the total number of assignments is also
¼ n(n-1) » ¼ n 2 .
We emphasize that this is an average for random data. Unlike selection sort, the actual performance of insertion
sort depends on the data supplied. If the given array is already sorted, insertion sort will quickly determine this by
making n-1 comparisons. In this case, it runs in O(n) time. One would expect that insertion sort will perform better
the more order there is in the data.
If the given data is in descending order, insertion sort performs at its worst since each new number has to travel
all the way to the beginning of the list. In this case, the number of comparisons is ½ n(n-1) » ½ n 2 . The number of
assignments is also ½ n(n-1) » ½ n 2 .
Thus, the number of comparisons made by insertion sort ranges from n-1 (best) to ¼ n 2 (average) to ½ n 2 (worst).
The number of assignments is always the same as the number of comparisons.
As with selection sort, insertion sort does not require extra array storage for its implementation.
As an exercise, modify the programming code so that it counts the number of comparisons and assignments
made in sorting a list using insertion sort.