Need help with Insertion-sort implementation.

[emptymind]

So I am a self-taught programmer and am trying to read the algorithms book CLRS. The first major algorithm covered is Insertion-sort. All the algorithms in the book are presented in pseudo-code. I thought a good exercise would be to implement all the algorithms in C++. I just started learning C++ and am having a really difficult time. I know some other programming languages like Java, LISP, and Python. I have a math degree and want to work in computer graphics. So I must get better at C++. So aside from helping me with this code, any advice is welcome as well.
I am getting errors saying vector does not have a type on line 4. On line 19 "'vector' was not declared in this scope", "expected primary expression before int", and "epectected ';' before 'int'". Thank you

#include<iostream>
#include<vector>

vector<int> Insertion_sort(vector<int> A)   {
    for(int i=2;i<A.size();++i) {
        int key=i;
        int i=i-1;

        while(i>0&&A(i)>key)    {
            A(i+1)=A(i);
            --i;
        }
        A(i+1)=key;
    }
    return A;
}

int main()  {
    vector<int> B(6);
    for(int i=B.size()-1;i>=0;--i)    {
        B(i)=6-i;
    }
    Insertion_sort(B);
    for(int i=0;i<B.size();++i) {
        cout<<"B["<<i<<"] = "<<B(i)<<"\n";
    }
}

[LendraDwi]

You'll need to use std::vector to declare vector (I thnk) then use at(x) to acces value at x

[Duthomhas]

That's not an insertion sort. It mixes indices and values, and clobbers data.

Remember, an index into the array tells you where some value is.
A value is what you are sorting relative to other values.
They are different types of things, and cannot be mixed.

You need to read up on how an insertion sort works:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/#algorithm

The algorithm works by treating an entire array as having two parts:
- stuff in the front is sorted
- stuff in the back is not sorted

That means you only need to modify an existing array -- you do not need to create additional arrays. Hence, your function should look like:

void Insertion_sort(vector<int> &A)
{
    // sort A here
}

(No need to return anything.)

For the actual sorting, you'll need to do two things:

  1 - search for the next value in the unsorted part of the array.
      (This is the same thing you did in earlier assignments where you had to
      find the smallest value in an array.)

  2 - swap the value (just found) to its final location (the beginning of
      the unsorted part).

This is illustrated nicely for you in the link:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/insertion-sort/#algorithm

Be careful what you are comparing. Remember the find-minimum type homeworks.

Good luck!