Vector sorting, Bubble-Sort problems

This is a discussion on Vector sorting, Bubble-Sort problems within the C++ Programming forums, part of the General Programming Boards category; Hi guys, I'm trying to learn more about the power of using vectors as containers, however I've run into some ...

  1. #1
    Interested Newbie
    Join Date
    Sep 2004
    Location
    Sweden
    Posts
    51

    Vector sorting, Bubble-Sort problems

    Hi guys, I'm trying to learn more about the power of using vectors as containers, however I've run into some problems when trying to create a bubble sort algorithm.

    I think I'm on the right track, but I have a problem, the container vector is holding track of a struct SMovie, which looks like this:

    Code:
    struct SMovie
    {	
    	string Title;
    	string Year;
    	string Director;
    	string Description;
    };
    And I'm not sure how I should link them so they can be exchangable, because using this method; causes illegal indirection error:

    Code:
    void CContainer::Sort()
    {
    	// Sorts all the items by title name within the vector, with the help of the bubblesort algorithm
    	
    	for(iter = Container.begin(); iter < Container.end(); ++iter)
    	{
    		for(iter2 = Container.begin(); iter2 < Container.end(); ++iter2)
    		{
    			if(iter < iter2)
    			{
    				iter_swap((*iter),(*iter2));
    			}
    		}
    	}
    
    };
    Anyone?

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,806
    That is not a bubble sort. For one thing, your if test is not comparing items correctly. There are simpler ways to sort your container. You should either define/overload the less-than opertor (<) for your struct and then simply call the sort function defined in the algorithm header, or call the sort function and pass it a binary predicate function to call to determine whether one struct is less-than another struct.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Interested Newbie
    Join Date
    Sep 2004
    Location
    Sweden
    Posts
    51
    I know their is a sort algorithm, but I'd like to implement one of my own, mostly for learning purposes.

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Actually that is a different version of the bubble sort just not the one seen more often.

    Couple of problems. First off, your sort will not work properly because the second for loop starts at the beginning instead of iter+1. The second problem is you are comparing two iterators in your if loop which means you are comparing two pointer values, not the values they are pointing to. Need to derefence those first. Last, you can't compare two structs directly like that. You need to either overload the < operator or have your if statement written like this:
    Code:
    			if(iter->Title < iter2->Title)

  5. #5
    Interested Newbie
    Join Date
    Sep 2004
    Location
    Sweden
    Posts
    51
    Thanks, PJYelton, that -> mistake was a silly one :P, however I don't understand what you mean by that iter2 should start on 1?

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    For the bubble sort to work properly, the second for loop on the inside doesn't start at the beginning but instead starts one greater than the outside loop:
    Code:
    for(iter2 = iter + 1; iter2 != Container.end(); ++iter2)

  7. #7
    Interested Newbie
    Join Date
    Sep 2004
    Location
    Sweden
    Posts
    51
    I see, but it doesn't seem to sort at all :/

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Repost your whole code.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,313
    You might want to try a somewhat easier version of bubblesort:
    Code:
    swap_flag = true
    while swap_flag is true
    	swap_flag = false
    	loop from first position to second last position
    		if swap condition is true
    			swap element at current position with element at next position
    			swap_flag = true
    swap_condition can be something like "element at current position is greater than element at next position" (upon which the sorting will be done in ascending order). In your case, the swap condition would be "Title member variable of element at current position is greater than Title member variable of element at next position".

    You might also want to experiment with say, vectors of ints before you try using vectors of structs.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Interested Newbie
    Join Date
    Sep 2004
    Location
    Sweden
    Posts
    51
    Code:
    void CContainer::Sort()
    {
    	// Sorts all the items by title name within the vector, with the help of the bubblesort algorithm
    	
    	for(iter = Container.begin(); iter < Container.end(); ++iter)
    	{
    		for(iter2 = iter + 1; iter2 < Container.end(); ++iter2)
    		{
    			if(iter->Title < iter2->Title)
    			{
    				iter_swap(iter, iter2);
    			}
    		}
    	}
    
    };

  11. #11
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    What's the result of the sort?

    First off, your sort will not work properly because the second for loop starts at the beginning instead of iter+1.
    Won't that leave the first element unsorted?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  12. #12
    Interested Newbie
    Join Date
    Sep 2004
    Location
    Sweden
    Posts
    51
    Quote Originally Posted by dwks
    What's the result of the sort?


    Won't that leave the first element unsorted?
    The result is that nothing happens to the list.

  13. #13
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Won't that leave the first element unsorted?
    No, the outer for loop starts at the first element, the inner for loop always starts one ahead. So the first element gets sorted just like any other element.

    My best guess as to why its not working is because your for loop is comparing pointers. Instead of saying the iterator is less than the end, try using the not equal sign for both loops:
    Code:
    	for(iter = Container.begin(); iter != Container.end(); ++iter)
    Also, I'm not sure if you are aware of this but because you swap the elements when iter->Title is less than iter2->Title the items will be sorted backwards from Z to A instead of A to Z.
    Last edited by PJYelton; 09-28-2005 at 11:43 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How do I bubble sort alphabetically?
    By arih56 in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2008, 02:30 AM
  2. Bubble sort
    By Lionmane in forum C Programming
    Replies: 5
    Last Post: 07-09-2005, 12:30 PM
  3. Help With Bubble Sort
    By Explicit in forum C Programming
    Replies: 7
    Last Post: 05-28-2004, 09:46 AM
  4. Sorting a string using bubble sort?!
    By j0hnb in forum C Programming
    Replies: 6
    Last Post: 01-26-2003, 05:44 PM
  5. bubble sort array of strings
    By the_head in forum C Programming
    Replies: 1
    Last Post: 04-02-2002, 05:15 PM

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