I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness?
Initially, I thought only algorithms outputting random numbers are called probabilistic. They are obviously non-deterministic.
However, what about the following algorithm: Take BubbelSort and randomly decide whether to start sorting from left to right or from right to left. If you modify the sorting order, the algorithm is deterministic, because small values will always be on the left and great values on the right side (or vice versa). As there is some randomness in the algorithm, do we call this algorithm probabilistic?
In short: Any algorithm using some randomness is called probabilistic. Is that correct? However, this term has nothing to do with determinism and non-determinism. Is that correct?