Databases
StackOverflow2013
Postsdbo
PODoes quicksort with randomized median-of-three do appreciably better than randomized quicksort?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PODoes quicksort with randomized median-of-three do appreciably better than randomized quicksort?
    primarykey
    data
    text
    <p>I was just answering a question about different approaches for picking the partition in a quicksort implementation and came up with a question that I honestly don't know how to answer. It's a bit math-heavy, and this may be the wrong site on which to ask this, so if this needs to move please let me know and I'll gladly migrate it elsewhere.</p> <p>It's well-known that a quicksort implementation that picks its pivots uniformly at random will end up running in expected O(n lg n) time (there's a nice proof of this <a href="http://en.wikipedia.org/wiki/Quicksort#Randomized_quicksort_expected_complexity" rel="nofollow noreferrer">on Wikipedia</a>). However, due to the cost of generating random numbers, many quicksort implementations don't pick pivots randomly, but instead rely on a "median-of-three" approach in which three elements are chosen deterministically and of which the median is chosen as the pivot. This is known to degenerate to O(n<sup>2</sup>) in the worst-case (see <a href="http://www.cs.dartmouth.edu/~doug/mdmspe.pdf" rel="nofollow noreferrer">this great paper</a> on how to generate those worst-case inputs, for example).</p> <p>Now, suppose that we <strong>combine</strong> these two approaches by picking three random elements from the sequence and using their median as the choice of pivot. I know that this also guarantees O(n lg n) average-case runtime using a slightly different proof than the one for the regular randomized quicksort. However, I have no idea what the constant factor in front of the n lg n term is in this particular quicksort implementation. For regular randomized quicksort Wikipedia lists the actual runtime of randomized quicksort as requiring at most 1.39 n lg n comparisons (using lg as the binary logarithm).</p> <p>My question is this: <strong>does anyone know of a way to derive the constant factor for the number of comparisons made using a "median-of-three" randomized quicksort</strong>? If we go even more generally, is there an expression for the constant factor on quicksort using a randomized median-of-k approach? I'm curious because I think it would be fascinating to see if there is some "sweet spot" of this approach that makes fewer comparisons than other randomized quicksort implementations. I mean, wouldn't it be cool to be able to say that randomized quicksort with a randomized median-of-six pivot choice makes the fewest comparisons? Or be able to conclusively say that you should just pick a pivot element at random?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USGEOCHET
    1. UStemplatetypedef
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. PODoes quicksort with randomized median-of-three do appreciably better than randomized quicksort?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PODoes quicksort with randomized median-of-three do appreciably better than randomized quicksort?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PODoes quicksort with randomized median-of-three do appreciably better than randomized quicksort?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIt may be math-heavy but it falls under clause 2 of the FAQ (a software algorithm) so I'd say it belongs here. You should keep in mind that efficiency depends on both the algorithm _and_ data. Even bubble sort is insanely efficient if the list is mostly sorted already (in fact, it even outperforms some others). Having said that, my answer is "stuffed if I know" but +1 for an interesting question :-)
      singulars
      1. PODoes quicksort with randomized median-of-three do appreciably better than randomized quicksort?
      1. USpaxdiablo
    2. COWouldn't generating 3 random numbers be *more* costly than generating 1 random number?
      singulars
      1. PODoes quicksort with randomized median-of-three do appreciably better than randomized quicksort?
      1. USLasse Vågsæther Karlsen
    3. COYes, but with very high probability (e.g., 1 - 1/n^2), we need a total of only O(n) random numbers. Asymptotically, this does not represent a significant added cost.
      singulars
      1. PODoes quicksort with randomized median-of-three do appreciably better than randomized quicksort?
      1. USa dabbler
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload