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

• pacmaninbw: Welcome to code review. We can do a better job of reviewing your code if you provide the entire SentenceFlip class and the main program.
• Jarryd: I've added the .h, .cpp and my test method. Thank you, and I'll add these to future questions.

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.

• Jarryd: Oh damn, I am completely out of touch with the standard library, which I need to remedy. And what a great idea, to reverse the words like that. Thanks for taking the time to provide such a great answer, I've learned a lot!

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.

• Loki Astari: Love that. Now if only if we had reverse ranges so we could use the range based for.
• Jerry Coffin: @MartinYork: Soon (C++20). Probably available already, if you use a reasonably new compiler.

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

• pacmaninbw: Welcome to code review. We do things a little differently than stack overflow, good answers actually comment on the users code rather than provide alternate solutions.

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