バブルソートを極限まで早くしてみたいと思います。
まず、バブルソートを改良したものはいくつかありますが、
隣り合った要素を交換する、という枷がある以上、交換する回数はどれも同じです。
つまり、高速化するには余分な比較を減らすしかありません。
有名な比較数の削減は、最後の交換の手前までしか比較しない、というものです。
図で見ていきます。
赤い部分が最後の交換だった場合、次は青い部分まで比較すればいいです。
また、スタート位置も途中からスタートさせることを考えます。
最初の交換が赤い部分だった場合、次は青い部分の比較からスタートすればいいです。
この考えを発展すると、前回の場所で交換があったら、次はその1個手前の場所だけ比較すればいいのです。
n個の要素の場合、(n-1)+(交換回数)回の比較だけで済みます。
それではプログラムを書いていきます。
まずは最初にズラッと舐めて、交換が発生したら、一個手前の場所をキューに入れます。
あとはキューがなくなるまでそれを繰り返します。
superbubble.cpp
# include <vector>
# include <algorithm>
# include <iostream>
# include <boost/timer/timer.hpp>
# include <boost/circular_buffer.hpp>
template<typename T>
bool ifswap(T &d1, T &d2){
if (d1 > d2) {std::swap(d1, d2); return true;}
return false;
}
template<typename iterator>
void bsort(iterator first, iterator last){
boost::circular_buffer<iterator> data(std::distance(first, last));
for (auto it = first; it != last; ++it) data.push_back(it);
if (!data.empty()) data.pop_back();
while(!data.empty()){
auto &it = data.front();
if (ifswap(*it, *(it + 1)) && it != first) data.push_back(it - 1);
data.pop_front();
}
}
int main(){
const int size = 32;
std::vector<int> v(size);
for (int i = 0; i < size; i++)v[i] = i;
std::random_shuffle(v.begin(), v.end());
auto v2 = v;
{
boost::timer::auto_cpu_timer t;
bsort(v.begin(), v.end());
// std::sort(v.begin(), v.end());
std::cout << std::is_sorted(v.begin(), v.end()) << std::endl;
}
return 0;
}
さて、速度比較です。
std::sortと比べてどのぐらい早いのか…。
要素数が32個の場合は、std::sortは挿入ソートを行います。
std::sort
0.000017s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
bsort
0.000042s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)
遅いですね。駄目ですね。
考えてみれば当然です。
実は挿入ソートって、比較数が最低という条件を満たしているんです。
つまり、このスーパーバブルソートは、挿入ソートをキューという仕組みを使って、
めんどくさく実装しただけ、ということになります。