슈퍼 버블 정렬

버블 소트를 극한까지 빨리 해보고 싶습니다.

첫째, 거품 정렬을 개선한 몇 가지가 있지만,
인접한 요소를 교환한다는 고문이 있는 이상 교환하는 횟수는 모두 동일합니다.
즉, 속도를 높이려면 여분의 비교를 줄일 수 있습니다.

유명한 비교 수를 줄이는 것은 마지막 교환 전까지만 비교한다는 것입니다.
그림으로 보겠습니다.

빨간 부분이 마지막 교환이었다면 다음은 파란색 부분까지 비교하면 됩니다.

또, 스타트 위치도 도중부터 스타트 시키는 것을 생각합니다.
첫번째 교환이 붉은 부분이었다면 다음은 파란색 부분의 비교에서 시작하면 됩니다.

이 생각을 발전하면, 전회의 장소에서 교환이 있으면, 다음은 그 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%)

느립니다. 안돼요.

생각해 보면 당연합니다.
실은 삽입 소트하고, 비교수가 최저라고 하는 조건을 채우고 있습니다.
즉, 이 슈퍼 버블 소트는, 삽입 소트를 큐라고 하는 구조를 사용해,
귀찮게 구현했을 뿐입니다.