Reverse a sentence quickly without pointers

Question

I am trying to reverse a sentence contained in a string and return a string in the quickest way possible using the least amount of memory. Also I don't want to use any unsafe code, so no pointers are allowed. Please let me know if anything can be improved.

My input example is

string mystring = "Hello! my name is";

My result is

"is name my Hello!"

My results on i7 4770S for 1000000 iterations is on average around 650ms.

public static string ReverseTheString(string MyString)
{

    int Length = MyString.Length;
    Char[] NormalArray = new char[Length];
    Char[] FinalArray = new char[Length];

    for (int i = 0; i < Length; i++)
    {
        NormalArray[i] = MyString[i];
    }
    Length = Length - 1; //use for last index
    int SpacesCount = 0;
    int AlphaCount = 0;

    Stack<char[]> ReversedArray = new Stack<char[]>();

    for (int i = 0; i < NormalArray.Length; i++)
    {
        if (NormalArray[i] == ' ' && i != Length)//Space
        {
            if (i != Length)
            {
                if (AlphaCount > 0)
                {
                    char[] temparray = new char[AlphaCount];
                    int tempindex = i - AlphaCount;
                    for (int j = tempindex, k = 0; k < AlphaCount; j++, k++)
                    {
                        temparray[k] = NormalArray[j];
                    }

                    ReversedArray.Push(temparray);
                    AlphaCount = 0;
                    temparray = null;
                }

                SpacesCount++;
            }
            else
            {

                SpacesCount++;
                if (SpacesCount > 0)
                {
                    char[] temparray = new char[SpacesCount];
                    int tempindex = i + 1 - SpacesCount;
                    for (int j = tempindex, k = 0; k < SpacesCount; j++, k++)
                    {
                        temparray[k] = NormalArray[j];
                    }

                    ReversedArray.Push(temparray);
                    SpacesCount = 0;
                    temparray = null;
                }

            }
        }

        if (NormalArray[i] != ' ' ) //alpha
        {
            if (i != Length)
            {
                if (SpacesCount > 0)
                {
                    char[] temparray = new char[SpacesCount];
                    int tempindex = i - SpacesCount;
                    for (int j = tempindex, k = 0; k < SpacesCount; j++, k++)
                    {
                        temparray[k] = NormalArray[j];
                    }

                    ReversedArray.Push(temparray);
                    SpacesCount = 0;
                    temparray = null;
                }
                AlphaCount++;
            }
            else
            {
                AlphaCount++;
                if (AlphaCount > 0)
                {
                    char[] temparray = new char[AlphaCount];
                    int tempindex = i + 1 - AlphaCount;
                    for (int j = tempindex, k = 0; k < AlphaCount; j++, k++)
                    {
                        temparray[k] = NormalArray[j];
                    }

                    ReversedArray.Push(temparray);
                    AlphaCount = 0;
                    temparray = null;
                }
            }
        }
    }


    int Pos = 0;
    while (ReversedArray.Count > 0)
    {
        char[] temparray = ReversedArray.Pop();

        for (int j = 0; j < temparray.Length; j++)
        {
            FinalArray[Pos] = temparray[j];
            Pos++;
        }
    }

    return new string(FinalArray);
}

Answer 1

Bug

• For a given string

  string mystring = "Hello! my name is "; <- see the space at the last character

  your method fails (does not produce the correct result).

Naming

• Based on the naming guidelines input parameters should be named using camelCase casing.

• Although there is nothing mentioned in the naming guidelines about naming variables which are local to methods, you should consider to use camelCase casing. int Length -> int length etc.

Measurement

• On my pc your code runs for 1.000.000 iterations in 480 ms.

Improvements

• by skipping NormalArray and instead using MyString[] directly you can reduce the amount of time to 470 ms.

• here

  SpacesCount++;
  if (SpacesCount > 0)  
  

  and here

  AlphaCount++;
  if (AlphaCount> 0)  
  

  you can skip the if condition, because you don't decrement SpaceCount nor AlphaCount in your code. Now your code is running in 460 ms and your code is more readable.

• declaring an array inside an if block limits its scope to this block. There is no need to set this array = null. So skipping temparray = null; reduces the amount of code and therefor increases readability.

• constructs like

  char[] temparray = new char[AlphaCount];
  int tempindex = i + 1 - AlphaCount;
  for (int j = tempindex, k = 0; k < AlphaCount; j++, k++)
  {
      temparray[k] = MyString[j];
  }
  

  are reducing the readability of the code. A better style would be

  char[] temparray = new char[AlphaCount];
  int tempindex = i + 1 - AlphaCount;
  for (int k = 0; k < AlphaCount; k++)
  {
      temparray[k] = NormalArray[tempindex];
      tempindex++;
  }
  

• by skipping the whole stack and just using a char array I reduced the processing time to 70 ms.

  public static string ReverseTheStringM(String myString)
  {
      int length = myString.Length;
      char[] tokens = new char[length];
      int position = 0;
      int lastIndex;
      for (int i = length - 1; i >= 0; i--)
      {
          if (myString[i] == ' ')
          {
              lastIndex = length - position;
              for (int k = i + 1; k < lastIndex; k++)
              {
                  tokens[position] = myString[k];
                  position++;
              }
              tokens[position] = ' ';
              position++;
          }
      }
  
      lastIndex = myString.Length - position;
      for (int i = 0; i < lastIndex; i++)
      {
          tokens[position] = myString[i];
          position++;
      }
  
      return new string(tokens);
  }
  

Answer 2

The shortest code I can produce is:

private static string Reverse(string input)
{
    return String.Join(" ", input.Split(' ').Reverse());
}

But the following alternative should be much faster:

private static string Reverse(string input)
{
    // Create a new StringBuilder and allocate the same space as in the input string:
    StringBuilder builder = new StringBuilder(input.Length);

    // Declare 2 index variables:
    int index;
    int lastIndex = input.Length;

    // Iterate from the end to the start of the string
    // while the ' ' char is found:
    while ((index = input.LastIndexOf(' ', lastIndex - 1)) != -1)
    {
        builder.Append(input, index + 1, lastIndex - index - 1).Append(' ');
        lastIndex = index;
    }
    // Last iteration (for the first token in the input string):
    if (lastIndex != index)
    {
        builder.Append(input, 0, lastIndex);
    }
    return builder.ToString();
}

The main idea is to iterate from the end of the input string to the beginning, looking for the space char.
Also it makes sense to rely on the .NET built-in methods as much as possible.
Therefore I used:

• The StringBuilder class for accumulation of a result.
• The String.LastIndexOf method for searching for the space char.

The reasons to use the StringBuilder:

• It is very effecient.
• It contains the Append(string value, int startIndex, int count) method which copies specified substring to the inner buffer directly (without creating an intermediate substring from the input string).

EDIT.
A new approach not using the StringBuilder class and with the same main idea:

private static string Reverse(string inputString)
{
    // Get array of chars from the inputString,
    // and allocate the same space in the output array:
    char[] input = inputString.ToCharArray();
    char[] output = new char[input.Length];

    // Declare 3 index variables:
    int index;
    int lastIndex = input.Length;
    int outputIndex = 0;

    // Iterate from the end to the start of the string
    // while the ' ' char is found:
    while ((index = inputString.LastIndexOf(' ', lastIndex - 1)) != -1)
    {
        Array.Copy(input, index + 1, output, outputIndex, lastIndex - index - 1);
        outputIndex += lastIndex - index;
        output[outputIndex - 1] = ' ';
        lastIndex = index;
    }
    // Last iteration (for the first token in the input string):
    if (lastIndex != index)
    {
        Array.Copy(input, 0, output, outputIndex, lastIndex);
    }
    return new string(output);
}

It is slightly less efficient than previous approach, but it is still very fast.