123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268 |
- <html>
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
- <title>Boost.Sort</title>
- <link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css">
- <meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
- <link rel="home" href="index.html" title="Boost.Sort">
- <link rel="next" href="sort/single_thread.html" title="2.- Single Thread Algorithms">
- </head>
- <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
- <table cellpadding="2" width="100%"><tr>
- <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td>
- <td align="center"><a href="../../../../index.html">Home</a></td>
- <td align="center"><a href="../../../../libs/libraries.htm">Libraries</a></td>
- <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
- <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
- <td align="center"><a href="../../../../more/index.htm">More</a></td>
- </tr></table>
- <hr>
- <div class="spirit-nav"><a accesskey="n" href="sort/single_thread.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div>
- <div class="chapter">
- <div class="titlepage"><div>
- <div><h2 class="title">
- <a name="sort"></a>Boost.Sort</h2></div>
- <div><div class="author"><h3 class="author">
- <span class="firstname">Steven</span> <span class="surname">Ross</span>
- </h3></div></div>
- <div><div class="author"><h3 class="author">
- <span class="firstname">Francisco</span> <span class="surname">Tapia</span>
- </h3></div></div>
- <div><div class="author"><h3 class="author">
- <span class="firstname">Orson</span> <span class="surname">Peters</span>
- </h3></div></div>
- <div><p class="copyright">Copyright © 2014-2017 Steven
- Ross, Francisco Tapia, Orson Peters</p></div>
- <div><div class="legalnotice">
- <a name="sort.legal"></a><p>
- Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
- Software License, Version 1.0</a>.
- </p>
- </div></div>
- </div></div>
- <div class="toc">
- <p><b>Table of Contents</b></p>
- <dl class="toc">
- <dt><span class="section"><a href="index.html#sort.introduction">1.- Introduction</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread.html">2.- Single Thread Algorithms</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread.html#sort.single_thread.overview">2.0.- Overview</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort.html">2.1.-Spreadsort</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview">Overview</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.intro">Introduction</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.overloading">Overloading</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.performance">Performance</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.tuning">Tuning</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp.html">Spreadsort</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp.html#sort.single_thread.spreadsort.sort_hpp.header_spreadsort">Header
- <code class="computeroutput"><boost/sort/spreadsort/spreadsort.hpp></code></a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/integer_sort.html">Integer
- Sort</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/float_sort.html">Float
- Sort</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/string_sort.html">String
- Sort</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/rationale.html">Rationale</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/definitions.html">Definitions</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/faq.html">Frequently Asked
- Questions</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/acks.html">Acknowledgements</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/bibliog.html">Bibliography</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spreadsort/history.html">History</a></span></dt>
- <dt><span class="section"><a href="boost_sort_c___reference.html">Boost.Sort C++ Reference</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="boost_sort_c___reference.html#header.boost.sort.spreadsort.float_sort_hpp">Header <boost/sort/spreadsort/float_sort.hpp></a></span></dt>
- <dt><span class="section"><a href="header/boost/sort/spreadsort/integer_sort_hpp.html">Header <boost/sort/spreadsort/integer_sort.hpp></a></span></dt>
- <dt><span class="section"><a href="header/boost/sort/spreadsort/spreadsort_hpp.html">Header <boost/sort/spreadsort/spreadsort.hpp></a></span></dt>
- <dt><span class="section"><a href="header/boost/sort/spreadsort/string_sort_hpp.html">Header <boost/sort/spreadsort/string_sort.hpp></a></span></dt>
- </dl></dd>
- </dl></dd>
- <dt><span class="section"><a href="sort/single_thread/pdqsort.html">2.2.- pdqsort</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread/pdqsort.html#sort.single_thread.pdqsort.pdqsort_intro">Introduction</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_usage.html">Usage</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_benchmark.html">Benchmark</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_best.html">The Best Case</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_avg.html">The Average
- Case</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_worst.html">The Worst
- Case</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_bad_partitions.html">Bad
- Partitions</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/single_thread/spinsort.html">2.3.- spinsort</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread/spinsort.html#sort.single_thread.spinsort.spinsort_description">Description</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spinsort/spinsort_benchmark.html">Benchmark</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/spinsort/spinsort_programming.html">Programming</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/single_thread/flat_stable_sort.html">2.4.- flat_stable_sort</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread/flat_stable_sort.html#sort.single_thread.flat_stable_sort.flat_stable_sort_description">Description</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/flat_stable_sort/flat_stable_sort_benchmark.html">Benchmark</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/flat_stable_sort/flat_stable_sort_programming.html">Programming</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/single_thread/linux_single.html">2.5.- Linux Benchmarks</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread/linux_single.html#sort.single_thread.linux_single.near_sorted">Near Sorted
- Data</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/linux_single/complex_benchmarks.html">Complex
- (Several Types)</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/single_thread/windows_single.html">2.6.- Windows Benchmarks</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/single_thread/windows_single.html#sort.single_thread.windows_single.near_sorted">Near
- Sorted Data</a></span></dt>
- <dt><span class="section"><a href="sort/single_thread/windows_single/complex_benchmarks.html">Complex
- (Several Types)</a></span></dt>
- </dl></dd>
- </dl></dd>
- <dt><span class="section"><a href="sort/parallel.html">3.- Parallel Algorithms</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort">3.1- block_indirect_sort</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_description">Description</a></span></dt>
- <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_benchmark">Benchmark</a></span></dt>
- <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_programming">Programming</a></span></dt>
- <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_internal">Internal
- Description</a></span></dt>
- <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.design_process">Design
- Process</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/parallel/sample_sort.html">3.2.- Sample_Sort</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/parallel/sample_sort.html#sort.parallel.sample_sort.sample_description">Description</a></span></dt>
- <dt><span class="section"><a href="sort/parallel/sample_sort/sample_programming.html">Programming</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/parallel/parallel_stable_sort.html">3.3.- Parallel_stable_sort</a></span></dt>
- <dd><dl>
- <dt><span class="section"><a href="sort/parallel/parallel_stable_sort.html#sort.parallel.parallel_stable_sort.parallel_description">Description</a></span></dt>
- <dt><span class="section"><a href="sort/parallel/parallel_stable_sort/parallel_programming.html">Programming</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/parallel/linux_parallel.html">3.4- Linux Benchmarks</a></span></dt>
- <dt><span class="section"><a href="sort/parallel/windows_parallel.html">3.5- Windows Benchmark</a></span></dt>
- </dl></dd>
- <dt><span class="section"><a href="sort/bibliography.html">4.- Bibliography</a></span></dt>
- <dt><span class="section"><a href="sort/gratitude.html">5.- Gratitude</a></span></dt>
- </dl>
- </div>
- <div class="section">
- <div class="titlepage"><div><div><h2 class="title" style="clear: both">
- <a name="sort.introduction"></a><a class="link" href="index.html#sort.introduction" title="1.- Introduction">1.- Introduction</a>
- </h2></div></div></div>
- <div class="blockquote"><blockquote class="blockquote">
- <p>
- The goal of the Boost Sort Library is provide to the users, the most modern,
- fast, and memory-efficient sorting algorithms.
- </p>
- <p>
- This library provides stable and unstable sorting algorithms, in single threaded
- and parallel versions.
- </p>
- <p>
- These algorithms do not use any other library or utility. The parallel algorithms
- need a C++11 compliant compiler.
- </p>
- <h5>
- <a name="sort.introduction.h0"></a>
- <span class="phrase"><a name="sort.introduction.single_thread_algorithms"></a></span><a class="link" href="index.html#sort.introduction.single_thread_algorithms"><span class="underline">Single Thread Algorithms</span></a>
- </h5>
- <p>
- <span class="bold"><strong>
- <pre class="programlisting"> | | | | Comparison |
- Algorithm |Stable | Additional memory |Best, average, and worst case | method |
- ------------------+-------+----------------------------+--------------------------------------------+---------------------+
- spreadsort | no | key_length | N, N sqrt(LogN), min(N logN, N key_length) | Hybrid radix sort |
- pdqsort | no | Log N | N, N LogN, N LogN | Comparison operator |
- spinsort | yes | N / 2 | N, N LogN, N LogN | Comparison operator |
- flat_stable_sort | yes |size of the data / 256 + 8K | N, N LogN, N LogN | Comparison operator |
- | | | | |
- </pre>
- </strong></span>
- </p>
- <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
- <li class="listitem">
- <span class="bold"><strong>spreadsort</strong></span> is an extremely fast hybrid
- radix sort algorithm, designed and developed by Steven Ross.
- </li>
- <li class="listitem">
- <span class="bold"><strong>pdqsort</strong></span> is a improvement of the quick
- sort algorithm, designed and developed by Orson Peters.
- </li>
- <li class="listitem">
- <span class="bold"><strong>spinsort</strong></span> is a stable sort that is fast
- with random or nearly sorted data, designed and developed by Francisco
- Tapia.
- </li>
- <li class="listitem">
- <span class="bold"><strong>flat_stable_sort</strong></span> is a stable sort that
- uses very little additional memory (around 1% of the size of the data),
- providing 80% - 90% of the speed of spinsort, designed and developed
- by Francisco Tapia.
- </li>
- </ul></div>
- <h5>
- <a name="sort.introduction.h1"></a>
- <span class="phrase"><a name="sort.introduction.parallel_algorithms"></a></span><a class="link" href="index.html#sort.introduction.parallel_algorithms"><span class="underline">Parallel Algorithms</span></a>
- </h5>
- <p>
- <span class="bold"><strong>
- <pre class="programlisting"> | | | |
- Algorithm |Stable | Additional memory |Best, average, and worst case |
- ----------------------+-------+------------------------+------------------------------+
- block_indirect_sort | no |block_size * num_threads| N, N LogN , N LogN |
- sample_sort | yes | N | N, N LogN , N LogN |
- parallel_stable_sort | yes | N / 2 | N, N LogN , N LogN |
- | | | |
- </pre>
- </strong></span>
- </p>
- <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
- <li class="listitem">
- <span class="bold"><strong>Sample_sort</strong></span> is a implementation of the
- <span class="bold"><strong><a href="https://en.wikipedia.org/wiki/Samplesort" target="_top">Samplesort
- algorithm</a></strong></span> done by Francisco Tapia.
- </li>
- <li class="listitem">
- <span class="bold"><strong>Parallel_stable_sort</strong></span> is based on the
- samplesort algorithm, but using a half of the memory used by sample_sort,
- conceived and implemented by Francisco Tapia.
- </li>
- <li class="listitem">
- <span class="bold"><strong>Block_indirect_sort</strong></span> is a novel high-speed
- parallel sort algorithm with low additional memory consumption, conceived
- and implemented by Francisco Tapia.
- </li>
- </ul></div>
- <p>
- The <span class="bold"><strong>block_size</strong></span> is an internal parameter
- of the algorithm, which in order to achieve the highest speed, changes according
- to the size of the objects to sort according to the next table. The strings
- use a block_size of 128.
- </p>
- <p>
- <span class="bold"><strong>
- <pre class="programlisting"> | | | | | | | |
- object size (bytes) | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 - |
- --------------------------------+--------+---------+---------+---------+---------+---------+----------+
- block_size (number of elements) | 4096 | 2048 | 1024 | 768 | 512 | 256 | 128 |
- | | | | | | | |
- </pre>
- </strong></span>
- </p>
- </blockquote></div>
- </div>
- </div>
- <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
- <td align="left"><p><small>Last revised: December 10, 2019 at 00:22:01 GMT</small></p></td>
- <td align="right"><div class="copyright-footer"></div></td>
- </tr></table>
- <hr>
- <div class="spirit-nav"><a accesskey="n" href="sort/single_thread.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div>
- </body>
- </html>
|