Assuming an algorithm has access to a true random seed, then it can be proven that the average time complexity is O(nlog(n)). The difference between a randomly chosen pivot and a wisely chosen pivot is just a constant of about 1.39, on the average.
However, note that a randomly chosen pivot does not eliminate the O(n2) problem. It is always possible that the randomly chosen pivot for each level of recursive call is the worst for a particular array. However, such a probability is very small for a large array. At least, an attacker can no longer craft an array to intentionally bring down a system.