QuickSortの実装・補遺

少し整理。あとポインタだけでなく、イテレータ(ランダムアクセスイテレータ)でも使えるように記述を少し変更。

template<typename T>
void swap(T& lhs, T& rhs)
{
    T temp(lhs);
    lhs = rhs;
    rhs = temp;
}

template<typename iterator_t>
void qsort(iterator_t begin, iterator_t end)
{
    if((end - begin) <= 1)
        return;

    iterator_t left  = begin;
    iterator_t right = end - 1;
    iterator_t pivot = end - 1;

    while(left < right)
    {
        while((left < right) && (*left < *pivot))
            ++left;
        if(left == right)
            break;

        while((left < right) && (*pivot <= *right))
            --right;
        if(left == right)
            break;

        swap(*left, *right);
    }

    swap(*left, *pivot);

    qsort(begin, left);
    qsort(left + 1, end);
}

2009/06/14-訂正:最初、iterator_t right = end - 2;って書いてましたが、やっぱりこれだときちんと動きません。訂正しました。