Стабильная сортировка сравнения с O (n * log (n)) временем и O (1) пространственной сложностью - PullRequest
Новая
       32

Стабильная сортировка сравнения с O (n * log (n)) временем и O (1) пространственной сложностью

6 голосов
/ 20 марта 2012

Проходя через список алгоритмов сортировки Википедии Я заметил, что нет стабильной сортировочной сравнения , которая имеет O(n*log(n)) (наихудший случай) сложность времени и O(1) (наихудший случай) пространство-сложность. Это, конечно, похоже на теоретическую границу, но я не смог найти больше информации об этом.

Как можно доказать это?

Примечание: я знаю о нижнем пределе O(n*log(n)) сложности времени в наихудшем случае для видов сравнения.

Ответы [ 2 ]

8 голосов
/ 20 марта 2012

Несмотря на то, что говорится в этой статье, можно сделать стабильную сортировку слиянием на месте O(n log n).

Здесь - это документ, объясняющий два способа реализацииэто.

0 голосов
/ 16 апреля 2013

Вот полная реализация C ++, которую я преобразовал из реализации C здесь : 

#include <algorithm>
#include <functional>

template<class It>
It rotate(It begin, It const middle, It end)
{
    typename std::iterator_traits<It>::difference_type i = 0, j;
    if (begin != middle && middle != end)
    {
        while ((i = std::distance(begin, middle)) !=
               (j = std::distance(middle, end)))
        {
            It k = middle;
            std::advance(
                k,
                std::max(
                    typename std::iterator_traits<It>::difference_type(),
                    j - i));
            std::swap_ranges(k, end, begin);
            if (i > j) { std::advance(begin, j); }
            else { std::advance(end, -i); }
        }
    }
    return std::swap_ranges(middle - i, middle, middle);
}

template<class It, class Less>
It bsearch(
    It begin, It left, It right,
    typename std::iterator_traits<It>::difference_type n,
    Less &less)
{
    while (left < right)
    {
        It const middle = left + std::distance(left, right) / 2;
        bool const b = !less(
            *(begin + (std::distance(middle, begin) + n)),
            *middle);
        (b ? left : right) = middle + b;
    }
    return left;
}

template<class It, class Less>
void merge(It const begin, It const middle, It const end, Less &less)
{
    bool naive_insertion_optimization = false;
    if (naive_insertion_optimization && std::distance(begin, end) < 0)
    {
        for (It i = middle; i != end; ++i)
        {
            for (It p = i; p != begin; --p)
            {
                if (!less(*p, *(p - 1)))
                {
                    break;
                }
                using std::iter_swap;
                iter_swap(p, p - 1);
            }
        }
    }
    else if (begin < middle && middle < end)
    {
        typename std::iterator_traits<It>::difference_type const
            half = std::distance(begin, end) / 2,
            left = std::distance(begin, middle),
            right = std::distance(middle, end);
        It const midpoint = begin + half;
        bool const b = left > right;
        It const i = bsearch(
            begin,
            b ? midpoint - right : begin,
            b ? midpoint : middle,
            half + left - 1,
            less);
        rotate(i, middle, begin + (std::distance(i, middle) + half));
        merge(begin, i, midpoint, less);
        merge(midpoint, midpoint + std::distance(i, middle), end, less);
    }
}

template<class It, class Less>
void sort(It const begin, It const end, Less &less)
{
    if (std::distance(begin, end) > 1)
    {
        It const middle = begin + std::distance(begin, end) / 2;
        sort(begin, middle, less);
        sort(middle, end, less);
        merge(begin, middle, end, less);
    }
}

template<class It>
void sort(It const begin, It const end)
{
    std::less<typename std::iterator_traits<It>::value_type> less;
    return sort(begin, end, less);
}
...