It's easy to run out of hot water when showering and nothing unusual. First thing to do is go and buy an Oxygenics shower head (around $40). They use less water make a HUGE difference. If you happen to have an electric element, you can run that in addition to propane and you will have faster recovery on the tank.
We have had an Oxygenics shower head on 3 TTs now and have not had a problem with running out of hot water and have not had to use water saving techniques. Before installing the Oxygenics heads, I used to run out of water every time.