The short answer is no, you don't need all the gems first.
Highlight for tip on how to kill the sharks:
The scout doesn't have to be really close to the shark to throw the harpoon. So, as soon as your scout harpoons the shark, move him a little bit away so the shark doesn't get him, but let him go again quickly so that he can throw out another harpoon. I've killed a shark using only one scout using this method.