ツンデレソート

「最初の方はぐちゃぐちゃだけど徐々に整列されていく」というツンデレソートってのがあるそうです。
私も作ってみたのですが、なかなか難しいです。

#include <stdlib.h>
#include <math.h>

template< typename T >
class Tundere {
private:
    T tmin;
    double average;        // 平均
    double average2;    // 2乗平均
    double count;        // カウント
    static const int width = 4;       // 分散の幅

public:
    Tundere():tmin(0),average(0),average2(0),count(-1){}

    bool operator()(T a, T b) {
        if (count < 0) {
            average = ((double)(a+b))/2.0;
            average2 = ((double)(a*a+b*b))/2.0;
            count = 0;
        } else {
            average = average*(count/(count+2.0)) + ((double)(a+b))/(count+2.0);
            average2 = average2*(count/(count+2.0)) + ((double)(a*a+b*b))/(count+2.0);
        }
        count += 2;
        tmin = std::min(tmin, std::min(a,b));   // 最小値を保存
        double variance = average2 - average*average;    // 分散
        double x = std::max(a,b);
        if (average + sqrt(variance)/((double)width) - (double)tmin + 1.0 < 1.0) return false;        // エラー?
        int prob = (double)(100.0*log(x + 1.0 - (double)tmin)/log(average + sqrt(variance)/((double)width) - (double)tmin + 1.0));
        int dummyrand = 0;
        T c = a + b;
        for (int i = 0; i < sizeof(T); i++) {
            dummyrand = 31 * dummyrand + ((char*)&c)[i];
        }
        dummyrand %= 100;
        if (dummyrand < prob) {
            return (a < b);
        } else {
            return false;
        }
    }
};

以下のように使います。

int main(int argc, char* argv[])
{
	std::vector< int > target;

	for (int i = 0; i < 3000; i++) {
		target.push_back(rand()%3000);
	}


	std::sort(target.begin(), target.end(), Tundere<int>());
	for (int i = 0; i < target.size(); i++) {
		std::cout << target[i] << std::endl;
	}

	return 0;
}

平均値（のようなもの）と分散（のようなもの）を逐次更新していき、平均値＋分散/4より大きいところでは正しい比較結果を返し、そうでないときは適当な結果を返すようになっています。確率を決定する乱数にrandを使いたくなかったのでJava流ハッシュ計算方法を用い、閾値には怪しく適当なLog関数を用いています。
結果は下記みたいになりますが、分散が大きいデータではうまくいかないらしいです。
うまくいった（？）例
適当な確率なんて使わない方がいいかもしれません。というかツンデレソート意外と難しいです。

以上