The text discusses the selection sort. We propose a different “sort” routine, the insertion sort. This routine is in a sense the opposite of the selection sort in that it picks up successive elements from the array and inserts each of these into the correct position in an already sorted subarray (at one end of the array we are sorting).

The array to be sorted is divided into a sorted subarray and an

unexamined subarray. Initially, the sorted subarray is empty. Each

element of the unexamined subarray is picked and inserted into its correct position in the sorted subarray.

Write a function and a test program to implement the selection sort.

Thoroughly test your program.

Example and hints: The implementation involves an outside loop that

selects successive elements in the unsorted subarray and a nested loop

that inserts each element in its proper position in the sorted subarray.

Initially, the sorted subarray is empty, and the unsorted subarray is all of

the array:

Pick the first element, a[0] (that is, 8), and place it in the first position.

The inside loop has nothing to do in this first case. The array and

subarrays look like this:

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

8 6 10 2 16 4 18 14 12 10

sorted unsorted

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

8 6 10 2 16 4 18 14 12 10

The first element from the unsorted subarray is a[1], which has value 6.

Insert this into the sorted subarray in its proper position. These are out of

order, so the inside loop must swap values in position 0 and position 1.

The result is as follows:

Note that the sorted subarray has grown by one entry.

Repeat the process for the first unsorted subarray entry, a[2], finding a

place where a[2] can be placed so that the subarray remains sorted. Since

a[2] is already in place, that is, it is larger than the largest element in the

sorted subarray, the inside loop has nothing to do. The result is as

follows:

Again, pick the first unsorted array element, a[3]. This time the inside

loop has to swap values until the value of a[3] is in its proper position.

This involves some swapping:

sorted unsorted

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

6 8 10 2 16 4 18 14 10 12

sorted unsorted

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

6 8 10 2 16 4 18 14 10 12

sorted unsorted

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

6 8 10<-->2 16 4 18 14 10 12

sorted unsorted

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

6 8<--->2 10 16 4 18 14 10 12

sorted unsorted

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

6<--->2 8 10 16 4 18 14 10 12

The result of placing the 2 in the sorted subarray is

sorted unsorted

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

2 6 8 10 16 4 18 14 10 12

The algorithm continues in this fashion until the unsorted array is empty

and the sorted array has all the original array’s elements.