Array.Reverse algorithm?

What kind of algorithm Array.Reverse(s开发者_StackOverflow中文版tring a), uses behind the scene to reverse the string?

UPDATE: See the bottom of this answer for one truly horrifying ramification of reversing a string in-place in .NET.

"Good" Answer

In .NET, there's no Array.Reverse overload that takes a string. That said, here's how one might be implemented if it were to exist:

static string ReverseString(string str) {
    char[] reversed = new char[str.Length];
    for (int i = 0; i < reversed.Length; ++i)
        reversed[i] = str[str.Length - 1 - i];
    return new string(reversed);
}

Note that in .NET this method has to return a string, since the System.String type is immutable and so you couldn't reverse one in-place.

Scary Answer

OK, actually, it is possible to reverse a string in-place in .NET.

Here's one way, which requires compiling in unsafe mode:

static unsafe void ReverseString(string str) {
    int i = 0;
    int j = str.Length - 1;

    fixed (char* fstr = str) {
        while (i < j) {
            char temp = fstr[j];

            fstr[j--] = fstr[i];
            fstr[i++] = temp;
        }
    }
}

And here's another way, which uses reflection and does not need to be compiled in unsafe mode:

static void ReverseString(string str) {
    int i = 0;
    int j = str.Length - 1;

    // what a tricky bastard!
    MethodInfo setter = typeof(string).GetMethod(
        "SetChar",
        BindingFlags.Instance | BindingFlags.NonPublic
    );

    while (i < j) {
        char temp = str[j];

        setter.Invoke(str, new object[] { j--, str[i] });
        setter.Invoke(str, new object[] { i++, temp });
    }
}

Totally inadvisable and reckless, yes -- not to mention that it would likely have horrendous performance. But possible nonetheless.

The Horror

Oh, and by the way, in case there's any doubt in your mind whatsoever that you should never do anything like this: be aware that either of the ReverseString methods I've provided above will actually allow you to write the following utterly bizarre program:

ReverseString("Hello!");
Console.WriteLine("Hello!");

The above code will output, believe it or not*:

!olleH

So yeah, unless you want all hell to break loose in your code, don't reverse a string in-place. Even though technically you can ;)

_{*You can try it for yourself if you don't believe me.}

Probably a standard in-place reversal algorithm.

function reverse-in-place(a[0..n])
 for i from 0 to floor(n/2)
     swap(a[i], a[n-i])

Sources

• Wikipedia/In-place algorithm

The algorithm is probably using two pointers i and j that start at 0 and length-1 respectively. Then the characters at position i and j are swapped (with the help of a temporal variable) and i is incremented and j decremented by 1. These steps are repeated until both pointers reach each other (i ≥ j).

In pseudo-code:

i := 0;
j := a.length-1;
while (i < j) do
    tmp := a[i];
    a[i] := a[j];
    a[j] := tmp;
    i := i+1;
    j := j-1;
endwhile;

According to Reflector, Array.Reverse(Array) (there's no string variation) first calls something called TrySZReverse, for which I can't find the implementation. I assume it's some sort of heavily optimized native method..

If that fails, it does something like this:

int num = index;
int num2 = (index + length) - 1;
while (num < num2)
{
    object obj2 = objArray[num];
    objArray[num] = objArray[num2];
    objArray[num2] = obj2;
    num++;
    num2--;
}

So, an in place algorithm, where it swaps the values at each end, then moves inward, repeatedly.

Here's a general-purpose, language-independent, question-appropriate answer: It copies the input string to the output string, reading from one end and writing to the other.

My suggestion:

    private string Reverse(string text)
    {
        char[] c = text.ToCharArray(0, text.Length);
        Array.Reverse(c);
        return new string(c);
    }