kaya3
2020-12-03 23:49:12
Randomised quicksort is equivalent to shuffling the array first and then applying naive quicksort. Shuffling takes linear time and makes it so that you get the average time complexity for quicksort regardless of the partially-sorted input, i.e. O(n log n).
Naive quicksort will have quadratic time complexity on these inputs because eventually the element t will be chosen as a pivot, and t occurs before the sorted region, so this region will be selected as a partition in its entirety. Naive quicksort will take quadratic time in (n/3) on this partition, which is quadratic in n.
热门帖子
热门github
6