| Taskflow: A General-purpose Task-parallel Programming System

Loading...
Searching...
No Matches
Parallel Sort

Taskflow provides template functions for constructing tasks to sort ranges of items in parallel.

# Include the Header

You need to include the header file, `taskflow/algorithm/sort.hpp`, for creating a parallel-sort task.

#include <taskflow/algorithm/sort.hpp>

# Sort a Range of Items

The task created by tf::Taskflow::sort(B first, E last) performs parallel sort to rank a range of elements specified by `[first, last)` in increasing order. The given iterators must be random-accessible. The following example creates a task to sort a data vector in increasing order.

tf::Taskflow taskflow;
tf::Executor executor;
std::vector<int> data = {1, 4, 9, 2, 3, 11, -8};
tf::Task sort = taskflow.sort(data.begin(), data.end());
executor.run(taskflow).wait();
assert(std::is_sorted(data.begin(), data.end()));
tf::Executor
class to create an executor
Definition executor.hpp:62
tf::Executor::run
tf::Future< void > run(Taskflow &taskflow)
runs a taskflow once
tf::FlowBuilder::sort
Task sort(B first, E last, C cmp)
constructs a dynamic task to perform STL-styled parallel sort
tf::Task
class to create a task handle over a taskflow node
Definition task.hpp:263
tf::Taskflow
class to create a taskflow object
Definition taskflow.hpp:64

Attention
  Elements are compared using the operator `<`.

# Sort a Range of Items with a Custom Comparator

tf::Taskflow::sort(B first, E last, C cmp) is an overload of parallel sort that allows users to specify a custom comparator. The following example sorts a data vector in decreasing order.

tf::Taskflow taskflow;
tf::Executor executor;
std::vector<int> data = {1, 4, 9, 2, 3, 11, -8};
tf::Task sort = taskflow.sort(data.begin(), data.end(),
[](int a, int b) { return a > b; }
);
executor.run(taskflow).wait();
assert(std::is_sorted(data.begin(), data.end(), std::greater<int>{}));

Attention
  tf::Taskflow::sort is not stable. That is, two or more objects with equal keys may not appear in the same order before sorting.

# Enable Stateful Data Passing

The iterators taken by tf::Taskflow::sort are templated. You can use std::reference_wrapper to enable stateful data passing between the sort task and others. The following example creates a task `init` to initialize the data vector and a task `sort` to sort the data in parallel after `init` finishes.

tf::Taskflow taskflow;
tf::Executor executor;
std::vector<int> data;
std::vector<int>::iterator first, last;
tf::Task init = taskflow.emplace([&](){
data = {1, 4, 9, 2, 3, 11, -8};
first = data.begin();
last = data.end();
});
tf::Task sort = taskflow.sort(
std::ref(first), std::ref(last), [] (int l, int r) { return l < r; }
);
init.precede(sort);
executor.run(taskflow).wait();
assert(std::is_sorted(data.begin(), data.end()));
tf::FlowBuilder::emplace
Task emplace(C &&callable)
creates a static task
Definition flow_builder.hpp:1352
tf::Task::precede
Task & precede(Ts &&... tasks)
adds precedence links from this to other tasks
Definition task.hpp:947