qsort_array

2019年6月19日2021年6月19日

qsort_arrayはQuickSortアルゴリズムの実装です。operator []インターフェースのような配列を持つものはすべてソートされます。クイックソートが不安定になると、ヒープソートに切り替わります。このように、ソートは最大でN * log（N）時間かかることが保証されています。

#include <dlib / sort.h>

    template <
        typename T,
        typename compare
        >
    inline void qsort_array (
        T& array,
        unsigned long left,
        unsigned long right,
        const compare& comp 
    );
    /*!
        requires
            - T implements operator[]                                 
            - the items in array must be comparable by comp where comp is a function
              object with the same syntax as std::less<>
            - the items in array must be swappable by a global swap()   
            - left and right are within the bounds of array
              i.e. array[left] and array[right] are valid elements
            - left <= right
        ensures
            - for all elements in #array between and including left and right the 
              ith element is < the i+1 element
            - sorts using a quick sort algorithm
    !*/

関連