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 );

説明

シーケンスまたはコンテナーをソートします。ソートは不安定で再現性がありません。等しいキーの相対的な順序は保存されず、同じシーケンスを再度ソートした場合でも同じ結果になる保証はありません。イテレーターとシーケンスの要件は、std::sort と同じです。具体的には、RandomAccessIterator はランダムアクセス・イテレーターであり、その値の型 T は次の表の要件をモデル化します。

呼び出し 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;
}