swap()? (g++)

EDIT: This problem has been solved.


I didn't notice that "swap" identifier had been overloaded in bubblesort(). :blush: The error from g++ was rather cryptic, to say the least. Well, it's been solved. This thread may be closed/deleted/removed if necessary.





So here I am, trying to implement bubblesort (for fun, what else is bubblesort good for ):

Code:

template <classname>
void swap(classname &x, classname &y)
{
	classname temp = x;
	x = y;
	y = temp;
}

template <class iterator>
void bubblesort(iterator start, iterator end)
{
	bool swapped = true;
	iterator swap;
	for(iterator i = end; i != start && swapped; --i)
	{
		swapped = false;
		iterator j = start, k = start;
		++k;
		for(; k != i; ++j, ++k)
		{
			if(*k < *j)
			{
				swap(*j, *k);
				swapped = true;
			}
		}
	}
}

int main()
{
	int array[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
	bubblesort(array, array + 10);
}

In GCC it fails to compile:

Code:

In function `void bubblesort(iterator, iterator) [with iterator = int*]':
`swap' cannot be used as a function

Even when I specialize the functions to int types and int* iterators, it outputs more or less the same thing.

When I remove swap() completely, gcc again produces the same error "`swap' cannot be used as a function".

If you want it, here's is my build line:

Code:

g++.exe "test.cpp" -o "test.exe"
-W -ansi  -I"lib\gcc\mingw32\3.4.2\include" -I"include\c++\3.4.2\backward"
-I"include\c++\3.4.2\mingw32" -I"include\c++\3.4.2" -I"include" -L"lib" -s

I'm compiling from Dev-C++ using MinGW 3.4.2, by the way.

Note that there's a function in the standard library called swap() which does exactly what you want. This might lead to ambiguity errors on compilers that properly implement two-phase lookup if you sort anything from namespace std, such as std::string or std::complex. (Not that std::complex can be sorted ...)
Anyway, you should either
1) just use the std::sort function (it's optimized for various types, such as std::string) or
2) completely qualify the call to your swap() in bubblesort as ::swap(*j, *k).

I knew that. I just didn't want my sort algorithms to rely on the standard library. And I was re-implementing many major algorithms, for practice. I tried to make a variety of drop-in iterator-based std::sort replacements. I just finished a while ago, with introsort. That way, I've learned a lot about how shellsort and heapsort work, and how quicksort partitions in-place.

I put all the functions into a namespace sort{}, to avoid the conflicts you mentioned. I just didn't include them in the posted code.

Introsort is still around half as fast as std::sort! Well, that's a start, at least that means I'm already half as good as the standards commitee

Originally Posted by jafet

Introsort is still around half as fast as std::sort! Well, that's a start, at least that means I'm already half as good as the standards commitee

Introsort is what's behind std::sort so you may want to recheck your implementation.

Also, since std::sort runs at O(N log(N)) you will have an hard time predicting your algorithm speed against std::sort in such accurate terms as "half as fast"

As in "half" I meant the constant factor. As you know, big-O isn't so big at measuring those. I know it's half because I benchmarked both at varying input sizes. Haven't had time to test against quicksort killer sequences yet... prolly never will.