#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 );
シーケンスまたはコンテナーの unstable ソートを行います。unstable ソートは、等しいキーの相対的な順序を保存しません。ソートは再現性があり、同じシーケンスのソートは毎回同じ結果になります。イテレーターとシーケンスの要件は、std::sort と同じです。具体的には、RandomAccessIterator はランダムアクセス・イテレーターであり、その値の型 T は次の表の要件をモデル化します。
擬似署名 |
意味 |
---|---|
void swap( T& x, T& y ) |
x と y を交換します。 |
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]; void SortExample() { 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>()); }