3 ms·
Why do you think quicksort's worst-case performance occurs when the data is already sorted?
by anonymoushn 7y ago
Why do you think quicksort's worst-case performance occurs when the data is already sorted?
- Izkata 7y agoQuicksort's worst-case occurs when all elements always land on one side of the pivot. If the pivot is naively chosen as the first or last element in the range, this will be the case for already-sorted data. Randomly selecting the pivot is an additional step easily skipped when first introducing the algorithm.
- anonymoushn 7y agoI don't think this really justifies GP's gripes about Wikipedia or sorted data occurring a lot in the real world. To get the first-element pivot selection quicksort to regularly interact with the sorted data, we would need some standard library to actually ship a quicksort that always picks the first element as the pivot. I don't think any of these exist.