1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>The Worst Case</title> 5<link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../../index.html" title="Boost.Sort"> 8<link rel="up" href="../pdqsort.html" title="2.2.- pdqsort"> 9<link rel="prev" href="pdqsort_avg.html" title="The Average Case"> 10<link rel="next" href="pdqsort_bad_partitions.html" title="Bad Partitions"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="pdqsort_avg.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pdqsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="pdqsort_bad_partitions.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h4 class="title"> 27<a name="sort.single_thread.pdqsort.pdqsort_worst"></a><a class="link" href="pdqsort_worst.html" title="The Worst Case">The Worst 28 Case</a> 29</h4></div></div></div> 30<p> 31 Quicksort naturally performs bad on inputs that form patterns, due to it 32 being a partition-based sort. Choosing a bad pivot will result in many 33 comparisons that give little to no progress in the sorting process. If 34 the pattern does not get broken up, this can happen many times in a row. 35 Worse, real world data is filled with these patterns. 36 </p> 37<p> 38 Traditionally the solution to this is to randomize the pivot selection 39 of quicksort. While this technically still allows for a quadratic worst 40 case, the chances of it happening are astronomically small. Later, in introsort, 41 pivot selection is kept deterministic, instead switching to the guaranteed 42 O(n log n) heapsort if the recursion depth becomes too big. In <code class="literal"><code class="computeroutput">pdqsort</code></code> we adopt a 43 hybrid approach, (deterministically) shuffling some elements to break up 44 patterns when we encounter a "bad" partition. If we encounter 45 too many "bad" partitions we switch to heapsort. 46 </p> 47</div> 48<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 49<td align="left"></td> 50<td align="right"><div class="copyright-footer">Copyright © 2014-2017 Steven 51 Ross, Francisco Tapia, Orson Peters<p> 52 Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost 53 Software License, Version 1.0</a>. 54 </p> 55</div></td> 56</tr></table> 57<hr> 58<div class="spirit-nav"> 59<a accesskey="p" href="pdqsort_avg.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pdqsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="pdqsort_bad_partitions.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 60</div> 61</body> 62</html> 63
