Fixed size sorters
Fixed-size sorters, sometimes called fixed sorters for simplicity are a special kind of sorters designed to sort a fixed number of values. Their operator()
also takes a pair of iterators and an optional comparison function. Most of the time, the end iterator is unused, but future versions of the library may start to use it to optionaly perform bounds-checking. As of now, every available fixed-sized sorter also supports projection parameters.
Fixed-sized sorters are not actual sorters per se but class templates that takes an std::size_t
template parameter. Every specialization of a class template for some size gives a "valid" sorter. Many of them have specializations for some sizes only and will produce a compile-time error otherwise. cpp-sort provides some tools to enhance the usability of fixed-sized sorters. You can read more about such tools in the page about sorter adapters.
It is possible to include all the fixed-sized sorters at once with the following line:
#include <cpp-sort/fixed_sorters.h>
The following fixed-size sorters are available and should work with any type for which std::less
works:
#include <cpp-sort/fixed/low_comparisons_sorter.h>
This fixed-size sorter implements specific sorting agolrithms whose goal is to keep the number of comparisons performed low, which may be desirable when the comparisons are expensive but the moves are cheap (for example strings with large common prefixes). To know which sorting algorithm has the lowest overall number of comparisons for an array of a given size, the following method is used: count the total number of comparisons needed to sort every permutation of the array, we call this the comparison weight of the array.
The following table illustrates the comparison weight of the algorithms used by the different specializations of low_comparisons_sorter
, as well as the algorithm used by the specialization
Size | Comparison weight | Algorithm |
---|---|---|
0 | 0 | Nothing |
1 | 0 | Nothing |
2 | 2 | Compare and exchange |
3 | 16 | Insertion sort |
4 | 112 | Insertion sort |
5 | 832 | Merge-insertion sort |
6 | 6912 | Merge-insertion sort |
7 | 62784 | Insertion sort |
8 | 623232 | Insertion sort |
9 | 6778368 | Insertion sort |
10 | 80121600 | Insertion sort |
11 | 1022860800 | Insertion sort |
12 | 15191884800 | Double gnome sort |
13 | 223752499200 | Double gnome sort |
While low_comparisons_sorter
is optimal from 0 thru 8 with regard to the number of comparisons performed, note that merge_insertion_sorter
performs less comparisons on average than some other specializations, but the algorithm is rather complex and has a high runtime cost, which makes it rather unusable. However, unrolled versions on the merge-insertion sort could be used to improve low_comparisons_sorter
. Pull requests welcome :)
template<std::size_t N>
struct low_comparisons_sorter;
#include <cpp-sort/fixed/low_moves_sorter.h>
This fixed-size sorter implements specific sorting agolrithms whose goal is to keep the number of moves performed low, which may be useful when comparisons are cheap but moves are expensive (large objects that only use one field for the comparison for example). To know which sorting algorithm performs the lowest number of move operations overall for an array of a given size, the following method is used: count the total number of moves needed to sort all the permutations of the array, we will call this the move weight of the array.
The following table illustrates the move weight of the algorithms used by the different specializations of low_moves_sorter
. If you ever find an algorithm that beats one of those without a big memory footprint, do not hesitate to contribute:
Size | Move weight |
---|---|
0 | 0 |
1 | 0 |
2 | 2 |
3 | 17 |
4 | 122 |
5 | 898 |
6 | 7188 |
7 | 63276 |
8 | 612048 |
9 | 6476112 |
10 | 74558880 |
11 | 929011680 |
12 | 12465394560 |
13 | 179294186880 |
The algorithms 0 to 3 use an unrolled insertion sort. The algorithm 4 uses a simple selection sort. The following algorithms use a recursive bidirectional selection sort, sometimes known as cocktail selection sort or minmax sort. While it does not perform less moves than a selection sort, it performs a bit less comparisons. This sorter has no upper bound, it can sort an array of size 155 if needed, but then it might generate too much code, so try to keep the size low if possible.
template<std::size_t N>
struct low_moves_sorter;
Note that this fixed-sized sorter is not move-optimal: it tries to perform a few moves without wasting too much memory and with a somewhat reasonable number of comparisons for small collections. If you really need a sorting algorithm that performs the lowest possible number of move operations, you can use the library's indirect_adapter
instead, but it comes at the cost of a higher memory footprint. You probably want to use if only when the objects are really expensive to copy.
#include <cpp-sort/fixed/sorting_network_sorter.h>
This sorter provides sorting network algorithms to sort collections of size 0 to 32. While using a generic algorithm for the task such as a Batcher's odd-even mergesort may be too slow to be usable, the unrolled resulting sorting networks may be fast enough and even tend to be faster than everything else when it comes to sorting small arrays of integers without even requiring additional memory.
template<std::size_t N>
struct sorting_network_sorter;
The following table gives the number of compare-exhange units (CEUs) used to sort a fixed collection of a given size. These numbers should correspond to the best-known size-optimal sorting networks at the time of writing (as opposed to depth-optimal sorting networks). If you ever find a sorting network using less CEUs for one of these sizes, don't hesiste to let me know, but you might as well write a research paper about it.
Size | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
CEUs | 0 | 1 | 3 | 5 | 9 | 12 | 16 | 19 | 25 | 29 | 35 | 39 | 45 | 51 | 56 | 60 |
Size | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
CEUs | 73 | 80 | 88 | 93 | 103 | 110 | 118 | 123 | 133 | 140 | 150 | 157 | 166 | 172 | 180 | 185 |
Note: don't be fooled by the name, none of the algorithms in this fixed-size sorter perform any operation in parallel. Everything is sequential. The algorithms are but long sequences of compare-and-exchange units.
- Home
- Quickstart
- Sorting library
- Comparators and projections
- Miscellaneous utilities
- Tutorials
- Tooling
- Benchmarks
- Changelog
- Original research