Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

2.- Single Thread Algorithms

2.0.- Overview
2.1.-Spreadsort
Overview
Introduction
Overloading
Performance
Tuning
Spreadsort
Header <boost/sort/spreadsort/spreadsort.hpp>
Spreadsort Examples
Integer Sort
Integer Sort Examples
Float Sort
Float Sort Examples
String Sort
String Sort Examples
Rationale
Radix Sorting
Hybrid Radix
Why spreadsort?
Unstable Sorting
Unused X86 optimization
Lookup Table?
Definitions
Frequently Asked Questions
Acknowledgements
Bibliography
History
Boost.Sort C++ Reference
Header <boost/sort/spreadsort/float_sort.hpp>
Header <boost/sort/spreadsort/integer_sort.hpp>
Header <boost/sort/spreadsort/spreadsort.hpp>
Header <boost/sort/spreadsort/string_sort.hpp>
2.2.- pdqsort
Introduction
Usage
Benchmark
The Best Case
The Average Case
The Worst Case
Bad Partitions
2.3.- spinsort
Description
Benchmark
Programming
2.4.- flat_stable_sort
Description
Benchmark
Programming
2.5.- Linux Benchmarks
Near Sorted Data
Complex (Several Types)
2.6.- Windows Benchmarks
Near Sorted Data
Complex (Several Types)
Single Thread Algorithms

This table provides a brief description of the single thread algorithms of the library.

                  |       |                            |                                         | Comparison          |
Algorithm         |Stable |   Additional memory        |  Best, average, and worst case          | method              |
------------------+-------+----------------------------+-----------------------------------------+---------------------+
spreadsort        |  no   |      key_length            | N, Nsqrt(LogN), min(NlogN, Nkey_length) | Hybrid radix sort   |
pdqsort           |  no   |      Log N                 | N, NLogN, NLogN                         | Comparison operator |
spinsort          |  yes  |      N / 2                 | N, NLogN, NLogN                         | Comparison operator |
flat_stable_sort  |  yes  |size of the data / 256 + 8K | N, NLogN, NLogN                         | Comparison operator |
                  |       |                            |                                         |                     |

  • spreadsort is an extremely fast hybrid radix sort algorithm, designed and developed by Steven Ross.
  • pdqsort is a improvement of the quick sort algorithm, designed and developed by Orson Peters.
  • spinsort is a stable sort that is fast with random or nearly sorted data, designed and developed by Francisco Tapia.
  • flat_stable_sort 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.

PrevUpHomeNext