CHAPTER 7 / Arrays 6. 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 to-be-sorted subarray. Initially, the sorted subarray is empty. Each element of the to-be-sorted 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 se- lects successive elements in the to-be-sorted subarray and a nested looD that inserts each element in its proper position in the sorted subarray Initially, the sorted subarray is empty, and the to-be-sorted subarray is all of the array: 6 10 16 4 10 Pick the first element, a[O] (that is, 8), and place it in the first posi tion. The inside loop has nothing to do in this first case. The array and subarrays look like this: sorted to-be-sorted 8 6 10 4 14 12 10 The firstelement from the to-be-sorted subarray is a [1], which hasvalue 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: sorted to-be-sorted 6 8 10 16 4 18 14 10 12