What does the "randomly shuffle training samples" in stochastic gradient descent attain?
If you are not training with minibatches, but just one batch per epoch, then random shuffle does nothing. However, if you are training with minibatches, and the data in the first minibatch is related and vastly different from the last minibatch, the error that is back propagated from the first could be totally the opposite of the error in the final.

By shuffling the records, the minibatches as presumably more representative of the entire training data and so the back-propagation of the errors will be, hopefully, making slow but stead progress towards the global minima, not whipsawing back and forth chasing what would essentially be a class based minima.