Problems with Insertion Sort Algorithm

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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. :)
Personally, I like writing insertion sort in C++ simply as

1
2
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.

Last edited on
Topic archived. No new replies allowed.