Class QuickSort

examples/sort.cpp:308–361

};

class QuickSort : public CppBenchmark::Benchmark, public SortFixture
{
public:
    using Benchmark::Benchmark;

protected:
    void Run(CppBenchmark::Context& context) override
    {
        // Generate items to sort
        std::generate(items.begin(), items.end(), rand);

        // Sort items
        if (items.size() > 0)
            QuickSortInternal(items, 1, items.size());
        context.metrics().AddItems(items.size());
    }

private:
    static void QuickSortInternal(std::vector<int>& subitems, size_t left, size_t right)
    {
        // Choose the pivot item
        int pivot = subitems[left + ((right - left) / 2) - 1];

        size_t l = left;
        size_t r = right;

        while (l <= r)
        {
            // Move left if item is less than pivot
            while ((l < right) && (subitems[l - 1] < pivot))
                l++;
            // Move right if item is less than pivot
            while ((r > left) && (subitems[r - 1] > pivot))
                r--;

            if (l <= r)
            {
                // Swap left and right items
                std::swap(subitems[l - 1], subitems[r - 1]);

                // Move left and right indexes
                ++l;
                --r;
            }
        }

        // Perform quick sort operation for the left sub items
        if (left < r)
            QuickSortInternal(subitems, left, r);
        // Perform quick sort operation for the right sub items
        if (l < right)
            QuickSortInternal(subitems, l, right);
    }
};

class QuickSort3 : public CppBenchmark::Benchmark, public SortFixture
{