Vector sorting, Bubble-Sort problems

**Tynnhammar** · 09-22-2005

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?

**hk_mp5kpdw** · 09-22-2005

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.

**Tynnhammar** · 09-22-2005

I know their is a sort algorithm, but I'd like to implement one of my own, mostly for learning purposes.

**PJYelton** · 09-22-2005

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)

**Tynnhammar** · 09-22-2005

Thanks, PJYelton, that -> mistake was a silly one :P, however I don't understand what you mean by that iter2 should start on 1?

**PJYelton** · 09-22-2005

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)

**Tynnhammar** · 09-22-2005

I see, but it doesn't seem to sort at all :/

**PJYelton** · 09-22-2005

Repost your whole code.

**laserlight** · 09-23-2005

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.

**Tynnhammar** · 09-24-2005

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);
			}
		}
	}

};

**dwks** · 09-24-2005

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?

**Tynnhammar** · 09-27-2005

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.

**PJYelton** · 09-28-2005

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.

Thread: Vector sorting, Bubble-Sort problems

Thread Tools

Search Thread

Display

Vector sorting, Bubble-Sort problems

Similar Threads

How do I bubble sort alphabetically?

Bubble sort

Help With Bubble Sort

Sorting a string using bubble sort?!

bubble sort array of strings