Click here to Skip to main content
15,894,410 members
Articles / General Programming / Algorithms

Various string reversal algorithms in C#

Rate me:
Please Sign up or sign in to vote.
2.61/5 (13 votes)
18 May 2010CPOL3 min read 62.5K   241   6  
Code illustrations of various string reversal algorithms in C#
/*
 * Code Author - Sarang Date
 */

using System;
using System.Collections.Generic;
using System.Text;

namespace MyPrograms
{
    class MyString
    {
        public static void Main()
        {
            int len = 0;

            Console.WriteLine("Enter input string to reverse");
            string source = Console.ReadLine();

            if (!string.IsNullOrEmpty(source.Trim()))
            {
                len = source.Length;

                Console.WriteLine("String Reversal with Swap algorithm");
                Console.WriteLine("Original is " + source + " and Reversed is " + ReverseWithSwapAlgo(source));
                Console.ReadLine();

                Console.WriteLine("String Reversal with Copy to Char Array");
                Console.WriteLine("Original is " + source + " and Reversed is " + ReverseWithCharArray(source));
                Console.ReadLine();

                Console.WriteLine("String Reversal with Recursion");
                Console.WriteLine("Original is " + source + " and Reversed is " + ReverseWithRecursion(source, len));
                Console.ReadLine();

                Console.WriteLine("String Reversal with Stack");
                Console.WriteLine("Original is " + source + " and Reversed is " + ReverseWithStack(source));
                Console.ReadLine();

                Console.WriteLine("String Reversal without Copy to Char Array - efficient");
                Console.WriteLine("Original is " + source + " and Reversed is " + ReverseWithCharArrayWithoutCopy(source));
                Console.ReadLine();

                Console.WriteLine("String Reversal without Copy to Char Array - most efficient as it uses TrySZReverse of ArrayHelpers in native code");
                Console.WriteLine("Original is " + source + " and Reversed is " + ReverseWithArrayReversal(source));
                Console.ReadLine();

                Console.WriteLine("String Reversal with Bitwise XORing.. cool stuff and as quick as the above Array Reversal one !!");
                Console.WriteLine("Original is " + source + " and Reversed is " + ReverseWithBitwiseXOR(source));
                Console.ReadLine();
            }
            else
            {
                Console.WriteLine("No Input. Bye Bye");
                Console.ReadLine();
            }
        }

        /// <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);
        }

        /// <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);
        }

        /// <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();
        }

        /// <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;
        }

        /// <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);
        }

        /// <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);
        }

        /// <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);
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Technical Lead Microsoft India R&D Pvt. Ltd. Hyderabad
India India
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions