sdf - Githubissues

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <windows.h>

using namespace std;

template <typename Iterator>
Iterator advance(const Iterator great, int shift)
{
    Iterator ans = great;
    if (0 < shift)
        while (ans - great < shift)
            ++ans;
    else
        while (great - ans < (-1) * shift)
            --ans;
    return ans;
}

template <typename Iterator>
void heap_sort(Iterator begin, Iterator end)
{
    make_heap(begin, end);
    for (Iterator step = end; step > begin; --step)
        pop_heap(begin, step);
}

template <typename Iterator>
void merge(Iterator begin, Iterator split, Iterator end)
{
    Iterator left = begin;
    Iterator right = split;
    vector <typename std::iterator_traits <Iterator>::value_type> result;
    while (left < split && right < end)
        if (*left < *right)
        {
            result.push_back(*left);
            ++left;
        }
        else
        {
            result.push_back(*right);
            ++right;
        }
    while (left < split)
    {
        result.push_back(*left);
        ++left;
    }
    while (right < end)
    {
        result.push_back(*right);
        ++right;
    }
    for (Iterator cur = begin; cur < end; ++cur)
        *cur = result[cur - begin];
}

template <typename Iterator>
void merge_sort(Iterator begin, Iterator end)
{
    if (end <= begin)
        return;
    if (end - begin < 30)
    {
        insert_sort(begin, end);
        return;
    }
    if (1 < end - begin)
    {
        Iterator split = advance(begin, (end - begin) / 2);
        merge_sort(begin, split);
        merge_sort(split, end);
        merge(begin, split, end);
    }
}

template <typename Iterator>
void insert_sort(Iterator begin, Iterator end)
{
    if (end <= begin)
        return;
    for (Iterator step = begin; end - step > 1; ++ step)
        for (Iterator find = step; begin <= find && *advance(find, 1) < *find; --find)
            std::iter_swap(find, advance(find, 1));
}

template <typename Iterator>
void selection_sort(Iterator begin, Iterator end)
{
    if (end <= begin)
        return;
    for (Iterator step = begin; step < end; ++step)
    {
        Iterator findmin = step;
        for (Iterator find = step; find < end; ++find)
            if (*find < *findmin)
                findmin = find;
        std::iter_swap(step, findmin);
    }
}

template <typename Iterator>
void quick_sort(Iterator begin, Iterator end)
{
    if (end <= begin)
        return;
    if (end - begin < 30)
    {
        insert_sort(begin, end);
        return;
    }

    int split = (end - begin);
    typename std::iterator_traits <Iterator>::value_type middle = *(advance(begin, rand() % split));
    Iterator left = begin;
    Iterator right = end;
    --right;
    while (left <= right)
    {
        while (left < end && *left < middle)
            ++left;
        while (begin <= right && middle < *right)
            --right;
        if (left <= right && left < end && begin <= right)
        {
            std::iter_swap(left, right);
            --right;
            ++left;
        }
    }
    if (end - right > 1)
        ++right;
    if (1 < end - left)
        quick_sort(left, end);
    if (1 < right - begin)
        quick_sort(begin, right);
}
template <typename Iterator>
bool check(Iterator begin, Iterator end)
{
    for (Iterator step = advance(begin, 1); step < end; ++step)
        if (*step < *advance(step, -1))
            return false;
    return true;
}
int main()
{
    vector <int> pudge;
    vector <int> coppy;
    vector<int>::iterator cur;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        pudge.push_back(rand() % 1000);
    coppy = pudge;
    int t_start =  GetTickCount();
    quick_sort(pudge.begin(), pudge.end());
    cout << GetTickCount() - t_start << " ms Quick_sort" << endl;
    if (not check(pudge.begin(), pudge.end()))
        return 0;

    pudge = coppy;
    t_start =  GetTickCount();
    heap_sort(pudge.begin(), pudge.end());
    cout << GetTickCount() - t_start << " ms Heap_sort" << endl;
    if (not check(pudge.begin(), pudge.end()))
        return 0;

    pudge = coppy;
    t_start =  GetTickCount();
    merge_sort(pudge.begin(), pudge.end());
    cout << GetTickCount() - t_start << " ms Merge_sort" << endl;
    if (not check(pudge.begin(), pudge.end()))
        return 0;

    pudge = coppy;
    t_start =  GetTickCount();
    std::sort(pudge.begin(), pudge.end());
    cout << GetTickCount() - t_start << " ms std::Sort" << endl;

    /*for (cur = pudge.begin(); cur < pudge.end(); ++cur)
        cout << *cur << " ";*/
    return 0;
}
Original issue reported on code.google.com by cyxanovz...@gmail.com on 29 Sep 2013 at 10:45
fuzan / rietveld

sdf #464
