269 lines
17 KiB
HTML
269 lines
17 KiB
HTML
<html>
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
|
|
<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: April 13, 2021 at 16:25:53 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>
|