sort.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_SORT_HPP__
#define NEFORCE_CORE_ALGORITHM_SORT_HPP__

 
#include "NeForce/core/algorithm/compare.hpp"
#include "NeForce/core/algorithm/heap.hpp"
#include "NeForce/core/algorithm/merge.hpp"
#include "NeForce/core/algorithm/partition.hpp"
NEFORCE_BEGIN_NAMESPACE__



template <typename Iterator, typename Compare>
bool is_sorted(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return true;
    }
    Iterator next = _NEFORCE next(first);
    for (; next != last; ++first, ++next) {
        if (comp(*next, *first)) {
            return false;
        }
    }
    return true;
}

template <typename Iterator>
bool is_sorted(Iterator first, Iterator last) {
    return is_sorted(first, last, _NEFORCE less<>());
}

template <typename Iterator, typename Compare>
Iterator is_sorted_until(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return last;
    }
    Iterator next = _NEFORCE next(first);
    for (; next != last; ++first, ++next) {
        if (comp(*next, *first)) {
            return next;
        }
    }
    return last;
}

template <typename Iterator>
Iterator is_sorted_until(Iterator first, Iterator last) {
    return is_sorted_until(first, last, _NEFORCE less<>());
}

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<>());
}

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<>());
}

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<>());
}

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<>());
}

template <typename Iterator, typename Compare>
void merge_sort(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
 
    const auto n = _NEFORCE distance(first, last);
    if (n < 2) {
        return;
    }
    Iterator mid = first + n / 2;
    _NEFORCE merge_sort(first, mid, comp);
    _NEFORCE merge_sort(mid, last, comp);
    _NEFORCE inplace_merge(first, mid, last, comp);
}

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

template <typename Iterator, typename Compare>
void partial_sort(Iterator first, Iterator middle, Iterator last, Compare comp) {
    if (first == middle) {
        return;
    }
    _NEFORCE make_heap(first, middle, comp);
    for (Iterator i = middle; i < last; ++i) {
        if (comp(*i, *first)) {
            inner::pop_heap_aux(first, middle, i, *i, comp);
        }
    }
    _NEFORCE sort_heap(first, middle, comp);
}

template <typename Iterator>
void partial_sort(Iterator first, Iterator middle, Iterator last) {
    return _NEFORCE partial_sort(first, middle, last, _NEFORCE less<>());
}

template <typename Iterator1, typename Iterator2, typename Compare>
Iterator2 partial_sort_copy(Iterator1 first, Iterator1 last, Iterator2 result_first, Iterator2 result_last,
                            Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator1>, "Iterator must be input_iterator");
 
    if (result_first == result_last) {
        return result_last;
    }
    Iterator2 result_real_last = result_first;
    while (first != last && result_real_last != result_last) {
        *result_real_last = *first;
        ++result_real_last;
        ++first;
    }
    _NEFORCE make_heap(result_first, result_real_last, comp);
    while (first != last) {
        if (comp(*first, *result_first)) {
            _NEFORCE adjust_heap(result_first, 0, result_real_last - result_first, *first, comp);
        }
        ++first;
    }
    _NEFORCE sort_heap(result_first, result_real_last, comp);
    return result_real_last;
}

template <typename Iterator1, typename Iterator2>
Iterator2 partial_sort_copy(Iterator1 first, Iterator1 last, Iterator2 result_first, Iterator2 result_last) {
    return _NEFORCE partial_sort_copy(first, last, result_first, result_last, _NEFORCE less<>());
}

NEFORCE_BEGIN_INNER__

template <typename Iterator, typename T, typename Compare>
void __insertion_sort_aux(Iterator last, T value, Compare comp) {
    Iterator next = last;
    --next;
    while (comp(value, *next)) {
        *last = *next;
        last = next;
        --next;
    }
    *last = value;
}
 
NEFORCE_END_INNER__

template <typename Iterator, typename Compare>
void insertion_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;
    }
    for (Iterator i = first + 1; i != last; ++i) {
        iter_value_t<Iterator> value = *i;
        if (comp(value, *first)) {
            _NEFORCE copy_backward(first, i, i + 1);
            *first = value;
        } else {
            inner::__insertion_sort_aux(i, value, comp);
        }
    }
}

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

template <typename Iterator, typename Compare>
void introspective_sort(Iterator first, Iterator last, int depth_limit, Compare comp) {
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    while (first < last) {
        if (depth_limit == 0) {
            _NEFORCE partial_sort(first, last, last, comp);
            return;
        }
        --depth_limit;
 
        Iterator cut = _NEFORCE lomuto_partition(first, last, comp);
        if (cut - first < last - cut) {
            _NEFORCE introspective_sort(first, cut, depth_limit, comp);
            first = cut + 1;
        } else {
            _NEFORCE introspective_sort(cut + 1, last, depth_limit, comp);
            last = cut;
        }
    }
}

template <typename Iterator>
void introspective_sort(Iterator first, Iterator last, int depth_limit) {
    return _NEFORCE introspective_sort(first, last, depth_limit, _NEFORCE less<>());
}

template <typename Iterator, typename Compare>
void quick_sort(Iterator first, Iterator last, Compare comp) {
    if (first < last) {
        Iterator cut = _NEFORCE lomuto_partition(first, last, comp);
        _NEFORCE quick_sort(first, cut, comp);
        _NEFORCE quick_sort(cut + 1, last, comp);
    }
}

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

NEFORCE_BEGIN_INNER__

template <typename Iterator, typename Compare>
void __intro_sort_dispatch(Iterator first, Iterator last, int depth_limit, Compare comp) {
    while (last - first > MEMORY_ALIGN_THRESHHOLD) {
        if (depth_limit == 0) {
            _NEFORCE partial_sort(first, last, last, comp);
            return;
        }
        --depth_limit;
 
        Iterator cut = _NEFORCE lomuto_partition(first, last, comp);
 
        if (cut - first < last - cut) {
            inner::__intro_sort_dispatch(first, cut, depth_limit, comp);
            first = cut + 1;
        } else {
            inner::__intro_sort_dispatch(cut + 1, last, depth_limit, comp);
            last = cut;
        }
    }
}

NEFORCE_CONST_FUNCTION constexpr int __log2_int(int x) noexcept {
    int k = 0;
    for (; x > 1; x >>= 1) {
        ++k;
    }
    return k;
}
 
NEFORCE_END_INNER__

template <typename Iterator, typename Compare>
void sort(Iterator first, Iterator last, Compare comp) {
    if (first == last) {
        return;
    }
 
    inner::__intro_sort_dispatch(first, last, inner::__log2_int(last - first) * 2, comp);
    constexpr size_t threshhold = MEMORY_ALIGN_THRESHHOLD;
 
    if (last - first > threshhold) {
        _NEFORCE insertion_sort(first, first + threshhold, comp);
        for (Iterator i = first + threshhold; i != last; ++i) {
            inner::__insertion_sort_aux(i, *i, comp);
        }
    } else {
        _NEFORCE insertion_sort(first, last, comp);
    }
}

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

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void tim_sort(Iterator first, Iterator last, Compare comp) {
    if (first == last) {
        return;
    }
 
    constexpr int min_merge = 32;
    const auto n = _NEFORCE distance(first, last);
 
    if (n > 0) {
        Iterator i = first;
        while (i < last) {
            auto step = _NEFORCE min(static_cast<decltype(n)>(min_merge), last - i);
            Iterator end = _NEFORCE next(i, step);
            _NEFORCE insertion_sort(i, end, comp);
            i = end;
        }
    }
 
    for (int size = min_merge; size < n; size *= 2) {
        for (Iterator left = first; left < last;) {
            const auto remaining = _NEFORCE distance(left, last);
            if (remaining <= size) {
                break;
            }
 
            Iterator mid = _NEFORCE next(left, size);
            Iterator right = _NEFORCE next(left, _NEFORCE min(2 * size, static_cast<int>(remaining)));
 
            if (mid < right) {
                _NEFORCE inplace_merge(left, mid, right, comp);
            }
            left = right;
        }
    }
}

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

template <typename Iterator, typename Compare>
void nth_element(Iterator first, Iterator nth, Iterator last, Compare comp) {
    while (last - first > 3) {
        Iterator cut = _NEFORCE lomuto_partition(first, last, comp);
        if (cut <= nth) {
            first = cut + 1;
        } else {
            last = cut;
        }
    }
    _NEFORCE insertion_sort(first, last, comp);
}

template <typename Iterator>
void nth_element(Iterator first, Iterator nth, Iterator last) {
    return _NEFORCE nth_element(first, nth, last, _NEFORCE less<>());
}
 // SortAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_SORT_HPP__