Inserting Item In Template Array

[power_computer]

Ok, I have a given template class code the only thing we are to implement is inserting an item so that the template array list is still in ascending order my template passes the parameter of another class, this classes contains overloaded operators < > == based upon the win to total games played ratio the.

Here is the code for the insert template function

template class<elemType>
arrayList<elemtype>::insert(elemtype insertItem)
{
//code
}

They also have included this function

template<class elemType>
int arrayListTypeT<elemType>::seqSearch(elemType item)  const
{
    int i;
    for (i = length - 1; i >= 0; i--)
       if (list[i] == item)
       { break; }
    return i;
} //end seqSearch

Which I believe could be of use because the insert function is just updating an item in the list

[Tom Gunn]

There are three steps to inserting in an array:

1. Find the position of the item being inserted.
2. Make room for the new item by shifting all items from that position forward one spot to the right.
3. Copy the new item into the position that was vacated.

Graphically it looks like this:

Step 1, inserting 5:

[0][1][2][3][4][6][7][8][][][]
                ^

Step 2:

[0][1][2][3][4][6][6][7][8][][]
                ^

Step 3:

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

See if you can roll that up into an algorithm.