#include "tbb/parallel_sort.h"
template<typename RandomAccessIterator> void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end ); template<typename RandomAccessIterator, typename Compare> void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end, const Compare& comp ); template<typename Container> void parallel_sort( Container c ); template<typename Container> void parallel_sort( Container c, const Compare& comp );
シーケンスまたはコンテナーをソートします。ソートは不安定で再現性がありません。等しいキーの相対的な順序は保存されず、同じシーケンスを再度ソートした場合でも同じ結果になる保証はありません。イテレーターとシーケンスの要件は、std::sort と同じです。具体的には、RandomAccessIterator はランダムアクセス・イテレーターであり、その値の型 T は次の表の要件をモデル化します。
擬似署名 |
意味 |
---|---|
void iter_swap( It a, It b ) |
イテレーター a および b が指している要素の値をスワップします。 |
bool Compare::operator()(const T& x, const T& y) |
x が y の前に現れる場合は true。その他の場合は false。 |
呼び出し parallel_sort( begin, end, comp ) は、相対的な順序を決定するために引数 comp を使用して、シーケンス [begin, end) をソートします。comp( x, y ) が true を返す場合、x はソートされたシーケンスで y の前に現れます。
呼び出し parallel_sort( begin, end ) は、parallel_sort( begin, end, std::less<T> ) と等価です。
呼び出し parallel_sort( c[, comp] ) は、parallel_sort( std::begin(c), std::end(c)[, comp] ) と等価です。
計算量
parallel_sort は、平均時間計算量 O(N×log(N)) の比較ソートです。ここで、N はシーケンスの要素の数です。ワーカースレッドが利用可能な場合、parallel_sort は実行時間が改善されるように、同時に実行するサブタスクを作成します。
次の例は、さまざまな形式の parallel_sort を示しています。配列 a および c は、デフォルト比較を使用して昇順にソートされます。配列 b および d は、比較に std::greater<float> を使用して降順にソートされます。
#include "tbb/parallel_sort.h" #include <math.h> using namespace tbb; const int N = 100000; float a[N], b[N], c[N], d[N]; int main() { for( int i = 0; i < N; i++ ) { a[i] = sin((double)i); b[i] = cos((double)i); c[i] = 1/sin((double)i); d[i] = 1/cos((double)i); } parallel_sort(a, a + N); parallel_sort(b, b + N, std::greater<float>()); parallel_sort(c); parallel_sort(d, std::greater<float>()); return 0; }