// Written in the D programming language./**This is a submodule of $(MREF std, algorithm).It contains generic sorting algorithms. $(SCRIPT inhibitQuickIndex = 1;)$(BOOKTABLE Cheat Sheet,$(TR $(TH Function Name) $(TH Description))$(T2 completeSort,        If `a = [10, 20, 30]` and `b = [40, 6, 15]`, then        `completeSort(a, b)` leaves `a = [6, 10, 15]` and `b = [20, 30, 40]`.        The range `a` must be sorted prior to the call, and as a result the        combination `$(REF chain, std,range)(a, b)` is sorted.)$(T2 isPartitioned,        `isPartitioned!"a < 0"([-1, -2, 1, 0, 2])` returns `true` because        the predicate is `true` for a portion of the range and `false`        afterwards.)$(T2 isSorted,        `isSorted([1, 1, 2, 3])` returns `true`.)$(T2 isStrictlyMonotonic,        `isStrictlyMonotonic([1, 1, 2, 3])` returns `false`.)$(T2 ordered,        `ordered(1, 1, 2, 3)` returns `true`.)$(T2 strictlyOrdered,        `strictlyOrdered(1, 1, 2, 3)` returns `false`.)$(T2 makeIndex,        Creates a separate index for a range.)$(T2 merge,        Lazily merges two or more sorted ranges.)$(T2 multiSort,        Sorts by multiple keys.)$(T2 nextEvenPermutation,        Computes the next lexicographically greater even permutation of a range        in-place.)$(T2 nextPermutation,        Computes the next lexicographically greater permutation of a range        in-place.)$(T2 nthPermutation,        Computes the nth permutation of a range        in-place.)$(T2 partialSort,        If `a = [5, 4, 3, 2, 1]`, then `partialSort(a, 3)` leaves        `a[0 .. 3] = [1, 2, 3]`.        The other elements of `a` are left in an unspecified order.)$(T2 partition,        Partitions a range according to a unary predicate.)$(T2 partition3,        Partitions a range according to a binary predicate in three parts (less        than, equal, greater than the given pivot). Pivot is not given as an        index, but instead as an element independent from the range's content.)$(T2 pivotPartition,        Partitions a range according to a binary predicate in two parts: less        than or equal, and greater than or equal to the given pivot, passed as        an index in the range.)$(T2 schwartzSort,        Sorts with the help of the $(LINK2 https://en.wikipedia.org/wiki/Schwartzian_transform, Schwartzian transform).)$(T2 sort,        Sorts.)$(T2 topN,        Separates the top elements in a range, akin to $(LINK2 https://en.wikipedia.org/wiki/Quickselect, Quickselect).)$(T2 topNCopy,        Copies out the top elements of a range.)$(T2 topNIndex,        Builds an index of the top elements of a range.)) Copyright: Andrei Alexandrescu 2008-. License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). Authors: $(HTTP erdani.com, Andrei Alexandrescu) Source: $(PHOBOSSRC std/algorithm/sorting.d) Macros:T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) */module std.algorithm.sorting; import std.algorithm.mutation : SwapStrategy;import std.functional : unaryFun, binaryFun;import std.range.primitives;import std.typecons : Flag, No, Yes;import std.meta : allSatisfy;import std.range : SortedRange;import std.traits; /**Specifies whether the output of certain algorithm is desired in sortedformat. If set to `SortOutput.no`, the output should not be sorted. Otherwise if set to `SortOutput.yes`, the output should be sorted. */alias SortOutput = Flag!"sortOutput"; // completeSort/**Sorts the random-access range `chain(lhs, rhs)` according topredicate `less`. The left-hand side of the range `lhs` is assumed to be already sorted;`rhs` is assumed to be unsorted.The exact strategy chosen depends on the relative sizes of `lhs` and`rhs`.  Performs $(BIGOH lhs.length + rhs.length * log(rhs.length))(best case) to $(BIGOH (lhs.length + rhs.length) * log(lhs.length +rhs.length)) (worst-case) evaluations of $(REF_ALTTEXT swap, swap, std,algorithm,mutation). Params:    less = The predicate to sort by.    ss = The swapping strategy to use.    lhs = The sorted, left-hand side of the random access range to be sorted.    rhs = The unsorted, right-hand side of the random access range to be        sorted.*/void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,        Lhs , Rhs)(SortedRange!(Lhs, less) lhs, Rhs rhs)if (hasLength!(Rhs) && hasSlicing!(Rhs)        && hasSwappableElements!Lhs && hasSwappableElements!Rhs){    import std.algorithm.mutation : bringToFront;    import std.range : chain, assumeSorted;    // Probably this algorithm can be optimized by using in-place    // merge    auto lhsOriginal = lhs.release();    foreach (i; 0 .. rhs.length)    {        auto sortedSoFar = chain(lhsOriginal, rhs[0 .. i]);        auto ub = assumeSorted!less(sortedSoFar).upperBound(rhs[i]);        if (!ub.length) continue;        bringToFront(ub.release(), rhs[i .. i + 1]);    }} ///@safe unittest{    import std.range : assumeSorted;    int[] a = [ 1, 2, 3 ];    int[] b = [ 4, 0, 6, 5 ];    completeSort(assumeSorted(a), b);    assert(a == [ 0, 1, 2 ]);    assert(b == [ 3, 4, 5, 6 ]);} // isSorted/**Checks whether a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)is sorted according to the comparison operation `less`. Performs $(BIGOH r.length)evaluations of `less`. Unlike `isSorted`, `isStrictlyMonotonic` does not allow for equal values,i.e. values for which both `less(a, b)` and `less(b, a)` are false. With either function, the predicate must be a strict ordering just like with`isSorted`. For example, using `"a <= b"` instead of `"a < b"` isincorrect and will cause failed assertions. Params:    less = Predicate the range should be sorted by.    r = Forward range to check for sortedness. Returns:    `true` if the range is sorted, false otherwise. `isSorted` allows    duplicates, `isStrictlyMonotonic` not.*/bool isSorted(alias less = "a < b", Range)(Range r)if (isForwardRange!(Range)){    if (r.empty) return true;     static if (isRandomAccessRange!Range && hasLength!Range)    {        immutable limit = r.length - 1;        foreach (i; 0 .. limit)        {            if (!binaryFun!less(r[i + 1], r[i])) continue;            assert(                !binaryFun!less(r[i], r[i + 1]),                "Predicate for isSorted is not antisymmetric. Both" ~                        " pred(a, b) and pred(b, a) are true for certain values.");            return false;        }    }    else    {        auto ahead = r.save;        ahead.popFront();        size_t i;         for (; !ahead.empty; ahead.popFront(), r.popFront(), ++i)        {            if (!binaryFun!less(ahead.front, r.front)) continue;            // Check for antisymmetric predicate            assert(                !binaryFun!less(r.front, ahead.front),                "Predicate for isSorted is not antisymmetric. Both" ~                        " pred(a, b) and pred(b, a) are true for certain values.");            return false;        }    }    return true;} ///@safe unittest{    assert([1, 1, 2].isSorted);    // strictly monotonic doesn't allow duplicates    assert(![1, 1, 2].isStrictlyMonotonic);     int[] arr = [4, 3, 2, 1];    assert(!isSorted(arr));    assert(!isStrictlyMonotonic(arr));     assert(isSorted!"a > b"(arr));    assert(isStrictlyMonotonic!"a > b"(arr));     sort(arr);    assert(isSorted(arr));    assert(isStrictlyMonotonic(arr));} @safe unittest{    import std.conv : to;     // https://issues.dlang.org/show_bug.cgi?id=9457    auto x = "abcd";    assert(isSorted(x));    auto y = "acbd";    assert(!isSorted(y));     int[] a = [1, 2, 3];    assert(isSorted(a));    int[] b = [1, 3, 2];    assert(!isSorted(b));     // ignores duplicates    int[] c = [1, 1, 2];    assert(isSorted(c));     dchar[] ds = "コーヒーが好きです"d.dup;    sort(ds);    string s = to!string(ds);    assert(isSorted(ds));  // random-access    assert(isSorted(s));   // bidirectional} @nogc @safe nothrow pure unittest{    static immutable a = [1, 2, 3];    assert(a.isSorted);} /// dittobool isStrictlyMonotonic(alias less = "a < b", Range)(Range r)if (isForwardRange!Range){    import std.algorithm.searching : findAdjacent;    return findAdjacent!((a,b) => !binaryFun!less(a,b))(r).empty;} @safe unittest{    import std.conv : to;     assert("abcd".isStrictlyMonotonic);    assert(!"aacd".isStrictlyMonotonic);    assert(!"acb".isStrictlyMonotonic);     assert([1, 2, 3].isStrictlyMonotonic);    assert(![1, 3, 2].isStrictlyMonotonic);    assert(![1, 1, 2].isStrictlyMonotonic);     // ー occurs twice -> can't be strict    dchar[] ds = "コーヒーが好きです"d.dup;    sort(ds);    string s = to!string(ds);    assert(!isStrictlyMonotonic(ds));  // random-access    assert(!isStrictlyMonotonic(s));   // bidirectional     dchar[] ds2 = "コーヒが好きです"d.dup;    sort(ds2);    string s2 = to!string(ds2);    assert(isStrictlyMonotonic(ds2));  // random-access    assert(isStrictlyMonotonic(s2));   // bidirectional} @nogc @safe nothrow pure unittest{    static immutable a = [1, 2, 3];    assert(a.isStrictlyMonotonic);} /**Like `isSorted`, returns `true` if the given `values` are orderedaccording to the comparison operation `less`. Unlike `isSorted`, takes valuesdirectly instead of structured in a range. `ordered` allows repeated values, e.g. `ordered(1, 1, 2)` is `true`. To verifythat the values are ordered strictly monotonically, use `strictlyOrdered`;`strictlyOrdered(1, 1, 2)` is `false`. With either function, the predicate must be a strict ordering. For example,using `"a <= b"` instead of `"a < b"` is incorrect and will cause failedassertions. Params:    values = The tested value    less = The comparison predicate Returns:    `true` if the values are ordered; `ordered` allows for duplicates,    `strictlyOrdered` does not.*/ bool ordered(alias less = "a < b", T...)(T values)if ((T.length == 2 && is(typeof(binaryFun!less(values[1], values[0])) : bool))    ||    (T.length > 2 && is(typeof(ordered!less(values[0 .. 1 + $ / 2])))        && is(typeof(ordered!less(values[$ / 2 .. $]))))    ){    foreach (i, _; T[0 .. $ - 1])    {        if (binaryFun!less(values[i + 1], values[i]))        {            assert(!binaryFun!less(values[i], values[i + 1]),                __FUNCTION__ ~ ": incorrect non-strict predicate.");            return false;        }    }    return true;} /// dittobool strictlyOrdered(alias less = "a < b", T...)(T values)if (is(typeof(ordered!less(values)))){    foreach (i, _; T[0 .. $ - 1])    {        if (!binaryFun!less(values[i], values[i + 1]))        {            return false;        }        assert(!binaryFun!less(values[i + 1], values[i]),            __FUNCTION__ ~ ": incorrect non-strict predicate.");    }    return true;} ///@safe unittest{    assert(ordered(42, 42, 43));    assert(!strictlyOrdered(43, 42, 45));    assert(ordered(42, 42, 43));    assert(!strictlyOrdered(42, 42, 43));    assert(!ordered(43, 42, 45));    // Ordered lexicographically    assert(ordered("Jane", "Jim", "Joe"));    assert(strictlyOrdered("Jane", "Jim", "Joe"));    // Incidentally also ordered by length decreasing    assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));    // ... but not strictly so: "Jim" and "Joe" have the same length    assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));} // partition/**Partitions a range in two using the given `predicate`. Specifically, reorders the range `r = [left, right$(RPAREN)` using $(REF_ALTTEXT swap, swap, std,algorithm,mutation)such that all elements `i` for which `predicate(i)` is `true` comebefore all elements `j` for which `predicate(j)` returns `false`. Performs $(BIGOH r.length) (if unstable or semistable) or $(BIGOHr.length * log(r.length)) (if stable) evaluations of `less` and $(REF_ALTTEXT swap, swap, std,algorithm,mutation).The unstable version computes the minimum possible evaluations of `swap`(roughly half of those performed by the semistable version). Params:    predicate = The predicate to partition by.    ss = The swapping strategy to employ.    r = The random-access range to partition. Returns: The right part of `r` after partitioning. If `ss == SwapStrategy.stable`, `partition` preserves the relativeordering of all elements `a`, `b` in `r` for which`predicate(a) == predicate(b)`.If `ss == SwapStrategy.semistable`, `partition` preservesthe relative ordering of all elements `a`, `b` in the left part of `r`for which `predicate(a) == predicate(b)`.*/Range partition(alias predicate, SwapStrategy ss, Range)(Range r)if (ss == SwapStrategy.stable && isRandomAccessRange!(Range) && hasLength!Range &&        hasSlicing!Range && hasSwappableElements!Range){    import std.algorithm.mutation : bringToFront;     alias pred = unaryFun!(predicate);    if (r.empty) return r;     if (r.length == 1)    {        if (pred(r.front)) r.popFront();        return r;    }    const middle = r.length / 2;    alias recurse = .partition!(pred, ss, Range);    auto lower = recurse(r[0 .. middle]);    auto upper = recurse(r[middle .. r.length]);    bringToFront(lower, r[middle .. r.length - upper.length]);    return r[r.length - lower.length - upper.length .. r.length];} ///dittoRange partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)if (ss != SwapStrategy.stable && isInputRange!Range && hasSwappableElements!Range){    import std.algorithm.mutation : swap;    alias pred = unaryFun!(predicate);     static if (ss == SwapStrategy.semistable)    {        if (r.empty) return r;         for (; !r.empty; r.popFront())        {            // skip the initial portion of "correct" elements            if (pred(r.front)) continue;            // hit the first "bad" element            auto result = r;            for (r.popFront(); !r.empty; r.popFront())            {                if (!pred(r.front)) continue;                swap(result.front, r.front);                result.popFront();            }            return result;        }         return r;    }    else    {        // Inspired from www.stepanovpapers.com/PAM3-partition_notes.pdf,        // section "Bidirectional Partition Algorithm (Hoare)"        static if (isDynamicArray!Range)        {            import std.algorithm.mutation : swapAt;            // For dynamic arrays prefer index-based manipulation            if (!r.length) return r;            size_t lo = 0, hi = r.length - 1;            for (;;)            {                for (;;)                {                    if (lo > hi) return r[lo .. r.length];                    if (!pred(r[lo])) break;                    ++lo;                }                // found the left bound                assert(lo <= hi, "lo must be <= hi");                for (;;)                {                    if (lo == hi) return r[lo .. r.length];                    if (pred(r[hi])) break;                    --hi;                }                // found the right bound, swap & make progress                r.swapAt(lo++, hi--);            }        }        else        {            import std.algorithm.mutation : swap;            auto result = r;            for (;;)            {                for (;;)                {                    if (r.empty) return result;                    if (!pred(r.front)) break;                    r.popFront();                    result.popFront();                }                // found the left bound                assert(!r.empty, "r must not be empty");                for (;;)                {                    if (pred(r.back)) break;                    r.popBack();                    if (r.empty) return result;                }

Lines 1–500 of 5117. Load more