Xjyuk

I was tasked with using C++ to turn this:

"Hello Jarryd, do you like socks?"

into:

"socks? like you do Jarryd, Hello";

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

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;
 
 

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 two additional times. Thus it is trivially proven linear:

1. Reverse everything.


2. Reverse every word in isolation.

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

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.

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