Reverse the word order in string, without reversing the words

Question

I was tasked with using C++ to turn this

"Hello Jarryd, do you like socks?"

into:

"socks? like you do Jarryd, Hello";

Edit: The condition was to reverse this in place.

Here's what I came up with, knocked up in Visual Studio using the TestExplorer to run it. Criticism is much appreciated!

.h

namespace SentenceFlipNamespace
{
    class SentenceFlip
    {
    public:
        SentenceFlip();
        ~SentenceFlip();

        int FlipSentenceInPlace(char* in_Sentence);
        void SentenceFlip::Move(int in_StartIndex, char in_String[]);

    };
}

.cpp

namespace SentenceFlipNamespace
{
    SentenceFlip::SentenceFlip()
    {
    }


    SentenceFlip::~SentenceFlip()
    {
    }

    int SentenceFlip::FlipSentenceInPlace(char in_Sentence[])
    {
        int index = 0;
        int length = strlen(in_Sentence);

        while (index < length)
        {
            int dist = 0;
            int wordSize = 0;

            //Get the characters to the first word
            for (int i = length - 1; i > 0; i--)
            {
                if (in_Sentence[i] == ' ' && i != length - 1)
                {
                    dist = i - index;
                    wordSize = length - i - 1; //exclude the space
                    break;
                }
            }

            //Push everything forwards
            for (int i = 0; i <= dist; i++)
                Move(index, in_Sentence);

            //This leaves a space at the end, push it forward
            if (index + wordSize >= length)
                return 0;

            for (size_t i = 0; i < length - wordSize - index - 1; i++)
                Move(index + wordSize, in_Sentence);

            index += wordSize + 1; //include the space          
        }

        return -1;
    }

    void SentenceFlip::Move(int in_StartIndex, char in_String[])
    {
        char temp = in_String[in_StartIndex];
        int length = strlen(in_String);
        for (int j = length - 1; j >= in_StartIndex; j--)
        {
            char temp2 = in_String[j];
            in_String[j] = temp;
            temp = temp2;
        }       
    }
}

Test Method, since I don't invoke it in main.

namespace CodeChallengesTests
{
    TEST_CLASS(TextFlip)
    {
    public:
        TEST_METHOD(SentenceFlipInPlace)
        {
            SentenceFlipNamespace::SentenceFlip *testFlip = new SentenceFlipNamespace::SentenceFlip();
            char input[] = "Hello Jarryd, do you like socks?";
            char expectedResult[] = "socks? like you do Jarryd, Hello";
            testFlip->FlipSentenceInPlace(input);

            Assert::AreEqual(expectedResult, input, "Results do not match");
        }
    };

}

Answer 1

Your algorithm is supremely inefficient. Moving a word to the front moves all the other characters to the back, resulting in a quadratic algorithm. In addition to that, you repeatedly recalculate the length of the null terminated string.

As an aside, the standard library provides std::rotate() for moving part of a sequence from the end to the beginning, no need to write your own.

There is an alternative in-place algorithm which swaps every character at most twice, and traverses three times. Thus it is trivially proven linear:

1. Reverse every word in isolation. Remember the end if needed.
2. Reverse everything.

The standard library features std::reverse() for implementing this.

Answer 2

I would probably do this by reading the words into a vector of strings, then rather than reversing the order, just traverse the vector in reverse order:

#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>

int main() { 
    std::vector<std::string> words { std::istream_iterator<std::string>(std::cin), {} };

    std::copy(words.rbegin(), words.rend(), 
              std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << '\n';
}

So a couple obvious points:

1. Avoiding work is good.
2. Letting your code avoid work is good too.
3. The standard library has lots of stuff that can make programming a lot easier.

Answer 3

This quite simple task.
Just find words in reverse order and put them in new string.

Code should be quite simple:

std::string reverse_words(std::string_view s)
{
    std::string result;
    result.reserve(s.size());
    while(!s.empty()) {
       auto i = s.rfind(' ');
       result.append(s.begin() + i + 1, s.end());
       if (i == std::string_view::npos) break;
       result += ' ';
       s = s.substr(0, i);
    }
    return result;
}

This code is fast since it does minimum allocations and minimum amount of coping.

https://wandbox.org/permlink/bYmojDyt0Z0xMJv0

Answer 4

If it is important to execute the reversing in place, here is an example code (which implements the algorithm mentioned in https://codereview.stackexchange.com/a/224037):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>


static void reverse_chars(char *s, int n)
{
  int n2 = n / 2;
  for (int i = 0; i < n2; i++)
  {
    char tmp = s[i];
    s[i] = s[n - i - 1];
    s[n - i - 1] = tmp;
  }
}

static char *get_next_word(char *s, int *wlen)
{
  while (*s && isspace(*s))
    s++;
  if (*s == '\0')
    return nullptr;
  char *p = s;  
  while (*p && !isspace(*p)) 
    p++;
  *wlen = (p - s);
  return s;
}

static void reverse_words(char *s, int n)
{
  reverse_chars(s, n);
  int wlen;
  char *w;
  while ((w = get_next_word(s, &wlen)) != nullptr)
  {
    reverse_chars(w, wlen);
    s += wlen;
  }
}

int main(int argc, char **argv)
{
  if (argc < 2)
  {
    fprintf(stderr, "Please, specify the string.\n");
    return 1;
  }
  printf("Original string: [%s]\n", argv[1]);
  reverse_words(argv[1], strlen(argv[1]));
  printf("Words reversed:  [%s]\n", argv[1]);
  return 0;
}