Is what you call the "shuffle button" a "shuffle playlist" button or a "shuffle mode" button? There is a subtle difference between those two and for what I understand you want the second

Most people want the second - if they hit it, it picks a random song, and then plays all of the remaining songs randomly before repeating.

Few people want to shuffle the playlist (which is closer to above) or worse, to actually randomly select a song each time.