Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It depends on your requirements. Choosing a pivot at random makes it harder to create a data set that generates O(N^2) performance. 'Median-of-three' (first, last, middle) is also a way of avoiding problems. Beware of relative performance of comparisons, though; if your comparisons are costly, then Mo3 does more comparisons than choosing (a single pivot value) at random. Database records can be costly to compare.</p> <hr> <p>Update: Pulling comments into answer.</p> <p><a href="https://stackoverflow.com/users/31455/mdkess">mdkess</a> asserted:</p> <blockquote> <p>'Median of 3' is NOT first last middle. Choose three random indexes, and take the middle value of this. The whole point is to make sure that your choice of pivots is not deterministic - if it is, worst case data can be quite easily generated.</p> </blockquote> <p>To which I responded:</p> <ul> <li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.1103" rel="noreferrer">Analysis Of Hoare's Find Algorithm With Median-Of-Three Partition</a> (1997) by P Kirschenhofer, H Prodinger, C Martínez supports your contention (that 'median-of-three' is three random items).</p></li> <li><p>There's an article described at <a href="http://portal.acm.org/citation.cfm?id=1176.1243&amp;coll=GUIDE&amp;dl=GUIDE&amp;CFID=20869026&amp;CFTOKEN=55062919" rel="noreferrer">portal.acm.org</a> that is about 'The Worst Case Permutation for Median-of-Three Quicksort' by Hannu Erkiö, published in The Computer Journal, Vol 27, No 3, 1984. [Update 2012-02-26: Got the text for the <a href="http://comjnl.oxfordjournals.org/content/27/3/276" rel="noreferrer">article</a>. Section 2 'The Algorithm' begins: '<em>By using the median of the first, middle and last elements of A[L:R], efficient partitions into parts of fairly equal sizes can be achieved in most practical situations.</em>' Thus, it is discussing the first-middle-last Mo3 approach.]</p></li> <li><p>Another short article that is interesting is by M. D. McIlroy, <a href="http://www.cs.dartmouth.edu/~doug/mdmspe.pdf" rel="noreferrer">"A Killer Adversary for Quicksort"</a>, published in Software-Practice and Experience, Vol. 29(0), 1–4 (0 1999). It explains how to make almost any Quicksort behave quadratically.</p></li> <li><p>AT&amp;T Bell Labs Tech Journal, Oct 1984 "Theory and Practice in the Construction of a Working Sort Routine" states "Hoare suggested partitioning around the median of several randomly selected lines. Sedgewick [...] recommended choosing the median of the first [...] last [...] and middle". This indicates that both techniques for 'median-of-three' are known in the literature. (Update 2014-11-23: The article appears to be available at <a href="http://ieeexplore.ieee.org/iel7/6731004/6771897/06771921.pdf?arnumber=6771921" rel="noreferrer">IEEE Xplore</a> or from <a href="http://onlinelibrary.wiley.com/doi/10.1002/j.1538-7305.1984.tb00067.x/abstract" rel="noreferrer">Wiley</a> — if you have membership or are prepared to pay a fee.)</p></li> <li><p><a href="http://www.cs.fit.edu/~pkc/classes/writing/samples/bentley93engineering.pdf" rel="noreferrer">'Engineering a Sort Function'</a> by J L Bentley and M D McIlroy, published in Software Practice and Experience, Vol 23(11), November 1993, goes into an extensive discussion of the issues, and they chose an adaptive partitioning algorithm based in part on the size of the data set. There is a lot of discussion of trade-offs for various approaches.</p></li> <li><p>A Google search for 'median-of-three' works pretty well for further tracking.</p></li> </ul> <p>Thanks for the information; I had only encountered the deterministic 'median-of-three' before.</p>
    singulars
    1. This table or related slice is empty.
    1. POQuicksort: Choosing the pivot
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USJonathan Leffler
    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. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COMedian of 3 is NOT first last middle. Choose three random indexes, and take the middle value of this. The whole point is to make sure that your choice of pivots is not deterministic - if it is, worst case data can be quite easily generated.
      singulars
      1. PO
      1. USmindvirus
    2. COI was reading abt introsort which combines good features of both quicksort and heapsort. The approach to select pivot using median of three might not always be favourable.
      singulars
      1. PO
      1. USSumit Kumar Saha
 

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