103 lines
4.1 KiB
Plaintext
103 lines
4.1 KiB
Plaintext
[/===========================================================================
|
|
Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters
|
|
|
|
|
|
Distributed under the Boost Software License, Version 1.0
|
|
See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt
|
|
=============================================================================/]
|
|
|
|
|
|
[section:spinsort 2.3.- spinsort]
|
|
|
|
|
|
[section:spinsort_description Description]
|
|
[:
|
|
|
|
[*Spinsort] is a new stable sort algorithm, designed and implemented by Francisco Tapia for the Boost Sort Library.
|
|
|
|
This algorithm combines several ideas used to optimize other stable sort algorithms.
|
|
|
|
|
|
[*[teletype]
|
|
``
|
|
| | | |
|
|
Algorithm | Stable | Additional Memory | Best, average, and worst case |
|
|
------------+---------+-------------------+--------------------------------+
|
|
spinsort | Yes | N / 2 | N, NlogN , NlogN |
|
|
| | | |
|
|
|
|
``
|
|
]
|
|
|
|
The algorithm is most efficient when the data are nearly sorted. Many times the new elements are inserted at the end
|
|
of the sorted elements, or some elements are modified, breaking the order of the elements. In these cases, spinsort
|
|
is very fast.
|
|
|
|
]
|
|
[endsect] [/section:spinsort_description Description]
|
|
|
|
[section:spinsort_benchmark Benchmark]
|
|
[:
|
|
|
|
The benchmark with 100000000 64 bits integers, comparing with the std::stable_sort of the GCC 6.3 compiler shows the mentioned characteristics, running on a Intel i7-5820K CPU @ 3.30GH .
|
|
|
|
|
|
[*[teletype]
|
|
``
|
|
Data |std::stable_sort | spin_sort |
|
|
-------------------------------+-----------------+--------------+
|
|
random | 8.62 | 9.73 |
|
|
| | |
|
|
sorted | 4.88 | 0.06 |
|
|
sorted + 0.1% end | 4.92 | 0.41 |
|
|
sorted + 1% end | 4.97 | 0.55 |
|
|
sorted + 10% end | 5.73 | 1.32 |
|
|
| | |
|
|
sorted + 0.1% middle | 6.58 | 1.89 |
|
|
sorted + 1% middle | 7.06 | 2.12 |
|
|
sorted + 10% middle | 9.56 | 4.02 |
|
|
| | |
|
|
reverse sorted | 0.13 | 0.14 |
|
|
reverse sorted + 0.1% end | 5.22 | 0.52 |
|
|
reverse sorted + 1% end | 5.29 | 0.66 |
|
|
reverse sorted + 10% end | 6.03 | 1.45 |
|
|
| | |
|
|
reverse sorted + 0.1% middle | 6.52 | 1.89 |
|
|
reverse sorted + 1% middle | 7.09 | 2.12 |
|
|
reverse sorted + 10% middle | 9.46 | 4.02 |
|
|
| | |
|
|
-------------------------------+-----------------+--------------+
|
|
``
|
|
]
|
|
]
|
|
[endsect] [/section:spinsort_benchmark Benchmark]
|
|
[section:spinsort_programming Programming]
|
|
|
|
[:
|
|
You only need to include the file boost/sort/sort.hpp to use spinsort.
|
|
|
|
The spinsort function is in the namespace boost::sort
|
|
|
|
[c++]
|
|
``
|
|
|
|
#include <boost/sort/sort.hpp>
|
|
|
|
|
|
template <class iter_t, typename compare>
|
|
void spinsort (iter_t first, iter_t last, compare comp = compare());
|
|
|
|
``
|
|
|
|
This algorithm uses a [*comparison object], in the same way as the standard library sort
|
|
algorithms. If you don't define it, the comparison object defaults to std::less, which uses
|
|
the < operator internally for comparisons.
|
|
|
|
This algorithm is [*exception safe], meaning that, the exceptions generated by the algorithm
|
|
guarantee the integrity of the objects to sort, but not their relative order. If the exception
|
|
is generated inside the objects (in the move or copy constructors) the results are undefined.
|
|
]
|
|
[endsect] [/section:spinsort_programming Programming]
|
|
[endsect]
|