Various string reversal algorithms in C#

• Download MyString.zip - 1.47 KB

Introduction

This article illustrates different string reversal algorithms implemented in C# and their performance and efficiency in terms of time and space usage considerations.

Background

FCL does not provide any in-built methods for string reversal. I have trained my hands on various possible algorithms for string reversals in C# which can be compared in terms of space and time bounds.

Using the code

First lets see a very basic and trivial one to reverse a given string in C#. This uses a swap mechanism to reverse a string. Input string is passed to the method and converted into CharArray. Later on a swap is performed character by character on the char array which is then converted into a string and returned as a reversed string. This is quite a mediocre but most commonly used technique of reversal because it has average performance and the overhead of copying twice (one to char array and other to original as strings are immutable).

/// <summary>
/// String Reversal with Swap algorithm - trivial one.. average performance and the overhead of copying twice 
/// (one to char array and other to original as strings are immutable)
/// Extra variable is used as temp unnecessarily
/// </summary>
/// <param name="source"></param>
/// <returns></returns>

private static string ReverseWithSwapAlgo(string source)
{
        char[] inputstream = source.ToCharArray();
    for (int i = 0, j = inputstream.Length - 1; i < j; i++, j--)
    {
        char temp = inputstream[i];
        inputstream[i] = inputstream[j];
        inputstream[j] = temp;
    }
    return new string(inputstream);
}

This one with CopyTo Char array. Again a trivial one with an average performance. Note the Comments section. The only difference with the previous technique here is the use of in-place swap without any temp variable. Memory efficient but comparitively no much difference in the performance from the previous one.

/// <summary>
/// String Reversal with Copy to Char Array - trivial one.. average performance and the overhead of copying twice 
/// (one to char array and other to original as strings are immutable)
/// No use of temp variable so memory efficient normal reversal
/// </summary>
/// <param name="source"></param>
/// <returns></returns>

private static string ReverseWithCharArray(string source)
{
    char[] inputstream = source.ToCharArray();
    for (int i = 0, j = inputstream.Length - 1; i < j; i++, j--)
    {
        inputstream[j] = source[i];
        inputstream[i] = source[j];
    }
    return new string(inputstream);
}

Now lets try something different. This time with recursion. Probably the simplest recursion one would ever find and thats in string reversals ! Although here I have used SubString function in C# to achieve the split/swap.

/// <summary>
/// String Reversal with Recursion - no extra memory usage although it uses stack internally. 
/// Perf wise works well for smaller strings but average for large strings
/// </summary>
/// <param name="source"></param>
/// <param name="len"></param>
/// <returns></returns>

private static string ReverseWithRecursion(string source, int len)
{
    if (len == 1)
        return source;
    else
        return ReverseWithRecursion(source.Substring(1, source.Length-1),--len) + source[0].ToString();
}

Thinking out of the box ! String reversal using Stack as a data structure. FILO is actually THE concept behind reversing an array of characters. Pushing the characters in the string first, and then Popping them so that the resultant string is automatically reversed. Performance is almost equal to the normal reversals. Note that two loops are being used.

/// <summary>
/// String Reversal with Stack - uses FILO structure for string reversal. 
/// Performance is almost equal to the normal reversals. 
/// Note that two loops are being used
/// </summary>
/// <param name="source"></param>
/// <returns></returns>

private static string ReverseWithStack(string source)
{
    Stack<string> inputStack = new Stack<string>();
    for (int i = 0; i < source.Length; i++)
        inputStack.Push(source.Substring(i, 1));
    string resultstring = string.Empty;
    for (int i = 0; i < source.Length; i++)
        resultstring += inputStack.Pop();
    return resultstring;
}

Lets take a new look at our initial trivial methods using Char arrays with copy and optimize them this time without an overhead of copying twice. We have avoided CopyTo Char array and instead using a new char[] buffer. If at all you have noticed the condition inside the for loop. it is i<=j. Why do we need an extra iteration? Thats because we need to restore the middle character if in case we have odd number of characters in the string. efficient because it doesnt use copying to char array and strings are immutable so new char[] and original string states are maintained separately throughout reversal.

/// <summary>
/// String Reversal without Copy to Char Array - 
/// efficient because it doesnt use copying to char array and 
/// strings are immutable so new char[] and original string states are maintained separately throughout reversal
/// </summary>
/// <param name="source"></param>
/// <returns></returns>

private static string ReverseWithCharArrayWithoutCopy(string source)
{
    char[] inputstream = new char[source.Length];
    for (int i = 0, j = inputstream.Length - 1; i <= j; i++, j--)
    {
        inputstream[j] = source[i];
        inputstream[i] = source[j];
    }
    return new string(inputstream);
}

Another innovative way to reverse a string. Did you know this can be achieved with Array Reversals ! Array reversal is an in-built method provided by FCL. This is very fast as it uses native code to actually perform the reversal. Most efficient so far !

/// <summary>
/// String Reversal without Copy to Char Array - 
/// most efficient as it uses TrySZReverse of ArrayHelpers in native code
/// </summary>
/// <param name="source"></param>
/// <returns></returns>

private static string ReverseWithArrayReversal(string source)
{
    char[] inputstream = source.ToCharArray();
    Array.Reverse(inputstream);
    return new string(inputstream);
}
 

And the cool one. using BitWise XOR ! How it works?

XOR implies [0 XOR 0 = 0], [0 XOR 1 = 1], [1 XOR 0 = 1], [1 XOR 1 = 0].

Now say we have two binary values A = 1 0 0 and B = 1 1 1 which we want to swap using XOR. How do we do that? Try it on paper and you will be amazed !

/// <summary>
/// String Reversal with Bitwise XORing.. cool stuff and quick one too without extra memory usage!!
/// </summary>
/// <param name="source"></param>
/// <returns></returns>

private static string ReverseWithBitwiseXOR(string source)
{
    char[] inputstream = source.ToCharArray();
    int length = source.Length - 1;
    for (int i = 0; i < length; i++, length--)
    {
        inputstream[i] ^= inputstream[length];
        inputstream[length] ^= inputstream[i];
        inputstream[i] ^= inputstream[length];
    }
    return new string(inputstream);
}

And this one is suggested by my friend Murli Krishna.

public static string StringReversal(string str)
{
    char[] revStr = new char[str.Length];
    GCHandle handle = GCHandle.Alloc(str, GCHandleType.Pinned);
    IntPtr pointer = handle.AddrOfPinnedObject();
    for (int i = str.Length-1,j=0; i >= 0; --i,++j)
    {
        revStr[j] =(char) Marshal.ReadByte(pointer, 2 * i);
    }
    handle.Free();
    return new string(revStr); 
}
 

Suggestions for more such methods are welcome !

Another update to this article is here. I have added an algorithm to reverse all the words in a statement in-place. The idea is to first convert the statement (set of strings) into a character array stream and then reverse that stream. Later, extract individual words (which are now reversed) and reverse them one by one resulting in a reversed statement at the end. Find the code below.

/// <summary>
/// Operation to reverse the sequence of words in a statement (string). This is an in-place strings reversal algorithm (words reversal)
/// </summary>
/// <param name="source"></param>
/// <returns></returns>

private static string ReverseWordsInString(string source)
{
	char[] reversedCharArray = ReverseWithArrayReversal(source).ToCharArray();
	int wordStart = 0;
	while (wordStart < reversedCharArray.Length)
	{
		while(wordStart < reversedCharArray.Length - 1 && !char.IsLetter(reversedCharArray[wordStart]))
		{
			wordStart++;
		}
		int wordEnd = wordStart;
		while(wordEnd < reversedCharArray.Length - 1 && char.IsLetter(reversedCharArray[wordEnd +1]))
		{
			wordEnd++;
		}
		if(wordEnd > wordStart)
		{
			int start = wordStart;
			int end = wordEnd;
			while (start < end)
			{
				char temp = reversedCharArray[start];
				reversedCharArray[start] = reversedCharArray[end];
				reversedCharArray[end] = temp;
				start++;
				end--;
			}
		}
		wordStart = wordEnd + 1;
	}
	return new string(reversedCharArray);
}