Implementing selection sort with vectors

问题:

I am attempting to implement a function that sorts a randomly generated vector using selection sort. I am trying a naive way just to see if I can get it working correctly. Here is my attempt:

void selection_sort(std::vector<int>& v)
{
    int pos, min, i;
    //std::vector<int>::iterator pos, min, i;

    for( pos = v[0]; pos < v[30]; ++pos)
    {
        min = pos;

        for( i = v[pos + 1]; i < v[30]; ++i)
        {   
            if( i < min)
            {
                min = i;
            }
        }

        if( min != pos)
        {   
            std::swap(v.at(min), v.at(pos));

        }
    }
}

For some reason however when I display the vector again, all of the elements are in the exact same order as they were originally. I am not sure if I am not using std::swap correctly or if my selection sort is not written correctly. I am sure the answer is trivially easy, but I can not see it. Thanks for your help in advance.

回答1:

Your problem is that you're trying to base your loops around the actual values in the vector, not the indexes in the vector.

So if your vector is randomly generated, and you say this:

for( pos = v[0]; pos < v[30]; ++pos)

There is a chance that the value at v[0] is greater than v[30]. Thus the loop would never run. I see the same problem in this loop:

for( i = v[pos + 1]; i < v[30]; ++i)

So I'd recommend using indexes for the actual looping. Try something like:

for( pos = 0; pos < 30; ++pos)
{
  min = v[pos];

etc...

EDIT: As mentioned below, it would also be better to base your loop of the size of the of the vector. However, to save your self from calling the expensive size() method every time the loops runs, just grab the size before the loop starts. For example:

size_t size = v.size();
for(size_t pos = 0; pos < size; ++pos)

回答2:

You should use 0, pos+1 and v.size() as end points in your for-loops.