Insertion sort problem...

I want to use insertion sort to sort a vector containing some classes. Each class has a string name variable like this:

Code:

class myClass {
  string name;
  ...
}

I want to sort the vector by the names contained in the classes. I tried something like this:

Code:

vector<myVector> insertionSort(vector<myVector> v) {
  vector<myVector>::const_iterator itr, temp;
  int i, size = v.size();

  for( i = 1, itr = v.begin(); i < size; i++ ) {
    temp = itr;
    itr++;
    while( itr->getName().compare(temp->getName()) < 0 )
      temp->swapName(itr->getName());
  }

  return v;
}

The code runs but doesn't sort correctly by name. swapName() is simply does this:

Code:

void myClass::swapName(string n) {
  name.swap(n);
}

Any help is appreciated.

Well you didn't really write an insert sort, so that would be the problem. This does work, though.

Code:

template <class type>
void insertsort ( std::vector<type> & v )
{
    std::vector<type>::size_type i;
    for ( i = 1; i < v.size(); i++ ) {
        std::vector<type>::size_type j = i;
        type save( v[i] );

        while ( j > 0 && v[j - 1] >= save ) { // until one is smaller
            v[j] = v[j - 1];                  // shift right
            j--;
        }
        v[j] = save;                          // insert it sorted
    }
    return;
}

How would you do this using iterators? I need to learn how to do it this way, I think this is what's confusing me from most of the insertion sort examples I've seen using arrays.

If you know the type of iterator that vectors use, it shouldn't be that difficult to figure out. Those iterators are usually implemented as pointers, so you'll need to think of them in that context.

Set the (two) iterators you'll need to the same positions as the index values would indicate from where you start, and use them in much the same way you would the index values. It should work. I'll leave implementing insert sort with iterators to you.

Don't mix indexes and iterators. You should use only iterators, or only indexes. In this case you should only use iterators. That means no calls to size(), and no use of ints at all. As it happens, a for-loop may not be the best for an outer loop.
During any point in the sorting you should have the following:

1. An iterator to the start of the sorted portion
2. An iterator to one-past the end of the sorted portion
3. An iterator to the start of the unsorted portion
4. An iterator to one-past the end of the unsorted portion

Now in this case:
1 is simply v.begin()
2 and 3 are the same thing and would be the iterator that is advanced by the outer loop. This should start at, begin()+1, and you stop when it equals v.end(). However any good sorting algorithm must also not crash upon being asked to sort an empty data set, so you should check for that condition first.
4 is simply v.end()
Easy so far...
Now the insertion part:
To perform the insertion via repeated swaps this loop isn't quite right:

Code:

    while( itr->getName().compare(temp->getName()) < 0 )
      temp->swapName(itr->getName());

First of all, if the names compare as equal you'll get an infinite loop. The next thing to notice is that once a single swap is performed in this loop then the next time you're comparing the same two items, which is not what you want. You also need to swap the entire class objects, not just the names, and you also need to adjust the iterators. I'll let you try and work out that bit, but it should only be two lines of code. If you only swap the names then you'll end up with "people" that have the right details but someone else's name, or the right name but the wrong details.
Next the loop also needs to correctly terminate if the item being inserted is less than all other items. If you reach v.begin() inside the inner loop then you have to stop!

See how far that help gets you.