SEARCHING AND SORTING - Java Programming: From Problem Analysis to Program Design - page 913

For a list of length n, selection sort makes exactly n ð n 1 Þ

2 key comparisons and
3(n 1) item assignments. Therefore, if n ¼ 1000, then to sort the list, selection sort
makes about 500,000 key comparisons and about 3000 item assignments. The next
section presents the insertion sort algorithm that reduces the number of comparisons.

Insertion Sort
As noted in the previous section, for a list of length 1000, selection sort makes 500,000
key comparisons, which is quite high. This section describes the sorting algorithm called
the insertion sort, which attempts to reduce the number of key comparisons.
The insertion sort algorithm sorts a list by repeatedly inserting an element in its proper
place into a sorted sublist until the whole list is sorted. Consider the list shown in
Figure 14-5.

[0] [1] [2] [3] [4] [5] [6] [7]

list 10 18 25 30 23 17 45 35

FIGURE 14-5 List

The length of the list is 8 . In this list, the elements list[0] , list[1] , list[2] , and
list[3] are in order. That is, list[0]...list[3] is sorted (see Figure 14-6).

sorted list unsorted list

[0] [1] [2] [3] [4] [5] [6] [7]

list 10 18 25 30 23 17 45 35

FIGURE 14-6 Sorted and unsorted portion of list

Next, we consider the element list[4] , the first element of the unsorted list. Because
list[4] < list[3] , we need to insert the element list[4] in its proper location.
From this list, it follows that element list[4] should be moved to list[2] (see
Figure 14-7).

1
4