ext_sort.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_EXT_SORT_HPP__
#define NEFORCE_CORE_ALGORITHM_EXT_SORT_HPP__

 
#include "NeForce/core/algorithm/leonardo_heap.hpp"
NEFORCE_BEGIN_NAMESPACE__



template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void bubble_sort(Iterator first, Iterator last, Compare comp) {
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return;
    }
    Iterator end = last;
    --end;
    auto revend = _NEFORCE make_reverse_iterator(first);
    auto revstart = _NEFORCE make_reverse_iterator(end);
    for (auto iter = revstart; iter != revend; ++iter) {
        bool not_finished = false;
        Iterator curend = iter.base();
        for (Iterator it = first; it != curend; ++it) {
            Iterator next = it;
            ++next;
            if (comp(*next, *it)) {
                _NEFORCE iter_swap(it, next);
                not_finished = true;
            }
        }
        if (!not_finished) {
            break;
        }
    }
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void bubble_sort(Iterator first, Iterator last) {
    return _NEFORCE bubble_sort(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void cocktail_sort(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_bid_iter_v<Iterator>, "Iterator must be bidirectional_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return;
    }
    bool swapped = true;
    Iterator left = first;
    Iterator right = last;
    --right;
    while (swapped) {
        swapped = false;
        for (Iterator i = left; i != right; ++i) {
            Iterator next = i;
            ++next;
            if (comp(*next, *i)) {
                _NEFORCE iter_swap(i, next);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
        --right;
        swapped = false;
        for (Iterator i = right; i != left; --i) {
            Iterator prev = i;
            --prev;
            if (comp(*i, *prev)) {
                _NEFORCE iter_swap(i, prev);
                swapped = true;
            }
        }
        ++left;
    }
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void cocktail_sort(Iterator first, Iterator last) {
    return _NEFORCE cocktail_sort(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void select_sort(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterator must be forward_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return;
    }
    for (Iterator i = first; i != last; ++i) {
        Iterator min = i;
        Iterator j = i;
        ++j;
        for (; j != last; ++j) {
            if (comp(*j, *min)) {
                min = j;
            }
        }
        _NEFORCE iter_swap(i, min);
    }
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void select_sort(Iterator first, Iterator last) {
    return _NEFORCE select_sort(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename Iterator, typename Compare, enable_if_t<is_ranges_rnd_iter_v<Iterator>, int> = 0>
NEFORCE_CONSTEXPR20 void shell_sort(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return;
    }
    auto dist = _NEFORCE distance(first, last);
    for (auto gap = dist / 2; gap > 0; gap /= 2) {
        for (Iterator i = first + gap; i < last; ++i) {
            iter_value_t<Iterator> temp = *i;
            Iterator j;
            for (j = i; j >= first + gap && comp(temp, *(j - gap)); j -= gap) {
                *j = *(j - gap);
            }
            *j = _NEFORCE move(temp);
        }
    }
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void shell_sort(Iterator first, Iterator last) {
    return _NEFORCE shell_sort(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename Iterator, typename Compare, typename IndexMapper>
NEFORCE_CONSTEXPR20 void counting_sort(Iterator first, Iterator last, Compare comp, IndexMapper mapper) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
    static_assert(is_invocable_v<IndexMapper, decltype(*first)>, "IndexMapper must be invocable");
 
    if (first == last) {
        return;
    }
    auto min_max = _NEFORCE minmax_element(first, last, comp);
    auto min_val = mapper(*min_max.first);
    auto max_val = mapper(*min_max.second);
    const auto range = static_cast<size_t>(max_val - min_val + 1);
    vector<int> count(range, 0);
 
    for (Iterator it = first; it != last; ++it) {
        auto value = mapper(*it);
        if (value < min_val || value > max_val) {
            NEFORCE_THROW_EXCEPTION(iterator_exception("element out of range for counting sort."));
        }
        ++count[static_cast<size_t>(value - min_val)];
    }
 
    for (size_t i = 1; i < count.size(); ++i) {
        count[i] += count[i - 1];
    }
 
    vector<iter_value_t<Iterator>> sorted(_NEFORCE distance(first, last));
    auto bound = _NEFORCE make_reverse_iterator(first);
 
    for (auto rit = _NEFORCE make_reverse_iterator(last); rit != bound; ++rit) {
        auto value = mapper(*rit);
        const auto index = static_cast<size_t>(value - min_val);
        size_t position = --count[index];
        sorted[position] = *rit;
    }
    _NEFORCE copy(sorted.begin(), sorted.end(), first);
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void counting_sort(Iterator first, Iterator last) {
    _NEFORCE counting_sort(first, last, _NEFORCE less<iter_value_t<Iterator>>(),
                           _NEFORCE identity<iter_value_t<Iterator>>());
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void bucket_sort_less(Iterator first, Iterator last) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterator must be forward_iterator");
 
    using T = iter_value_t<Iterator>;
    pair<Iterator, Iterator> min_max = _NEFORCE minmax_element(first, last);
    T min_val = *min_max.first;
    T max_val = *min_max.second;
    T range = max_val - min_val + 1;
    vector<size_t> bucket(range, 0);
 
    for (Iterator it = first; it != last; ++it) {
        ++bucket[*it - min_val];
    }
 
    Iterator index = first;
 
    for (size_t i = 0; i < bucket.size(); ++i) {
        while (bucket[i] > 0) {
            *index++ = static_cast<T>(i + min_val);
            --bucket[i];
        }
    }
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void bucket_sort_greater(Iterator first, Iterator last) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterator must be forward_iterator");
 
    using T = iter_value_t<Iterator>;
    pair<Iterator, Iterator> min_max = _NEFORCE minmax_element(first, last);
    T min_val = *min_max.first;
    T max_val = *min_max.second;
    T range = max_val - min_val + 1;
    vector<size_t> bucket(range, 0);
 
    for (Iterator it = first; it != last; ++it) {
        ++bucket[*it - min_val];
    }
 
    Iterator index = first;
 
    for (size_t i = bucket.size(); i-- > 0;) {
        while (bucket[i] > 0) {
            *index++ = static_cast<T>(i + min_val);
            --bucket[i];
        }
    }
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void bucket_sort(Iterator first, Iterator last) {
    _NEFORCE bucket_sort_less(first, last);
}

NEFORCE_BEGIN_INNER__
 
template <typename Iterator>
int __max_bit_aux(Iterator first, Iterator last) {
    auto max_num = *_NEFORCE max_element(first, last, [](const auto& a, const auto& b) -> bool { return a < b; });
    int p = 0;
    while (max_num > 0) {
        p++;
        max_num = max_num / 10;
    }
    return p;
}
 
template <typename T>
int __get_number_aux(T num, T d) {
    int p = 1;
    for (T i = 1; i < d; ++i) {
        p *= 10;
    }
    return num / p % 10;
}
 
NEFORCE_END_INNER__

template <typename Iterator, typename Mapper>
NEFORCE_CONSTEXPR20 void radix_sort_less(Iterator first, Iterator last, Mapper mapper) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
    static_assert(is_invocable_v<Mapper, decltype(*first)>, "Mapper must be invocable");
 
    if (first == last) {
        return;
    }
    using Mapped = remove_reference_t<decltype(mapper(*first))>;
 
    auto length = _NEFORCE distance(first, last);
    vector<Mapped> mapped_values(length);
    vector<iter_value_t<Iterator>> bucket(length);
    vector<int> count(10);
    Iterator it = first;
 
    for (auto& value: mapped_values) {
        value = mapper(*it++);
    }
 
    for (int d = 1; d <= inner::__max_bit_aux(mapped_values.begin(), mapped_values.end()); ++d) {
        _NEFORCE fill(count.begin(), count.end(), 0);
        for (const auto& num: mapped_values) {
            ++count[inner::__get_number_aux(num, d)];
        }
 
        for (size_t i = 1; i < count.size(); ++i) {
            count[i] += count[i - 1];
        }
        for (auto iter = mapped_values.rbegin(); iter != mapped_values.rend(); ++iter) {
            const int k = inner::__get_number_aux(*iter, d);
            bucket[--count[k]] = *(first + _NEFORCE distance(mapped_values.begin(), iter.base() - 1));
        }
 
        it = first;
        for (const auto& value: bucket) {
            *it++ = value;
        }
 
        it = first;
        for (auto& value: mapped_values) {
            value = mapper(*it++);
        }
    }
}

template <typename Iterator, typename Mapper>
NEFORCE_CONSTEXPR20 void radix_sort_greater(Iterator first, Iterator last, Mapper mapper) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
    static_assert(is_invocable_v<Mapper, decltype(*first)>, "Mapper must be invocable");
 
    if (first == last) {
        return;
    }
    using Mapped = remove_cvref_t<decltype(mapper(*first))>;
 
    iter_difference_t<Iterator> length = _NEFORCE distance(first, last);
    vector<Mapped> mapped_values(length);
    vector<iter_value_t<Iterator>> bucket(length);
    vector<int> count(10);
    Iterator it = first;
 
    for (auto& value: mapped_values) {
        value = mapper(*it++);
    }
    for (int d = 1; d <= inner::__max_bit_aux(mapped_values.begin(), mapped_values.end()); ++d) {
        _NEFORCE fill(count.begin(), count.end(), 0);
        for (const auto& num: mapped_values) {
            ++count[inner::__get_number_aux(num, d)];
        }
 
        for (size_t i = count.size() - 1; i > 0; --i) {
            count[i - 1] += count[i];
        }
 
        for (auto iter = mapped_values.rbegin(); iter != mapped_values.rend(); ++iter) {
            const int k = inner::__get_number_aux(*iter, d);
            bucket[--count[k]] = *(first + _NEFORCE distance(mapped_values.begin(), iter.base() - 1));
        }
 
        it = first;
        for (const auto& value: bucket) {
            *it++ = value;
        }
 
        it = first;
        for (auto& value: mapped_values) {
            value = mapper(*it++);
        }
    }
}

template <typename Iterator, typename Mapper = _NEFORCE identity<iter_value_t<Iterator>>>
NEFORCE_CONSTEXPR20 void radix_sort(Iterator first, Iterator last, Mapper mapper = Mapper()) {
    _NEFORCE radix_sort_less(first, last, mapper);
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void smooth_sort(Iterator first, Iterator last) {
    _NEFORCE make_leonardo_heap(first, last);
    _NEFORCE sort_leonardo_heap(first, last);
}

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void tim_sort(Iterator first, Iterator last, Compare comp) {
    constexpr int min_merge = 32;
    iter_difference_t<Iterator> n = _NEFORCE distance(first, last);
    for (Iterator i = first; i < last; i += min_merge) {
        Iterator end = _NEFORCE min(i + min_merge, last);
        _NEFORCE insertion_sort(i, end, comp);
    }
    for (int size = min_merge; size < n; size *= 2) {
        for (Iterator left = first; left < last; left += 2 * size) {
            Iterator mid = left + size;
            Iterator right = _NEFORCE min(left + 2 * size, last);
            if (mid < right) {
                _NEFORCE inplace_merge(left, mid, right, comp);
            }
        }
    }
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void tim_sort(Iterator first, Iterator last) {
    return _NEFORCE tim_sort(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename Iterator, typename Compare>
void monkey_sort(Iterator first, Iterator last, Compare comp) {
    while (!_NEFORCE is_sorted(first, last, comp)) {
        _NEFORCE shuffle(first, last);
    }
}

template <typename Iterator>
void monkey_sort(Iterator first, Iterator last) {
    return _NEFORCE monkey_sort(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}
 // SortAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_EXT_SORT_HPP__