views:

2898

answers:

3

I read this post about card shuffling and in many shuffling and sorting algorithms you need to swap two items in a list or array. But what does a good and effecient Swap method look like? Lets say for a T[] and for a List<T>. How would you best implement a method that swaps two items in those two?

Swap(ref cards[i], ref cards[n]);   // How is Swap implemented?
+7  A: 
Marc Gravell
Interlocked.Exchange?
Svish
How would it work with an array?
Svish
Strike the exchange...
Marc Gravell
Re the array - you aren't *passing* the array - you are passing the element.
Marc Gravell
If these are integers, wouldn't it be better to just swap by value?
Dmitri Nesteruk
@Dmitri - I am swapping by value...
Marc Gravell
The int was just meant as an example though. should probably clear that up in the question...
Svish
but thanks for clear answer :)
Svish
Pretty easy to add generics to the above...
Marc Gravell
Why cross the Interlocked.Exchange?
Joan Venge
I honestly can't remember... there was probably a reason...
Marc Gravell
A: 

A good swap is one where you don't swap the contents. In C/C++ this would be akin to swapping pointers instead of swapping the contents. This style of swapping is fast and comes with some exception guarantee. Unfortunately, my C# is too rusty to allow me to put it in code. For simple data types, this style doesn't give you much. But once you are used to, and have to deal with larger (and more complicated) objects, it can save your life.

dirkgently
But for an int[] or List<int>, the contents are either the same (x86) or half the size (x64). In this case, swap the contents.
Marc Gravell
+1  A: 
void swap(int &a, int &b)

    { // &a != &b
      //  a ==  b OK 
     a ^= b;
     b ^= a;
     a ^= b;
     return;
    }

edit: did not realize i was in c# section. is c++ code but should have same basic idea. Believe ^ is XOR in c# as well. looks like instead of & you may need "ref"? not sure.

Joe
Interesting... what do those comments mean?
Svish
(And is that `return;` really needed?)
Svish