Basically the distinction can be best illustrated with bozo/bogo sort. The definition many people use is:
1. Randomly shuffle the input
2. See if it is sorted, if not go to 1.
The problem, as explained to me by an algorithms lecturer a long time ago, is that the algorithm is not guaranteed to finish, and more over the same input may or may not result in it finishing on different runs.
Per that lecturer a “correct” bozo sort is
1. Generate a list of every permutation of the input
2. Iterate the list until you find a sorted entry and return that.
It has computable best case, worst case, and average case (all terrible). It is guaranteed that the same input will always produce the same output (terminate vs not terminate).
Obviously you could optimize this if you had an algorithm that could shuffle an input such that you were guaranteed that if you shuffled it’s own output you were guaranteed to produce every ordering of the original input. Then you would get closer to: shuffle; check; repeat. But still note that there is no random involved :)