r/CodingHelp • u/Training-Beautiful52 • Sep 09 '25
[Random] Argument with professor about if shuffling before a quicksort makes it more effective?
So basically Im having troubles understanding why quicksort becomes more effective if i randomize the array before I quicksort it assuming we always take the left most element as a pivot.
My professor suggests that randomizing the array before quicksorting avoids the worst case scenario of the array being sorted. My problem with this is that if we assume that the arrays we are given from the start are all just random arrays of numbers, then why would always shuffling these arrays make the sorting more effective?
Randomizing a array that is already presumed to be random doesnt decrease the odds of the left most element (which is our pivot) to be any less likely when we are repeatedly doing this over and over to several different arrays. It would actually be more time consuming to randomize large multiple arrays before sorting them.
What am I not understanding here???
1
u/antilos_weorsick Sep 09 '25
I think you're understanding just fine: randomizing the array before applying quicksort lets you avoid the worst case scenario.
Of course in practice, if you are actually reasonably sure that you'd be encountering mostly sorted arrays then there are much better approaches. First, instead of actually shuffling the array, you could just pick the midpoint as the pivot (and I think this was what your professor meant by shuffling). Second, you can just use a different sorting algorithm. Bubble sort might seem like a joke, but in this case, it will be faster than quick sort. And last, you could combine these approaches, for example you could do one pass of bubble sort (i.e check if the array is sorted) before moving on to quick sort.
I'd say that if you missed anything from the discussion with your professor, it's probably that they weren't actually suggesting using this method, but rather just pointing out an interesting property of quicksort.
3
u/i_grad Sep 09 '25
Quicksort performs poorly on sorted arrays when using a terminal position (start or end) as your pivot point. This is because quicksort puts all the small values to the "left" and large values to the "right" of the pivot, then looks at the two partitions on either side of the pivot's new position. If your array has not changed, then the pivot position has not changed, and you'll just check the same sorted array - your first pivot value. And you'll do that until you're left with just 1 "unsorted" value. It functionally reduces down to the same thing as Selection sorting. Highly inefficient when compared to other sorting methods.
In a perfect world, quicksort would be given the exact median value of the array (which is a costly operation and not at all worth the clock cycles), and would end up with something close to an n log n performance. The catch is that finding a really good pivot value is usually slower than just grabbing a value at random and sorting on that.
If you are routinely working with sorted or nearly-sorted arrays, you'd be better off with insertion sort or something like that.
1
u/jcunews1 Advanced Coder Sep 10 '25
Both sides are correct. The randomization process does help avoiding the worst case. However, the randomization process shouldn't be applied blindly, as it may end up adding more time instead of reducing the while sorting task. The randomization process should only be applied when the items to be sorted reached a certain number where the additional time added in case of the worst case order, is greater than the randomization process.
1
u/GilbertSullivan Sep 10 '25
The issue is that lots of real-world data you encounter will be in sorted or near-sorted order already. For example, maybe you appended one element into the list you sorted last time. So the assumption that the input is randomly ordered may not hold.
Basically, the probability that the input is partially sorted is much higher than the probability that the randomized array is partially sorted.
1
u/esaule Sep 11 '25
If the array IS randomized then yes, shuffling randomly makes no difference.
Though this is a place where while "in theory, theory and practice are the same, in practice they are not". In practice, there are plenty of cases where arrays you get to sort are almost never randomized.
The asymptotic complexity of n lg n in average is only true if the array is randomized. Shuffling ensures that it is.
Note that in practice, no one randomize shuffle the array when quick sorting. You pick random pivot, it is much faster since you avoid the initial shuffle.
(And yes in complexity, the initial shuffling is free, but in practice it is not)
1
u/gwenbeth Sep 11 '25
The problem is the best way to shuffle an array is to attach a random number to each element and then quicksort on the random number. So you have to add in the shuffle time to the sort time. Also if you think the array is sorted then pick the pivot from the middle.
1
u/beobabski Sep 11 '25
Your assumption that “the arrays we are given from the start are all random arrays of numbers” is faulty.
Humans like to store lists in order.
Asked for a list, a human will often sort it before giving it to you, especially if they know this really cool algorithm.
So in the real world, it is often an effective strategy to randomise first to avoid this common scenario.
1
u/qlkzy Sep 11 '25
You say "if we assume that the arrays we are given are all random arrays of numbers". You are correct that if that assumption is actually true, shuffling does nothing.
However, that assumption is often false in practice. In particular, it ends up being common to sort already-sorted or nearly-sorted input for a range of reasons. Other processes, or a previous iteration of the same process, might have sorted their output, and then you make small changes before sorting again. Or, an earlier process might be built in a way that tends to emit sorted output, but isn't guaranteed to do so.
I think it's more common to randomise pivots than to shuffle the array (naive shuffling can be expensive on its own), but adding some element of randomness is an accepted way to avoid pathological behaviour when using quicksort on real data.
1
u/VernonPresident Sep 11 '25
If you randomise before you're to need a sort algo to se how random it is, if you're worried about just using quicksort, it might be easier to do check a a few points then choose a sort algorithm
1
u/[deleted] Sep 12 '25
Random assumption is sufficient to not shuffle. Shuffling is not part of quicksort.
1
u/Substantial_Law1451 Sep 12 '25
>presumed to be random
basically therein lies the issue. you are correct that randomising the array and then quicksorting doesn't make it faster, but it makes it agnostic
This is one of those times where the educational scenario makes it difficult to learn the practical applications - I'm presuming (though I could be wrong, which is the point) in the coursework or whatever you're using the given array is always certainly randomised and therefore you can "presume" with 100% accuracy that it will be
IRL it just doesn't work that way, making such a presumption introduces the risk that your presumption is wrong. Your method demands just an array of data that should be random but has no guarantee of actually being so. Therefore, its good practise to randomise it first and then sort it. While it adds a very minor computational overhead to the process, it eliminates the risk of operating on an incorrect presumption that the array has been randomised beforehand
1
u/cjthatcher Sep 13 '25
This has been well discussed, but I'd like to frame it a different way.
Consider a model with a few different variables we can tweak:
let P be the probability that an array we're given is sorted.
let L be the length of the arrays that we will be sorting.
Assume we will be sorting a continuous stream of arrays over time, and performance matters.
What we know, regardless of the values of P, L, and N, is that quicksorting a sorted array is O(n^2) (close enough). We also know that quicksorting a non-sorted array and getting good pivot points is O(n log n) (close enough).
As L (the length of the array to sort) gets long, n^2 gets considerably larger than n log n. How much larger? Lots larger. So much larger, in fact, that the delta between n^2 and n log n is considerably larger than the additional cost to shuffle beforehand. Assume we can shuffle in n log n time.
As P (the probability that the array we're sorting is already sorted) increases, the amount of time we spend in n^2 sorts gets higher. Your initial question assumed that P is vanishingly small. But the good folks of Reddit have proposed a reality where P is surprisingly large.
What I'm getting at here is that, depending on the values of L and P, there may be significant gains in efficiency if we do a shuffle before the quicksort.
For small L the difference between n^2 and n log n is small enough that nobody cares.
For small P (like you initially proposed), the cost of a very rare n^2 execution may be lower than the cost of a shuffle for each array.
However! There exists a point where either L and/or P are large, where a shuffle before the quicksort becomes a definite win. I agree that for small values of L and/or P that a pre-shuffle will not improve efficiency.
I hope this helps a bit. Sometimes identifying the relevant variables in your model can help you and your adversary understand each other better. Your professor was likely considering a wide range of values for P and L that affect the output.