Introduction
TNL offers several different parallel algorithms for sorting of arrays (or vectors) and also sorting based on user defined swapping. The latter is more general but also less efficient.
Sorting of arrays and vectors
The sorting of arrays and vectors is accessible via the following functions:
The following example demonstrates the use of ascending and descending sort:
1#include <iostream>
2#include <TNL/Containers/Array.h>
3#include <TNL/Algorithms/sort.h>
4
8
9template< typename ArrayT >
10void
12{
13 const int size = 10;
14
15
16
17
19 srand( size + 2021 );
21 size,
22 [ & ]( int i )
23 {
24 aux_array[ i ] =
std::rand() % ( 2 * size );
25 } );
26 array = aux_array;
27
29
30
31
32
35
36
37
38
41}
42
43int
44main( int argc, char* argv[] )
45{
46
47
48
52
53#ifdef __CUDACC__
54
55
56
60#endif
61 return EXIT_SUCCESS;
62}
Array is responsible for memory management, access to array elements, and general array operations.
Definition Array.h:64
Namespace for fundamental TNL algorithms.
Definition AtomicOperations.h:9
std::enable_if_t< std::is_integral_v< Begin > &&std::is_integral_v< End > > parallelFor(const Begin &begin, const End &end, typename Device::LaunchConfiguration launch_config, Function f, FunctionArgs... args)
Parallel for-loop function for 1D range specified with integral values.
Definition parallelFor.h:41
void descendingSort(Array &array, const Sorter &sorter=Sorter{})
Function for sorting elements of array or vector in descending order.
Definition sort.h:67
void sort(Array &array, const Compare &compare, const Sorter &sorter=Sorter{})
Function for sorting elements of array or vector based on a user defined comparison lambda function.
Definition sort.h:107
void ascendingSort(Array &array, const Sorter &sorter=Sorter{})
Function for sorting elements of array or vector in ascending order.
Definition sort.h:37
Namespace for TNL containers.
Definition Array.h:17
The main TNL namespace.
Definition AtomicOperations.h:9
Here we create an array with random sequence of integers using the parallelFor function and then we sort the array in ascending order using ascendingSort and descending order using the descendingSort.
The result looks as follows:
Sorting on CPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Array sorted in ascending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Array sorted in descending order:[ 15, 14, 14, 11, 8, 5, 5, 2, 1, 0 ]
Sorting on GPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Array sorted in ascending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Array sorted in descending order:[ 15, 14, 14, 11, 8, 5, 5, 2, 1, 0 ]
How to achieve the same result with user defined ordering is demonstrated by the following example:
1#include <iostream>
2#include <TNL/Containers/Array.h>
3#include <TNL/Algorithms/sort.h>
4
8
9template< typename ArrayT >
10void
12{
13 const int size = 10;
14
15
16
17
19 srand( size + 2021 );
21 size,
22 [ & ]( int i )
23 {
24 aux_array[ i ] =
std::rand() % ( 2 * size );
25 } );
26 array = aux_array;
27
29
30
31
32
35 {
36 return a < b;
37 } );
39
40
41
42
45 {
46 return a > b;
47 } );
49}
50
51int
52main( int argc, char* argv[] )
53{
54
55
56
60
61#ifdef __CUDACC__
62
63
64
68#endif
69 return EXIT_SUCCESS;
70}
#define __cuda_callable__
Definition Macros.h:49
The result looks as follows:
Sorting on CPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Array sorted in ascending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Array sorted in descending order:[ 15, 14, 14, 11, 8, 5, 5, 2, 1, 0 ]
Sorting on GPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Array sorted in ascending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Array sorted in descending order:[ 15, 14, 14, 11, 8, 5, 5, 2, 1, 0 ]
The same way, one can sort also TNL::Containers::ArrayView, TNL::Containers::Vector and TNL::Containers::VectorView.
Sorting with user-defined swapping
1#include <iostream>
2#include <TNL/Containers/Array.h>
3#include <TNL/Algorithms/sort.h>
4
8
9template< typename ArrayT >
10void
12{
13 const int size = 10;
14
15
16
17
19 srand( size + 2021 );
21 size,
22 [ & ]( int i )
23 {
24 aux_array[ i ] =
std::rand() % ( 2 * size );
25 } );
26 array = aux_array;
27
28
29
30
31 ArrayT index( size );
32 index.forAllElements(
34 {
35 value = idx;
36 } );
39
40
41
42
43 auto array_view = array.getView();
44 auto index_view = index.getView();
45 sort<
typename ArrayT::DeviceType,
46 typename ArrayT::IndexType >(
47 0,
48 size,
50 return array_view[ i ] < array_view[ j ];
51 },
53 TNL::swap( array_view[ i ], array_view[ j ] );
54 TNL::swap( index_view[ i ], index_view[ j ] );
55 } );
58}
59
60int
61main( int argc, char* argv[] )
62{
63
64
65
69
70#ifdef __CUDACC__
71
72
73
77#endif
78 return EXIT_SUCCESS;
79}
__cuda_callable__ constexpr void swap(Type &a, Type &b)
This function swaps values of two parameters.
Definition Math.h:496
In this example, we fill array array
with random numbers and array index
with numbers equal to position of an element in the array. We want to sort the array array
and permute the index
array correspondingly. This is achieved by calling a variant of the sort
function, which does not accept an array-like data structure, but only range of indexes and two lambda functions. The first lambda function defines the ordering of the elements by comparing elements of array array
. The second lambda function is responsible for swapping elements. Note that we do not swap only elements of array array
, but also index
array.
The result looks as follows:
Sorting on CPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Index array: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
Sorted array: [ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Index: [ 4, 1, 6, 3, 0, 9, 5, 8, 7, 2 ]
Sorting on GPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Index array: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
Sorted array: [ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Index: [ 4, 1, 6, 0, 3, 9, 5, 7, 8, 2 ]