Polymorphism - Java Software Solutions: Foundations of Program Design - page 512

Similar to the selection sort implementation, the insertionSort method
uses two for loops to sort the array. In the insertion sort, however, the outer
loop controls the index in the array of the next value to be inserted. The inner
loop compares the current insert value with values stored at lower indexes
(which make up a sorted subset of the entire list). If the current insert value
is less than the value at position , that value is shifted to the right. Shifting
continues until the proper position is opened to accept the insert value. Each
iteration of the outer loop adds one more value to the sorted subset of the list,
until the entire list is sorted.
Comparing Sorts
There are various reasons for choosing one sorting algorithm over another,
including the algorithm's simplicity, its level of efficiency, and the amount of
memory it uses. An algorithm that is easier to understand is also easier to imple-
ment and debug. However, often the simplest sorts are the most inefficient ones.
Efficiency is usually considered to be the primary criterion when comparing sort-
ing algorithms. In general, one sorting algorithm is less efficient than another if it
performs more comparisons than the other. There are several algorithms that are
more efficient than the two we examined, but they are also more complex.
Both selection sort and insertion sort have essentially the same level of effi-
ciency. Both have an outer loop and an inner loop with similar properties, if not
purposes. The outer loop is executed once for each value in the list, and the inner
loop compares the value in the outer loop with most, if not all, of the values in
the rest of the list. Therefore, both algorithms perform approximately n 2 number
of comparisons, where n is the number of values in the list. We say that both
selection sort and insertion sort are algorithms of order n 2 . More efficient sorts
perform fewer comparisons and are of a smaller order, such as n log 2 n .
Because both selection sort and insertion sort have the same general efficiency,
the choice between them is almost arbitrary. However, there are some additional
issues to consider. Selection sort is usually easy to understand and will often suf-
fice in many situations. Further, each value moves exactly once to its final place
in the list. That is, although the selection and insertion sorts are equivalent (gener-
ally) in the number of comparisons made, selection sort makes fewer swaps.
SELF-REVIEW QUESTIONS (see answers in Appendix N)
SR 10.12 Describe the Comparable interface.
SR 10.13 Show the sequence of changes the selection sort algorithm makes to
the following list of numbers:
5 7 1 8 2 4 3