# Vector sorting, Bubble-Sort problems

• 09-22-2005
Tynnhammar
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? :)
• 09-22-2005
hk_mp5kpdw
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.
• 09-22-2005
Tynnhammar
I know their is a sort algorithm, but I'd like to implement one of my own, mostly for learning purposes.
• 09-22-2005
PJYelton
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)`
• 09-22-2005
Tynnhammar
Thanks, PJYelton, that -> mistake was a silly one :P, however I don't understand what you mean by that iter2 should start on 1? :confused:
• 09-22-2005
PJYelton
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)`
• 09-22-2005
Tynnhammar
I see, but it doesn't seem to sort at all :/
• 09-22-2005
PJYelton
• 09-23-2005
laserlight
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.
• 09-24-2005
Tynnhammar
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);                         }                 }         } };```
• 09-24-2005
dwks
What's the result of the sort?

Quote:

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?
• 09-27-2005
Tynnhammar
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.
• 09-28-2005
PJYelton
Quote:

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.