Thread: Good old 'Swap' function

Originally Posted by matsp

And, how does C++ do it "better"?

Templates of course:

Code:

template<typename T> void Swap(T& Arg1, T& Arg2)
{
	T Temp = Arg1;
	Arg1 = Arg2;
	Arg2 = Temp;
}

Yes, but it's only (a little bit) handier than the macro I wrote:

Code:

#define SWAP(T, A, B)   do { T temp = (A); (A) = (B); (B) = temp; } while(0)

Yes, the do-while stuff is a bit ugly, but that's about it.

And of course, you have to specify the type, and it doesn't work with arrays, before anyone else points that out.

--
Mats

But then you also have to specify type and it doesn't work with arrays, so C is still somewhat limited when it comes to stuff like this
And as we all know, debugging macros can be a pain, for one...

Originally Posted by Elysia

But then you also have to specify type and it doesn't work with arrays, so C is still somewhat limited when it comes to stuff like this
And as we all know, debugging macros can be a pain, for one...

Yeah, and debugging templates is trivial, right?

By the way gcc for example supports a typeof, so you can do:

Code:

#define SWAP(A, B) do { typeof(A) temp = A; A = B; B = temp } while(0)

--
Mats

Originally Posted by matsp

Yeah, and debugging templates is trivial, right?

It's easier, at least...

By the way gcc for example supports a typeof, so you can do:

Code:

#define SWAP(A, B) do { typeof(A) temp = A; A = B; B = temp } while(0)

But I'm guessing that's not standard, so if you want to rely on compiler specific extensions, then sure.

Originally Posted by matsp

Yes, but it's only (a little bit) handier than the macro I wrote:

Code:

#define SWAP(T, A, B)   do { T temp = (A); (A) = (B); (B) = temp; } while(0)

Yes, the do-while stuff is a bit ugly, but that's about it.

And of course, you have to specify the type, and it doesn't work with arrays, before anyone else points that out.

--
Mats

That can work with arrays, you just have to use the type of item in the array for T instead of the array type, and use the [] syntax for A and B.

However, it's still far inferrior to what you would use in C++:
if A or B have side effects then they get executed twice.
No support for copying of objects since you can't define an assignment operator.
Macros are evil and polluting.
You have to tell it the type, instead of letting the compiler handle that.
Explicit specialisations of swap can be given in C++ to allow certain objects to be swapped more efficiently. The caller doesn't have to care about this.
Debugging template code is not really harder than non-templated code, but debugging macros is much worse! (It's the compile-time errors that are the tricker part when it comes to template code)

Having said that, if I were forced to use C, I would do the same as above.

Code:

void Swap(void** pA, void** pB)
{
	void* pTemp = *pA;
	*pA = *pB;
	*pB = pTemp;
}

I believe that's how it should be, yes? That's what happens when you post code that you don't test...
Btw, use Firefox + Tab in Textarea extension. This will allow you to use tabs in the editor!
Otherwise just write the code in your IDE and copy it here.

I'd say that without knowing what type of data you're sorting, you can't sort. Or at least I'm tempted to say so. It will probably behave wrong when sorting one type and right when sorting one.

The way that the library function qsort() solves this problem is by calling back to a function that compares the two items - just pass the address of your two items to the a function

Code:

int comparefunc(void *a, void *b);

This function should return an integer that is less than, equal to or greater than zero if a is less than, equal to or greater than b.

Sine the compare function is given by the caller, you don't have to pass a size, as the caller of the sort function should know what type to cast a and b into.

--
Mats

You can improve Bubblesort beyond using a mere boolean flag!

In C++ I'd do it like this:

Code:

template <class T>
void BubbleSort(T a[], int n) {
	int sinker = n-1;
	do {
		int floater = 0;
		for (int i = 0; i < sinker; ++i) {
			if (a[i + 1] < a[i]) {
				Swap(a[i], a[i + 1]);
				floater = i;
			}
		}
		sinker = floater;
	} while (sinker > 0);
}

Bear in mind that your effort to sort things will always be rather a learning experience than an improvement on anything existing - the C environment has a qsort/heapsort implemented in the standard library, and C++ has a couple of sort mechanisms "ready to use" already too. It's quite unlikely that you will improve on these two - but it's a great learning experience to try it out, especially to make it work for "all types".

--
Mats