なんとなーくアルゴリズムのお話など。
combsortてゆーソート・アルゴリズムがあります。
遅いので有名なbubblesortの改良版なんですけどね。
bubblesortがなして遅いかっちゅーと、隣接する二つの比較/交換を繰り返すので一回の交換で要素がちょびっとしか移動せんからなんですわ。
二要素間の距離を大きくとって交換し、次第に距離を狭めていくのがcombsortです。
#include <algorithm>
#include <iterator>
template<typename Iterator, typename Predicate>
void combsort(Iterator first, Iterator last, Predicate pred) {
auto gap = std::distance(first,last); // 要素間の距離:最初は要素数から
Iterator iter1, iter2;
bool swapped;
do {
gap = gap * 10 / 13; // ちょびっと狭める
if ( gap == 0 ) gap = 1;
swapped = false;
Iterator iter1 = first;
Iterator iter2 = first;
std::advance(iter2,gap); // iter1,iter2間をgapだけ離す
while ( iter2 != last ) { // これ以降はbubblesortと同じね
if ( pred(*iter2,*iter1) ) {
swapped = true;
std::iter_swap(iter1,iter2);
}
++iter1;
++iter2;
}
} while (swapped || gap != 1);
}
要素間の距離:gapが繰り返しのたんびに 1/1.3 になってます。
この1/1.3て値、あんまり大きいと荒っぽすぎて効果がないし、小さいとなかなか収束しない。
実験的に求められた"よさげな値"が1/1.3らしいす。