Array.Reverse Algortihm ?

Question

What kind of algorithm Array.Reverse(string a), uses behind the scene to reverse the string?

Answer 1

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

Answer 2

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;

Answer 3

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.

Answer 4

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.}

Answer 5

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.

Answer 6

My suggestion:

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