partial_sort

std::partial_sortは、先頭から決められた数だけソートします。例えば、

#include <iostream>
#include <algorithm>

int main() {
    int a[] = { 7, 2, 5, 1, 6, 8, 3, 9, 4 };
    const int   size = sizeof(a) / sizeof(a[0]);
    std::partial_sort(a, a + 4, a + size);
    for(int i = 0; i < size; i++)
        std::cout << a[i] << " ";
    std::cout << std::endl;
}

とすると頭から4つまでは正しく並び替えられます。

1 2 3 4 7 8 6 9 5

std::sortと速度を比較します。全てソートする場合です。

#include <iostream>
#include <algorithm>
#include <map>
#include <windows.h>

#pragma comment(lib, "winmm.lib")

const int   N = 1000000;

void init(int *a, int n) {
    a[0] = n / 3;
    a[1] = n / 2;
    for(int k = 2; k < n; k++) {
        a[k] = (a[k-1] + a[k-2]) & 0xFFFF;
    }
}

double bench_sort(int n) {
    int *a = new int[n];
    init(a, n);
    int *b = new int[n];
    const int   t = timeGetTime();
    const int   num_iteration = N / n;
    for(int k = 0; k < num_iteration; k++) {
        std::copy(a, a + n, b);
        std::sort(b, b + n);
    }
    double  dt = (double)(timeGetTime() - t) / num_iteration;
    delete [] a;
    delete [] b;
    return dt;
}

double bench_partial_sort(int n, int m) {
    int *a = new int[n];
    init(a, n);
    int *b = new int[n];
    const int   t = timeGetTime();
    const int   num_iteration = N / n;
    for(int k = 0; k < num_iteration; k++) {
        std::copy(a, a + n, b);
        std::partial_sort(b, b + m, b + n);
    }
    double  dt = (double)(timeGetTime() - t) / num_iteration;
    delete [] a;
    delete [] b;
    return dt;
}

int main() {
    const int   N = 100;
    const int   a[] = { 100, 1000, 10000, 100000 };
    const int   n = sizeof(a) / sizeof(int);
    for(int k = 0; k < n; k++) {
        double  t1 = 0.0;
        double  t2 = 0.0;
        for(int i = 0; i < N; i++) {
            t1 += bench_sort(a[k]);
            t2 += bench_partial_sort(a[k], a[k]);
        }
        std::cout << a[k] << " " << t1 / N << " " << t2 / N << std::endl;
    }
}

以下は、ソート1回あたりにかかる時間(ms)です。

n	sort	partial..	ratio
100	0.00333	0.0054	1.62
1000	0.0747	0.0992	1.33
10000	1.042	1.266	1.22
100000	12.95	16.92	1.31

partial_sortのほうが1.2から1.6倍程度時間がかかるようです。意外と速いですね。
今度は部分的にソートします。この時間を配列の大きさで割ります。

だいたい下に凸で、ソートする部分の長さをmとすると、log m / log n * (sortの時間)よりもmが大きいところよりも時間が短いようです。