Write a function
void InsertionSort( int InArray[ ], int N, int M );
Your function InsertionSort should sort an array of length L into
descending order. The array to be sorted is passed to it as an argument,
InArray. The algorithm to be implemented in the function
InsertionSort must be an insertion sort, as described below.
InsertionSort should work with a array of any size and with integer starting
and ending indices, N and M respectively. (i.e. don’t assume that the data to
be sorted starts in location 0 and fills the whole array, up to InArray(L-1) where L is the length of the array),
You may wish to sort a part of a larger array beginning with the nth
element of the larger array and ending with the mth
element of the array. InsertionSort should work with
an array of any size and with integer starting and ending indices, N and M
respectively.
To make the problem easier you may wish to begin by assuming N=0, and
M=L-1. This means that you are beginning by sorting the entire array from
location 0 to location L-1, not just part of it. When you have the function
working for this simpler condition then see if you can modify it to work in the
more general case of sorting any part of
the array between (and including) location N and location M. 0<=N,M<L
The insertion sort algorithm is similar to the way most people sort playing
cards, by starting with one card, and inserting each card in its proper place
in the hand, one by one. Before examining the ith element we can assume
that the preceding (i-1) elements are already sorted; then insert the ith
element into its proper place among the previously sorted elements. If we
follow this method for each element from the first to the last, then the entire
list will be sorted after we finish inserting the last element. The first
element is already sorted, so we can start our outer loop with the second
element of the array.
To insert the ith element into its proper place, we may need to move the
elements after (with larger index) it in the array down one space to make room
for it. For example, suppose we start with (85, 201, 202, 210, 35, 207, 102).
Consider the second element in the array. 201 is larger than the first element,
85
Shift 85 one location to the right and insert 201 into location 0
( 201, 85, 202, 210, 35, 207, 102)
Consider the third element in the array. Find the correct location of
202.
Notice that 202 is larger than 201, so it belongs in the first location. Shift
the first two elements one location to the right then insert 202 at location 0
( 202, 201, 85, 210, 35, 207, 102)
Consider the fourth element in the array. Find the correct location of
210.
Notice that 210 is larger than 202, so it belongs in the first location. Shift
the first three elements on location to the right the insert 210 at location
0.<>.<>
(210, 202, 201, 85, 35, 207, 102)
Consider the fifth element in the array. Find the correct location of 35.
Since 35 is less than all four elements preceding it, it is already in the
correct location.
(210, 202, 201, 85, 35, 207, 102)
<>Consider the sixth element in the array. Find the correct
location of 207.
Notice that 207 is smaller than 210 but larger than 202. Shift the four
elements 202, 201, 85 and 35 on location to the right, then inser 207 in
location 1
(210, 207, 202, 201, 85, 35, 102)
Consider the seventh element in the array. Find the correct location of
102.
Notice that 102 is smaller than 201 but larger than 85. Shift 85 and 35 to the
right then insert 102 in location 5.
(210, 207, 202, 201, 102, 85, 35)
This is the simplest algorithm of the insertion family. It is called a
straight insertion sort.
Write a main program to test your sorting function. Your main program
should
§ Prompt for and read the integers, M, N, and
L
§ Prompt for and read the integers to be sorted
(fill your array so that all locations with index <=M have values, your
array may contain more values than this but not less)
§ Display the array of integers to the screen
(only those with values)
§ Use your insertion sort function to sort the
integers into descending order
§ Display the array of sorted integers to the
screen (same array as displayed before, but now with the elements sorted)