 |
Sorting Network Search
Backtracking for Small Sorting Networks
|
|
Sorting Network Search
Backtracking for Small Sorting Networks
|
Sorting network in first normal form. More...
#include <1NF.h>
Public Member Functions | |
| C1NF () | |
| Constructor. More... | |
 Public Member Functions inherited from CSortingNetwork | |
| CSortingNetwork () | |
| Constructor. More... | |
| ~CSortingNetwork () | |
| Destructor. More... | |
| Public Member Functions inherited from CComparatorNetwork | |
| CComparatorNetwork () | |
| Constructor. More... | |
| virtual | ~CComparatorNetwork () |
| Destructor. More... | |
| void | Save (const std::string &) |
| Save to file. More... | |
Protected Member Functions | |
| void | Initialize () |
| Initialize the sorting test. More... | |
| bool | Sorts () |
| Does it sort all inputs? More... | |
| bool | StillSorts (const size_t) |
| Does it still sort when a bit is changed? More... | |
| bool | EvenSorts () |
| Does it sort if there are an odd number of inputs and we fix the value on the last channel? More... | |
| Protected Member Functions inherited from CSortingNetwork | |
| virtual void | Initialize () |
| Initialize the sorting test. More... | |
| virtual bool | Sorts () |
| Does it sort? More... | |
| virtual bool | StillSorts (const size_t) |
| Does it still sort when a bit is changed? More... | |
| size_t | FlipInput (size_t, const size_t, const size_t) |
| Recompute network values when a bit is changed. More... | |
| void | InitValues (const size_t, const size_t) |
| Initialize the network values to the all zero input. More... | |
Additional Inherited Members | |
| Static Public Member Functions inherited from CSettings | |
| static void | SetWidth (const size_t) |
| Set width. More... | |
| static void | SetDepth (const size_t) |
| Set depth. More... | |
| Protected Attributes inherited from CSortingNetwork | |
| CBinaryGrayCode * | m_pGrayCode = nullptr |
| Gray code generator. More... | |
| size_t | m_nValue [MAXDEPTH][MAXINPUTS] = {0} |
| Values at each level when sorting. More... | |
| size_t | m_nZeros = 0 |
| Number of zeros in the input. More... | |
| Protected Attributes inherited from CComparatorNetwork | |
| size_t | m_nComparator [MAXDEPTH][MAXINPUTS] = {0} |
| Comparator array. More... | |
| Static Protected Attributes inherited from CSettings | |
| static size_t | m_nWidth = 9 |
| Comparator network width. More... | |
| static size_t | m_nDepth = 6 |
| Comparator network depth. More... | |
A first normal form sorting network has comparators in the first level between channels 0-1, 2-3, 4-5, etc. If there exists an \(n\)-input sorting network of depth \(d\), then there exists an \(n\)-input sorting network of depth \(d\) that is in first normal form. For example, the sorting network in the figure below (left) is not in first normal form. We swap the green and blue channels to get the sorting network on the right, which has both the min-max comparators that we have used so far (which put the maximum on the bottom channel and the minimum on the top channel), and max-min comparators, which put the maximum on the top channel and the minimum on the bottom channel. In the figure below (right) the arrows on the comparators point in the direction taken by the maximum. Notice that we have created a single max-min comparator (shown in red) and a twist at the end of the channel to keep the outputs in sorted order.
Next, as shown in the figure below (left) we flip the max-min comparator by swapping the channels to its right shown in green and blue, and introducing the corresponding twist at the end. This will undo the twist from the first step. In general there may be more than two steps but the twists will always cancel out as in this example. The resulting sorting network below (right) is in first normal form.
Restricting the search to sorting networks in first normal form therefore does us no harm, and it speeds up the search by not having to iterate through all possibilities for the first level. In addition, it speeds up the sorting test since we need only test ternary Gray code strings (00, 01, and 11 as inputs to pairs of channels) instead of binary Gray code strings. These are generated using an instance of CTernaryGrayCode instead of the instance of CBinaryGrayCode.
| C1NF::C1NF | ( | ) |
|
protected |
Check whether sorting network sorts all inputs. Works for even number of channels, and for odd number of channels it doesn't change the last input. The difference between this and CSortingNetwork::sorts() is that this version does not call Initialize(), which means that the value on any hypothetical last even-numbered channel will not be changed.
|
protectedvirtual |
Initialize the network for the sorting test, that is, make the Gray code word for input be all zeros, and the values on every channel at every level be zero.
Reimplemented from CSortingNetwork.
Reimplemented in CAutocomplete.
|
protectedvirtual |
Check whether sorting network sorts all inputs. Works for both odd and even number of channels. The difference between this and CSortingNetwork::sorts() is that this version has to handle any hypothetical last even-numbered channel separately, testing it first with value zero then with value 1.
Reimplemented from CSortingNetwork.
Reimplemented in CAutocomplete.
|
protectedvirtual |
Check that sorting network sorts when the current input has channel flipped.
| delta | Index of channel to flip. |
Reimplemented from CSortingNetwork.
Reimplemented in CAutocomplete.
1.9.4