It was written on January 11, 2016. If there are any mistakes, please correct them.
The original
Two days ago, I saw a problem about the performance of quick sort algorithm on Zhihu. I simply summarized an optimization idea, and now I post it in my blog. The copyright is mine.
In fact, most of it was covered in another blog post of mine: take a closer look at javascript sort methods
The answer: www.zhihu.com/question/39…
Quicksort deep water. I do not post code, mainly about optimization ideas and means.
1. Pivot wisely
It is definitely not appropriate for you to choose the first or last element of the partition for pivot. For cases that are already sorted, or close to being sorted, it goes to the worst case, where the time complexity decays to
The ideal situation for pivot’s selection is that the number of elements in the partition smaller than pivot is about the same as the number of elements larger than Pivot. A more common practice is midian of three, where the pivot takes the median from the first, last, and middle terms. Of course, this does not completely avoid the worst-case scenario. So more careful and rigorous pivot choices are often taken (especially important for large arrays). For example, the large array is evenly divided into three parts: left, middle and right. Each part is divided into three parts to get a median, and then find the median from the three median.
I’ve seen another way of choosing pivot in the javascript V8 engine: consider an array with more than 1000 entries as a large array, pick one element every 200 or so (unfixed), find the median of those elements, add the first and last elements, and find the median of those three elements as pivot.
By the way, in the real world, the need for you to sort a pre-ordered array is so common that this optimization has to be done.
2. Partition faster
I see that what they’re doing is they’re going from left to right and they’re doing the pivot, and they’re doing the switch, and that’s not very efficient. For a simple example, take an array [2, 1, 3, 1, 3], pick the first element as pivot, and if you follow the logic, each discovery of a number less than 2 causes a swap, three times. However, intuitively, you can swap the first 3 with the last 1 to get all three. So a better way to partition is to go from two sides to the middle. You can refer to the implementation of @linbread upstairs.
3. Deal with duplicate elements
What if all the elements in an array are the same size (or there are a lot of the same elements)? This is a boundary case, but makes quicksort a worst-case scenario, because either way you choose pivot, the partition result will be big on one side and small on the other. So how do you solve this problem? We need three partitions: less than Pivot, equal to pivot, and greater than pivot. Since said not to stick code, that point to it, interested in their own can find others to see.
4. Optimize small array efficiency
This has been mentioned by many people. Why optimize small arrays? Because for small sizes, quicksort is not an obvious advantage (it may not be), and recursive algorithms introduce additional overhead. So for this kind of case can choose non-recursive algorithm to replace. Ok, so there are two questions: How small an array is a small array? What’s the substitution algorithm?
Usually this threshold is set to 16 (10 in V8), and the replacement algorithm is usually selective sorting. It is said that the threshold is set to make better use of the CPU cache, which I don’t know much about. Similarly, for the partition of the small array should be immediately selected sort, or after the partition is complete, and then unified selection sort, this problem will also have a certain cache hit difference, I do not understand, not in-depth.
5. Monitor recursion
What I’m talking about here is introspective sorting. If you think about it, we’ve made some efforts to keep the quicksort algorithm from getting into the worst case. But it may not be as good as we think. Ideally, how deep would the recursive attempts of quicksort go? This one is easy to answer:
6. Optimize recursion
I want to make it clear that introspective sorting, while it will avoid too much recursion, is not intended to optimize recursion.
In the partitioning process, we are essentially splitting a large problem into two smaller problems. Now we need to think about which of these two little problems is smaller. By working on smaller problems first and then on larger ones, you reduce the recursion depth and save stack overhead.
Someone upstairs also mentioned tail recursion. For the support of tail recursion language, natural is excellent, small problems recurse first, reduce the depth of recursion, large problems directly through the tail recursion optimization, do not enter the recursive stack.
However, not all languages support tail recursion, such as Python (reportedly) and javascript. In the javascript V8 engine, I saw that it manually implemented the same optimization as tail recursion with a loop variant, which was awesome.
7. Parallel
Since quicksort algorithm is a typical divide-and-conquer algorithm, the small problems decomposed can be processed in parallel in different threads. Of course it doesn’t work for javascript, well, I do the front end.