C++ generic insertion sort
I am creating this to try get a better understanding of sorting algorithms
and generic functions. I have implemented a basic insertion sort algorithm
and I am trying to make it work with multiple data structures (lists and
arrays at least).
Since I can access lists like this : list[N] to get the value, I think I
need to be using iterators. So I am trying to convert my solution. Here is
the basic insertion sort algorithm I am trying to modify:
int *insertionsort(int *a)
{
for (int i = 1; i<length(a); ++i)
{
int k = a[i];
int j = i-1;
{
while (j>=0 && a[j] > k)
{
a[j+1] = a[j--];
}
a[j+1] = k;
}
return a;
}
And here is what I have so far for the generic version:
template <class T>
T insertionsort(T a)
{
for (auto i = a.begin()+1; i<a.end(); ++i)
{
auto k = i;
auto j = i-1;
while (j>=a.begin() && *j>*k)
{
(j + 1) = j--;
}
(j + 1) = k;
}
return a;
}
Unfortunatley I can't seem to get this generic function to sort correctly
at all. I have been looking at this quite a while with no luck. Ideas?