C#: Good/best implementation of Swap method

Question

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 efficient Swap method look like?

Let's 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?

Answer 1

Well, the code you have posted (ref cards[n]) can only work with an array (not a list) - but you would use simply (where foo and bar are the two values):

static void Swap(ref int foo, ref int bar) {
    int tmp = foo;
    foo = bar;
    bar = tmp;
}

Or possibly (if you want atomic):

Interlocked.Exchange(ref foo, ref bar);

Personally, I don't think I'd bother with a swap method, though - just do it directly; this means that you can use (either for a list or for an array):

int tmp = cards[n];
cards[n] = cards[i];
cards[i] = tmp;

If you really wanted to write a swap method that worked on either a list or an array, you'd have to do something like:

static void Swap(IList<int> list, int indexA, int indexB)
{
    int tmp = list[indexA];
    list[indexA] = list[indexB];
    list[indexB] = tmp;
}

(it would be trivial to make this generic) - however, the original "inline" version (i.e. not a method) working on an array will be faster.

Answer 2

Use:

void swap(int &a, int &b)
{
    // &a != &b
    // a == b OK
    a ^= b;
    b ^= a;
    a ^= b;
    return;
}

I did not realize I was in the C# section. This is C++ code, but it should have the same basic idea. I believe ^ is XOR in C# as well. It looks like instead of & you may need "ref"(?). I am not sure.

Answer 3

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.

Answer 4

What about this? It's a generic implementation of a swap method. The Jit will create a compiled version ONLY for you closed types so you don't have to worry about perfomances!

/// <summary>
/// Swap two elements
/// Generic implementation by LMF
/// </summary>
public static void Swap<T>(ref T itemLeft, ref T itemRight) {
    T dummyItem = itemRight;
    itemLeft = itemRight;
    itemRight = dummyItem;
}

HTH Lorenzo

Answer 5

For anyone wondering, swapping can also be done also with Extension methods (.NET 3.0 and newer).

In general there seems not to be possibility to say that extension methods "this" value is ref, so you need to return it and override the old value.

public static class GeneralExtensions {
    public static T SwapWith<T>(this T current, ref T other) {
        T tmpOther = other;
        other = current;
        return tmpOther;
    }
}

This extension method can be then used like this:

int val1 = 10;
int val2 = 20;    
val1 = val1.SwapWith(ref val2);