lal::detail::sorting Namespace Reference
Sorting algorithms. More...
Namespaces | |
| namespace | countingsort |
| Types used only by the counting sort algorithm. | |
Classes | |
| class | sorted_vector |
| Sorted vector class. More... | |
Enumerations | |
| enum class | sort_type { non_decreasing , non_increasing } |
| The different types of sorting patterns. More... | |
Functions | |
| template<typename T , typename iterator_t , std::enable_if_t< std::is_integral_v< T > and is_pointer_iterator_v< T, iterator_t >, bool > = true> | |
| void | bit_sort (const iterator_t begin, const iterator_t end, const T &m, char *const seen) noexcept |
| Sorts the elements within range [begin, end) | |
| template<typename T , typename It , std::enable_if_t< std::is_integral_v< T > and is_pointer_iterator_v< T, It >, bool > = true> | |
| void | bit_sort_mem (const It begin, const It end, const std::size_t size, char *const seen) noexcept |
| Sort integer values increasingly. | |
| template<typename T , typename It , std::enable_if_t< std::is_integral_v< T > and is_pointer_iterator_v< T, It >, bool > = true> | |
| void | bit_sort (const It begin, const It end, const std::size_t size) noexcept |
| Sort integer values increasingly. | |
| template<typename value_t , sort_type type, bool memory_has_frequencies, typename value_iterator_t , typename Callable , std::enable_if_t< is_pointer_iterator_v< value_t, value_iterator_t >, bool > = true> | |
| void | counting_sort (const value_iterator_t begin, const value_iterator_t end, const std::size_t largest_key_plus_1, const Callable &key, countingsort::memory< value_t > &mem) noexcept |
| Counting sort algorithm with reusable memory. | |
| template<typename value_t , sort_type type, typename value_iterator_t , typename Callable , std::enable_if_t< is_pointer_iterator_v< value_t, value_iterator_t >, bool > = true> | |
| void | counting_sort (const value_iterator_t begin, const value_iterator_t end, const std::size_t largest_key, const std::size_t upper_bound_size, const Callable &key) noexcept |
| Counting sort algorithm. | |
| template<typename It > | |
| void | insertion_sort (const It begin, const It end) noexcept |
| Insertion sort. | |
Detailed Description
Sorting algorithms.
Enumeration Type Documentation
◆ sort_type
|
strong |
Function Documentation
◆ bit_sort() [1/2]
template<typename T , typename It , std::enable_if_t< std::is_integral_v< T > and is_pointer_iterator_v< T, It >, bool > = true>
|
noexcept |
Sort integer values increasingly.
- Template Parameters
-
T The type of the values ot be sorted. It The type of iterator over the range [being, end)
- Parameters
-
begin Iterator at the beginning of the container. end Iterator at the end of the container. size The value of std::distance(begin, end), i.e., the number of elements from begin to sort, i.e., the size of the container.
- Precondition
- All values within [begin, end) must be unique.
- Postcondition
- The elements in the range [begin,end) are sorted increasingly.
◆ bit_sort() [2/2]
template<typename T , typename iterator_t , std::enable_if_t< std::is_integral_v< T > and is_pointer_iterator_v< T, iterator_t >, bool > = true>
|
noexcept |
Sorts the elements within range [begin, end)
- Template Parameters
-
T The type of the values ot be sorted. iterator_t The type of iterator over the range [being, end)
- Parameters
-
begin Iterator at the beginning of the container. end Iterator at the end of the container. m Smallest value in the range to sort. seen The bit array used to sort.
- Precondition
- All values of mem are set to false.
- All values within [begin, end) are unique.
- Postcondition
- All the values of seen are set to false.
- The elements in the range [begin,end) are sorted increasingly.
◆ bit_sort_mem()
template<typename T , typename It , std::enable_if_t< std::is_integral_v< T > and is_pointer_iterator_v< T, It >, bool > = true>
|
noexcept |
Sort integer values increasingly.
- Template Parameters
-
T The type of the values ot be sorted. It The type of iterator over the range [being, end)
- Parameters
-
begin Iterator at the beginning of the container. end Iterator at the end of the container. size The value of std::distance(begin, end), i.e., the number of elements from begin to sort, i.e., the size of the container. seen The bit array used to sort.
- Precondition
- All values of mem must be set to 0.
- All values within [begin, end) must be unique.
- Postcondition
- All the values of seen are set to 0.
- The elements in the range [begin,end) are sorted increasingly.
◆ counting_sort() [1/2]
template<typename value_t , sort_type type, typename value_iterator_t , typename Callable , std::enable_if_t< is_pointer_iterator_v< value_t, value_iterator_t >, bool > = true>
|
noexcept |
Counting sort algorithm.
This algorithm is useful for sorting containers with non-unique values that can be easily mapped to integers within a reasonable range, e.g., in the range [1,n]. For details on the algorithm, see https://en.wikipedia.org/wiki/Counting_sort
- Template Parameters
-
value_t Type of the values sorted. sort_type One of lal::detail::sorting::sort_type::non_increasing or lal::detail::sorting::sort_type::non_decreasing. value_iterator_t Iterator over type 'value_t' type. Can be inferred. Callable The type of the function passed as parameter. Can be inferred.
- Parameters
-
begin Iterator at the beginning of the range. end Iterator at the end of the range. largest_key Integer value equal to the largest key that can be obtained with function key. upper_bound_size An upper bound of the size of the container to be sorted. The lowest value is std::distance(begin,end), the actual size of the container. key Function that returns a single integer value used to compare the elements. This function is always called twice per element in the range to be sorted.
- Postcondition
- The elements in the range [begin,end) are sorted according to the sorting criterion.
- The function key is called exactly twice for each element in the range to be sorted.
◆ counting_sort() [2/2]
template<typename value_t , sort_type type, bool memory_has_frequencies, typename value_iterator_t , typename Callable , std::enable_if_t< is_pointer_iterator_v< value_t, value_iterator_t >, bool > = true>
|
noexcept |
Counting sort algorithm with reusable memory.
This algorithm is useful for sorting containers with non-unique values that can be easily mapped to integers within a reasonable range, e.g., in the range [1,n]. For details on the algorithm, see https://en.wikipedia.org/wiki/Counting_sort and [17].
- Template Parameters
-
value_t Iterated type sort_type One of lal::detail::sorting::sort_type::non_increasing or lal::detail::sorting::sort_type::non_decreasing. memory_has_frequencies The memory passed as parameter already conatins the frequencies for the counting sort algorithm. See code for more details. value_iterator_t Iterator type. Can be inferred. Callable The type of the function passed as parameter. Can be inferred.
Function paremeters:
- Parameters
-
begin Iterator at the beginning of the range. end Iterator at the end of the range. largest_key_plus_1 Integer value equal to 1 + the largest key that can be obtained with function key. key Function that returns a single integer value used to compare the elements. This function is always called twice per element in the range to be sorted. mem Reusable memory for the counting sort algorithm.
- Precondition
- Memory's count must be set to 0 (see lal::detail::sorting::countingsort::memory::reset_count).
- Postcondition
- The elements in the range [begin,end) are sorted according to the sorting criterion.
- The function key is called exactly twice for each element in the range to be sorted.
◆ insertion_sort()
template<typename It >
|
noexcept |
Insertion sort.
- Parameters
-
begin Iterator at the beginning of the container. end Iterator at the end of the container.
- Postcondition
- The elements in the range [begin,end) are sorted increasingly.
Generated by
1.11.0