parallel_sort テンプレート関数

概要

シーケンスをソートします。

ヘッダー

#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 は次の表の要件をモデル化します。

RandomAccessIterator の値の型 T の要件

擬似署名

意味

void swap( T& x, T& y )

xy を交換します。

bool Compare::operator()( const T& x, const T& y )

xy の前に現れる場合は 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>());
}

関連情報