| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102 |
- [/===========================================================================
- 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]
|
