16

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?
Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Svish
  • 152,914
  • 173
  • 462
  • 620

7 Answers7

29

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.

Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
6

11 years later and we have tuples...

(foo, bar) = (bar, foo);
gaggleweed
  • 204
  • 3
  • 5
  • 1
    Welcome to SO, @gaggleweed, and thanks for the good contribution! One note: The OP asked for the swap functionality to be buried within a method, but your code does the swap directly inline. I can see why it would seem unnecessary to put such a simple one-liner in a method, but it would be good to explain that in the post if that's what you were thinking. Or better yet, explain that *and* include a version that has it in a method, just in case the OP has a good reason for wanting it that way. – sfarbota Jan 26 '20 at 03:48
  • It's also worth noting that this is not thread-safe, but that would only matter if you were swapping variables that are shared beyond the local scope. – sfarbota Jan 26 '20 at 03:49
3

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

LoxLox
  • 977
  • 9
  • 16
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.

dirkgently
  • 108,024
  • 16
  • 131
  • 187
  • 3
    But for an int[] or List, the contents are either the same (x86) or half the size (x64). In this case, swap the contents. – Marc Gravell Feb 16 '09 at 09:39
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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Joe
  • 45
  • 1
  • 2
  • Interesting... what do those comments mean? – Svish Jan 04 '10 at 13:32
  • 5
    (And is that `return;` really needed?) – Svish Jan 04 '10 at 13:37
  • return is not needed, and you would use ref instead of & yes, +1 – Ric Tokyo Mar 23 '11 at 00:31
  • &a != &b basically means method assumes that address of variable a is different from address of variable b. In terms of C# you may think that you didn't call swap(ref a, ref a). While it is will work - don't know why author assumes that thing, probably just defensiveness of old-school C++ developer :) The second comment explains that equality of variables' values is OK. – Ivan Danilov Jun 14 '11 at 04:49
  • 2
    FWIW, Wikipedia claims that this method is actually less efficient than the usual `buffer = a; a = b; b = buffer;` construct. –  Dec 12 '11 at 13:50
  • 2
    Benchmarks show that indeed temp variable swap is faster than 3 XOR operations in C#. – Firestrand Aug 05 '13 at 15:18
  • @Ivan Danilov: No, it will definitely not work. It you call `swap(ref a, ref a)`, the expected result is that a remains unchanged. The actual result of this swap function will always be a == 0. – Paul Groke May 24 '14 at 17:15
  • @PaulGroke It will work under assumption that a and b are not same. I said that I don't know why author made this assumption in the first place - and of course your example shows the case when it won't. – Ivan Danilov May 24 '14 at 18:28
0

You can now use tuples to accomplish this swap without having to manually declare a temporary variable:

static void Swap<T>(ref T foo, ref T bar)
{
    (foo, bar) = (bar, foo)
}
C Bergs
  • 71
  • 7
-1

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);
Tuukka Lindroos
  • 1,270
  • 10
  • 14