Can we do quick sort with minimal complexity in n logn?

Question

I was wondering if we could somehow modify the quicksort algorithm to create worse O (n logn) time complexity. Although this can be done by rearranging the data, and then assuming that we get average complexity, not the worst case. But this is not a complete proof, since we can again get into the worst case after a permutation. Is there any other way you can offer.

Answer 1

Well, yes, we can bring this to O (nlogn). All the algorithms I've seen that try to reduce this are based on the choice of the pivot point. If you can "reasonably" choose your anchor point, it can be knocked down.

Parameters 1. Intro Sort . Now this is no longer a "clean" quick look. Subsequently, it uses merge sort. 2. The choice of the median as a rod. Now the search for the median can take a huge amount of time if you do it in the usual way, but there is a mention in the Introduction to Algorithms .

Here's Something Direct From The Horse's Mouth Introduction to Algorithms

• Divide the array into [n / 5] groups with each group having 5 elements
• Find the median of each group using insertion sort, and then select the median from this list.
• Then you will need to recursively try to find the median [n / 5] medians calculated from each group.
• Divide the array around this median

There are several more complicated things in this algorithm that I have hidden. You can go through this in the same book if you want. I usually do not try to use this algorithm. I use a randomized selection operation to find the rod and work with it.

Answer 2

Well, “change” here is a rather subjective word. There are several ways to increase high-speed sorting so that it runs in O(n log n) . Regardless of whether you want to call it a quick view, you need to determine.

One of them is introsort . Introsort starts with a quick sort, but then switches to a merge sort, which has the worst O(n log n) complexity. One of the goals of the introsort is to deal with the 3 median killer lists.