lal::detail::sorting Namespace Reference

Sorting algorithms. More...

Namespaces
namespace	countingsort
	Types used only by the counting sort algorithm.

Classes
struct	non_decreasing_t
	Non-decreasing sort type. More...
struct	non_increasing_t
	Non-increasing sort. More...
class	sorted_vector
	Sorted vector class. More...

Functions
template<typename T , typename iterator_t , std::enable_if_t< std::is_integral_v< T > &&is_pointer_iterator_v< T, iterator_t >, bool > = true>
void	bit_sort (iterator_t begin, iterator_t end, const T &m, char *const seen) noexcept
	Sorts the elements within range [begin, end) More...
template<typename T , typename It , std::enable_if_t< std::is_integral_v< T > &&is_pointer_iterator_v< T, It >, bool > = true>
void	bit_sort_mem (It begin, It end, const std::size_t size, char *const seen) noexcept
	Sort integer values increasingly. More...
template<typename T , typename It , std::enable_if_t< std::is_integral_v< T > &&is_pointer_iterator_v< T, It >, bool > = true>
void	bit_sort (It begin, It end, const std::size_t size) noexcept
	Sort integer values increasingly. More...
template<typename value_t , typename sort_type , bool memory_has_frequencies, typename value_iterator_t , std::enable_if_t< is_pointer_iterator_v< value_t, value_iterator_t > &&(std::is_same_v< sort_type, non_decreasing_t >||std::is_same_v< sort_type, non_increasing_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 std::function< std::size_t(const value_t &)> &key, countingsort::memory< value_t > &mem) noexcept
	Counting sort algorithm with reusable memory. More...
template<typename value_t , typename sort_type , typename value_iterator_t , std::enable_if_t< is_pointer_iterator_v< value_t, value_iterator_t > &&(std::is_same_v< sort_type, non_decreasing_t >||std::is_same_v< sort_type, non_increasing_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 std::function< std::size_t(const value_t &)> &key) noexcept
	Counting sort algorithm. More...
template<typename It >
void	insertion_sort (It begin, It end) noexcept
	Insertion sort. More...

Detailed Description

Sorting algorithms.

Function Documentation

bit_sort() [1/2]

template<typename T , typename It , std::enable_if_t< std::is_integral_v< T > &&is_pointer_iterator_v< T, It >, bool > = true>

void lal::detail::sorting::bit_sort ( It  begin, It  end, const std::size_t  size  )

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 > &&is_pointer_iterator_v< T, iterator_t >, bool > = true>

void lal::detail::sorting::bit_sort ( iterator_t  begin, iterator_t  end, const T &  m, char *const  seen  )

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 > &&is_pointer_iterator_v< T, It >, bool > = true>

void lal::detail::sorting::bit_sort_mem ( It  begin, It  end, const std::size_t  size, char *const  seen  )

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 , typename sort_type , typename value_iterator_t , std::enable_if_t< is_pointer_iterator_v< value_t, value_iterator_t > &&(std::is_same_v< sort_type, non_decreasing_t >||std::is_same_v< sort_type, non_increasing_t >), bool > = true>

void lal::detail::sorting::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 std::function< std::size_t(const value_t &)> &  key  )

noexcept

Counting sort algorithm.

This algorithm is interesting 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:

Template Parameters

value_t	Type of the values sorted.
sort_type	One of lal::detail::sorting::non_increasing_t or lal::detail::sorting::non_decreasing_t.
value_iterator_t	Iterator over type 'value_t' type.

Function paremeters:

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.

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 , typename sort_type , bool memory_has_frequencies, typename value_iterator_t , std::enable_if_t< is_pointer_iterator_v< value_t, value_iterator_t > &&(std::is_same_v< sort_type, non_decreasing_t >||std::is_same_v< sort_type, non_increasing_t >), bool > = true>

void lal::detail::sorting::counting_sort ( const value_iterator_t  begin, const value_iterator_t  end, const std::size_t  largest_key_plus_1, const std::function< std::size_t(const value_t &)> &  key, countingsort::memory< value_t > &  mem  )

noexcept

Counting sort algorithm with reusable memory.

This algorithm is interesting 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 [12].

Template Parameters

value_t	Iterated type
sort_type	One of lal::detail::sorting::non_increasing_t or lal::detail::sorting::non_decreasing_t.
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

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.
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 >

void lal::detail::sorting::insertion_sort ( It  begin, It  end  )

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.