Are turboprops really more efficient than jets?
If yes, does that mean that airlines who use jets sacrifice fuel for faster flights?
The short answer to both your questions are Yes. The long answer is, it's not so simple.
The ATR 72 you have pictured has a top speed of 276 knots and a range of 1,300 miles. It can carry around 70 passengers.
This document provides detailed comparisons of burn rates. So we can see the ATR 72 burns about 810 Liters per hour (about 214 gallons/hr). A Boeing 737-400 seats about 150, has a maximum range of about 2,400 miles, and a cruising speed of about 473 knots (almost double the range, and over 1.5 times the speed). But its burn rate is about 3,000 liters per hour (793 gallons).
So is it a strict trade-off? Speed for Efficiency? Well, not entirely.
TAS is true airspeed. That is, the speed of the aircraft relative to the airmass in which it is flying
. However, an decrease in density (e.g. high altitudes; air is less dense) will yield an increase in TAS. Thus, it is easier to fly at the same true airspeed at higher altitudes. Since jets are generally used on longer flights (where much of the time in the air is spent at high cruise altitude), they have to work less to fly the same speed as they would 10,000 feet below. There are other reasons why jets are more efficient at high altitudes - they have to combine less fuel with the thinner air, and there is less drag at high altitudes.
So why don't propeller planes fly at high altitudes then? Well, part of it is that turboprops are less efficient at higher speeds and higher altitudes, and jets (turbofans) are more efficient at both (obviously to a point, but airliners don't fly fast or high enough to decrease their efficiency again).
Since jet engines can also produce more thrust, they are better suited to large airplanes, which are the ones used for long distances (e.g. if you wanted a propeller plane the size of an Airbus A380, you would need a lot more than 4 engines). So jets are used in situations where they are more economical, and props where they are more economical.
In summary:
Turboprop characteristics
This leads to smaller aircraft on shorter, slower routes, like you've observed, since they don't have to climb or fly fast to get there in a reasonable amount of time. Also these short hops generally require fewer passengers, or flying a second flight is better than needing a much bigger plane.
Turbofan characteristics
This leads to larger aircraft on longer, faster routes, like you've observed, since they need to fly higher and faster to get there in a reasonable amount of time. Also since these routes are more "popular", and it costs so much to fly that far, it makes more sense to put more passengers on one plane, than two.
In general, an airline would not sacrifice fuel for faster flights if that was the only advantage, unless they knew there could be a price premium for the faster flight (e.g. Concorde).
For short distances, turboprops are more fuel efficient than jets. On the longer flights, the jet (turbofan) engines win the race.
Turbofan engines perform best at high altitudes. At medium and low altitudes, the turboprops are more efficient engines. Since all flights start and end at low altitudes, the high altitude cruise segment needs to be long enough for the turbofan engine to offset it's disadvantage during start and landing.
The break even point is somewhere between 300 and 500 NM.
The jets are indeed faster, but on short flights the time difference is marginal. A large percentage of the time is spent on the airport and at low altitude where speed is often restricted. The longer the flight is distance wise, the time factor becomes an import advantage for the jet. Not only do passenger like the shorter flight, but it also means less cost for the operator that pays pilots and flight attendants by the hour.