Re: [HACKERS] qsort again (was Re: Strange Create

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



At 08:37 PM 2/15/2006, Dann Corbit wrote:

Adding some randomness to the selection of the pivot is a known technique to fix the oddball partitions problem.
True, but it makes QuickSort slower than say MergeSort because of the 
expense of the PRNG being called ~O(lgN) times during a sort.

However, Bentley and Sedgewick proved that every quick sort algorithm has some input set that makes it go quadratic
Yep.  OTOH, that input set can be so specific and so unusual as to 
require astronomically unlikely bad luck or hostile hacking in order 
for it to actually occur.

(hence the recent popularity of introspective sort, which switches to heapsort if quadratic behavior is detected. The C++ template I submitted was an example of introspective sort, but PostgreSQL does not use C++ so it was not helpful).
...and there are other QuickSort+Other hybrids that address the issue as well. MergeSort, RadixExchangeSort, and BucketSort all come to mind. See Gonnet and Baeza-Yates, etc.

Here are some cases known to make qsort go quadratic:
1. Data already sorted
Only if one element is used to choose the pivot; _and_ only if the 
pivot is the first or last element of each pass.
Even just always using the middle element as the pivot avoids this 
problem.  See Sedgewick or Knuth.

2. Data reverse sorted
Ditto above.


3. Data organ-pipe sorted or ramp
Not sure what this means?  Regardless, median of n partitioning that 
includes samples from each of the 1st 1/3, 2nd 1/3, and final 3rd of 
the data is usually enough to guarantee O(NlgN) behavior unless the 
_specific_ distribution known to be pessimal to that sampling 
algorithm is encountered.  The only times I've ever seen it ITRW was 
as a result of hostile activity: purposely arranging the data in such 
a manner is essentially a DoS attack.

4. Almost all data of the same value
Well known fixes to inner loop available to avoid this problem.


There are probably other cases. Randomizing the pivot helps some, as does check for in-order or reverse order partitions.
Randomizing the choice of pivot essentially guarantees O(NlgN) behavior no matter what the distribution of the data at the price of increasing the cost of each pass by a constant factor (the generation of a random number or numbers).

In sum, QuickSort gets all sorts of bad press that is far more FUD than fact ITRW. Ron.


[Postgresql General]     [Postgresql PHP]     [PHP Users]     [PHP Home]     [PHP on Windows]     [Kernel Newbies]     [PHP Classes]     [PHP Books]     [PHP Databases]     [Yosemite]

  Powered by Linux