QuickSortの実装を学習しなおしました

でも、釈然としないのはなぜだろう?

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

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

    T* left  = begin;
    T* right = end - 1;
    T  pivot = *right;

    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, end - 1);

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

テスト。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstdlib>

int main(int, char* [])
{
    static const int N = 20;

    int n[N];
    for(int i = 0; i < N; ++i)
    {
        n[i] = std::rand() % 900 + 100;
    }

    std::cout << "before:";
    std::copy(n, n + N, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    qsort(n, n + N);

    std::cout << "after :"; 
    std::copy(n, n + N, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

結果。

before:707 449 573 858 230 972 844 378 423 209 640 765 592 342 487 903 827 629 440 812 
after :209 230 342 378 423 440 449 487 573 592 629 640 707 765 812 827 844 858 903 972