Implementing selection sort with vectors

Question

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.

Why do you use sometimes indexed access, sometimes at? (Hint: don’t use the latter.) — Konrad Rudolph
– Konrad Rudolph, Commented Feb 8, 2012 at 19:57

Robert Kelly · Accepted Answer · 2012-02-08 19:48:21Z

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)

edited Feb 8, 2012 at 19:48

answered Feb 8, 2012 at 19:21

Robert Kelly

1,0061 gold badge11 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Stephan Dollberg Over a year ago

maybe change the pos < 30 to pos < v.size()

user670595 Over a year ago

Thank you for this. I should of caught that. Sometimes it is the simple things that we miss.

Andreas Magnusson · Accepted Answer · 2012-02-08 19:23:54Z

0

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

answered Feb 8, 2012 at 19:23

Andreas Magnusson

7,4343 gold badges34 silver badges37 bronze badges

Collectives™ on Stack Overflow

Implementing selection sort with vectors

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related