Reverse the order of words

Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it
skvenkeeAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Mikal613Commented:
can it be in vb6?
0
Rodney HelsensCommented:
this sounds like homework
0
Mikal613Commented:
really?
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

skvenkeeAuthor Commented:
This is not a homework. I am trying to get solutions for as many algorithms as possible for the interview. I do have a solution with me. I just want the algorithm and not a program.

My algorithms is:

1. Start from the end of the array and keep decrementing until you see a <space>
2. Then start another loop that then, stores the characters from that index to the next space
3. Continue this until you reach the start.


The efficiency of this algorithm is O(nk) where n is the total number of characters in the sentence and K is the length of the biggest word in the sentence.

Does anyone know a better (efficient ) algorithm than this.

It will also be helpful if anyone have a link or file containing solutions to these type of algorithms.

Thanks.
0
Mikal613Commented:
well you split with the spaces and just start from the bottom of the array
0
fridomCEO/ProgrammerCommented:
very simple:
import List

reverse_sentence sentence =
    List.unwords (List.reverse (List.words sentence))


Main> reverse_sentence "this is a sentence"
"sentence a is this"

Feel free to find out the language used

Regards
Friedrich
0
MaximKammererCommented:
Hi skvenkee,

IMO the efficency of your algorithm is O(n); n being the array lengh. AFAIK in an O(something) description, constant factors are ignored.

Two questions:
- Target array == source array or different?
- What kind of efficency (memory, processing or code size)?

Best regards,
Maxim
0
skvenkeeAuthor Commented:
I refer to efficiency as the execution time of the algorithm.
It will be great if the target array is same as the source array
0
darconeCommented:
Here is a simple algorithm that should perform pretty well:

char c;
            
for(int i = 0; i < word.length/2; i++) {
                  
  c = word[i];
  word[i] = word[word.length - 1 - i];
  word[word.length - 1 - i] = c;
}

word is a character array.

Hope this helps!
0
darconeCommented:
Oh sorry.. nervmind that post :-/ That was reversing characters, not words
0
MaximKammererCommented:
Hi svenkee,

I can't see how your original algorithm description can be much improved while using two seperate arrays.
You don't need a second loop, just remember the space, continue counting down 'til the next space and do a memcopy of the chars in between. I think there is not much room for improvement in this - you _do_ have to look at every character to make sure where the spaces are.

(Just brainstorming):
If your target is not to produce another char[], but could be a different structure you could replace all the spaces with \0 while counting up and just put all the pointers to first letters into a stack / list / array (expensive resizing?) -> voilá, you'll get a sorted structure of words. You can walk it up or down and get the order you want. Main advantage: You don't have to do memcopys.

At the moment I don't see any reasonably performing method of re-using the same array. I think you'd need a maximum word size and even then you would have to use twice as many memcopys. This only would be useful if the array is huge in size and the words remain very small compared to the size of the array. Then the algorithm could look somewhat like this:

0) bufferL and bufferR have a size of 2*MaxWordSize
1) Coming from left, read words sorted into bufferL until PosLeft > Length - PosRight (initially Length==PosRight -> 1 word read at 1st iteration)
2) Write bufferR to Array at PosRight (initially empty / 0 -> nothing done at 1st iteration)
3) Coming from right, read words sorted into bufferR until Length-PosRight > PosLeft
4) Write bufferL to Array at Length-PosLeft
5) Repeat  at 1) until PosRight <= PosLeft

Best regards,
Maxim
0
baboo_Commented:
svenkee:

Best solution, I think, is this:

1) Reverse the whole array - O(n)

"Punch me in the face"

         becomes

"ecaf eht ni em hcnup"


2) Reverse each word in place
       a) Read until you reach the end of the word - O(n) in total
       b) Then swap first and last letters, working your way in to the middle - O(n/2) worst case

for a grand total of O( n + n + n/2 ) = O((5/2)n), which is better than O(nk) whenever the longest string is longer than 2.5 characters.


Aaaand, here's the site you're looking for:

http://www.techinterview.org/index.html


BTW, Maxim: when you're comparing two algorithms where one asymptotically increases, then you're right - constants can be left off, as they are asymptotically insignificant.  For example, if you were comparing O( 5n ) versus O( n^2 ), you would be correct to say that the 5 doesn't matter.  But for algorithms that are in the same complexity category (like these two), there's nothing wrong with leaving in constant multipliers and the like, since it allows you to differentiate algorithmic complexity with higher granularity.

baboo_
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
nee_neeCommented:
I wanted to do something like this but instead I wanted to read a file, search for states that are 2 char length and make the country for them United States.  Can anyone assist me with this?
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.