Insertion sort problem...

This is a discussion on Insertion sort problem... within the C++ Programming forums, part of the General Programming Boards category; I want to use insertion sort to sort a vector containing some classes. Each class has a string name variable ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    39

    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.

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,739
    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;
    }

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    39
    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.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,739
    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.
    Last edited by whiteflags; 05-26-2008 at 11:48 PM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    Last edited by iMalc; 05-27-2008 at 12:59 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem with gets and bubble sort
    By wwwildbill in forum C Programming
    Replies: 4
    Last Post: 04-04-2009, 01:31 AM
  2. Shell Sort with Vectors Problem
    By TheSpoiledMilk in forum C++ Programming
    Replies: 4
    Last Post: 11-22-2005, 02:05 PM
  3. Replies: 5
    Last Post: 11-07-2005, 10:34 PM
  4. netonotisr inor (insertion sort)
    By The Brain in forum C++ Programming
    Replies: 0
    Last Post: 05-04-2005, 03:11 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21