3 ms·
No op, but I think I understand what they are getting at. With a quicksort you take one item and compare it one at a time to every other item by just asking t
by SimonPStevens 5y ago
No op, but I think I understand what they are getting at.
With a quicksort you take one item and compare it one at a time to every other item by just asking this question "does this come before or after". Then you repeat that process with each side.
But with insertion sort you take each new item and ask the question "where does it go in this already ordered list".
Although these are logically essential the same thing, and certainly have the same result, it's the way the question is framed that makes the quicksort approach often the easier question to answer when trying to decide on a priority order.
Both require a little cunning because you have to get the other person to "forget" that they are essentially prioritising a large list and focus on the easier question of the individual step in the sort algorithm. That's easier with quicksort because the question is very small and isolated, but with insertion sort you are constantly looking at the larger list in order to find the insertion point.