Problems with Insertion Sort Algorithm

[kuriolis]

Hello,

I have to implement insertion sort for an assignment, and I have an algorithm that aught to work (as far as I can tell), but is giving me trouble. I should also mention that we're using a template class in the assignment, though I doubt that would make a difference. First, here's the code:

vector<T>::size_type startIndex, minIndex, position;
    T temp;

for(startIndex=1; startIndex < v.size(); startIndex++)
    {
        minIndex = startIndex-1;
        temp = v.at(startIndex);

        while((minIndex >= 0) && (temp < v.at(minIndex)))
        {
            v.at(minIndex+1) = v.at(minIndex);
            minIndex--;

        }
        v.at(minIndex+1) = temp;
    }

The problem is that, if I leave the first comparison in the while loop condition as minIndex >= 0, I get a runtime error and the program crashes. But as far as I can see, that's the way it should be.

If I change the condition to ]minIndex > 0, I no longer have a run time error, and the sorting works properly EXCEPT that the first value in the vector is skipped.

I can't see why that condition should be giving me an error. I also can't see another way to make the code work properly.

If anyone can see anything I might be missing, I'll greatly appreciate it. :)

[Cubbi]

Personally, I like writing insertion sort in C++ simply as

for (auto i = v.begin(); i != v.end(); ++i)
    std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);

(it's faster than the nested loops approach, too, since it uses binary search to find the insertion point)

As for your program, load it in a debugger and step through to see when the values of your variables begin disagreeing with what you expected.

As written, your inner loop starts with minIndex==0, decrements it on the first iteration from zero to SIZE_MAX (remember, size_type is always unsigned), and before the second iteration begins, it throws in the loop condition in v.at(minIndex), which is now out of bounds.