Parallel merge sort and quick sort algorithms.
More...
|
template<typename RAI , typename ComparisonFunction > |
void | embb::algorithms::MergeSortAllocate (RAI first, RAI last, ComparisonFunction comparison=std::less< typename std::iterator_traits< RAI >::value_type >(), const embb::mtapi::ExecutionPolicy &policy=embb::mtapi::ExecutionPolicy(), size_t block_size=0) |
| Sorts a range of elements using a parallel merge sort algorithm with implicit allocation of dynamic memory. More...
|
|
template<typename RAI , typename RAITemp , typename ComparisonFunction > |
void | embb::algorithms::MergeSort (RAI first, RAI last, RAITemp temporary_first, ComparisonFunction comparison=std::less< typename std::iterator_traits< RAI >::value_type >(), const embb::mtapi::ExecutionPolicy &policy=embb::mtapi::ExecutionPolicy(), size_t block_size=0) |
| Sorts a range of elements using a parallel merge sort algorithm without implicit allocation of dynamic memory. More...
|
|
template<typename RAI , typename ComparisonFunction > |
void | embb::algorithms::QuickSort (RAI first, RAI last, ComparisonFunction comparison=std::less< typename std::iterator_traits< RAI >::value_type >(), const embb::mtapi::ExecutionPolicy &policy=embb::mtapi::ExecutionPolicy(), size_t block_size=0) |
| Sorts a range of elements using a parallel quick sort algorithm. More...
|
|
Parallel merge sort and quick sort algorithms.
template<typename RAI , typename ComparisonFunction >
Sorts a range of elements using a parallel merge sort algorithm with implicit allocation of dynamic memory.
The range consists of the elements from first
to last
, excluding the last element. Since the algorithm does not sort in-place, it requires additional memory which is implicitly allocated by the function.
- Exceptions
-
- Dynamic memory allocation
- Array with
last-first
elements of type std::iterator_traits<RAI>::value_type
.
- Concurrency
- Thread-safe if the elements in the range
[first,last)
are not modified by another thread while the algorithm is executed.
- Note
- No guarantee is given on the execution order of the comparison operations.
For nested algorithms, the task limit may be exceeded. In that case, increase the task limit of the MTAPI node.
- See also
- embb::mtapi::ExecutionPolicy, MergeSort()
- Template Parameters
-
RAI | Random access iterator |
ComparisonFunction | Binary predicate with both arguments of type std::iterator_traits<RAI>::value_type or an embb::mtapi::Job associated with an action function accepting a struct containing two members of type std::iterator_traits<RAI>::value_type as its argument buffer and a struct containing one bool member as its result buffer. |
- Parameters
-
[in] | first | Random access iterator pointing to the first element of the range |
[in] | last | Random access iterator pointing to the last plus one element of the range |
[in] | comparison | Binary predicate used to establish the sorting order. An element a appears before an element b in the sorted range if comparison(a, b) == true . The default value uses the less-than relation. |
[in] | policy | embb::mtapi::ExecutionPolicy for the merge sort algorithm |
[in] | block_size | Lower bound for partitioning the range of elements into blocks that are sorted in parallel. Partitioning of a block stops if its size is less than or equal to block_size . The default value 0 means that the minimum block size is determined automatically depending on the number of elements in the range divided by the number of available cores. |
template<typename RAI , typename RAITemp , typename ComparisonFunction >
Sorts a range of elements using a parallel merge sort algorithm without implicit allocation of dynamic memory.
The range consists of the elements from first
to last
, excluding the last element. Since the algorithm does not sort in-place, it requires additional memory which must be provided by the user. The range pointed to by temporary_first
must have the same number of elements as the range to be sorted, and the elements of both ranges must have the same type.
- Exceptions
-
- Concurrency
- Thread-safe if the elements in the ranges
[first,last)
and [temporary_first,temporary_first+(last-first)
are not modified by another thread while the algorithm is executed.
- Note
- No guarantee is given on the execution order of the comparison operations.
For nested algorithms, the task limit may be exceeded. In that case, increase the task limit of the MTAPI node.
- See also
- embb::mtapi::ExecutionPolicy, MergeSortAllocate()
- Template Parameters
-
RAI | Random access iterator |
RAITemp | Random access iterator for temporary memory. Has to have the same value type as RAI. |
ComparisonFunction | Binary predicate with both arguments of type std::iterator_traits<RAI>::value_type . |
- Parameters
-
[in] | first | Random access iterator pointing to the first element of the range |
[in] | last | Random access iterator to last plus one element to be sorted |
[in] | temporary_first | Random access iterator pointing to the last plus one element of the range |
[in] | comparison | Binary predicate used to establish the sorting order. An element a appears before an element b in the sorted range if comparison(a, b) == true . The default value uses the less-than relation. |
[in] | policy | embb::mtapi::ExecutionPolicy for the merge sort algorithm |
[in] | block_size | Lower bound for partitioning the range of elements into blocks that are sorted in parallel. Partitioning of a block stops if its size is less than or equal to block_size . The default value 0 means that the minimum block size is determined automatically depending on the number of elements in the range divided by the number of available cores. |
template<typename RAI , typename ComparisonFunction >
Sorts a range of elements using a parallel quick sort algorithm.
The range consists of the elements from first
to last
, excluding the last element. The algorithm sorts in-place and requires no additional memory. It has, however, a worst-case time complexity of O((last-first)2)
.
- Exceptions
-
- Concurrency
- Thread-safe if the elements in the range
[first,last)
are not modified by another thread while the algorithm is executed.
- Note
- No guarantee is given on the execution order of the comparison operations.
For nested algorithms, the task limit may be exceeded. In that case, increase the task limit of the MTAPI node.
- See also
- embb::mtapi::ExecutionPolicy, MergeSort()
- Template Parameters
-
RAI | Random access iterator |
ComparisonFunction | Binary predicate with both arguments of type std::iterator_traits<RAI>::value_type or an embb::mtapi::Job associated with an action function accepting a struct containing two members of type std::iterator_traits<RAI>::value_type as its argument buffer and a struct containing one bool member as its result buffer. |
- Parameters
-
[in] | first | Random access iterator pointing to the first element of the range |
[in] | last | Random access iterator pointing to the last plus one element of the range |
[in] | comparison | Binary predicate used to establish the sorting order. An element a appears before an element b in the sorted range if comparison(a, b) == true . The default value uses the less-than relation. |
[in] | policy | embb::mtapi::ExecutionPolicy for the quick sort algorithm |
[in] | block_size | Lower bound for partitioning the range of elements into blocks that are sorted in parallel. Partitioning of a block stops if its size is less than or equal to block_size . The default value 0 means that the minimum block size is determined automatically depending on the number of elements in the range divided by the number of available cores. Note that quick sort does not guarantee a partitioning into evenly sized blocks, as the partitions depend on the values to be sorted. |