Engee documentation

Sorting and related functions

Julia has an extensive and flexible API for sorting and interacting with already sorted arrays of values. By default, Julia chooses reasonable algorithms and performs the sorting in ascending order.:

julia> sort([2,3,1])
3-element Vector{Int64}:
 1
 2
 3

You can also sort the values in reverse order.:

julia> sort([2,3,1], rev=true)
3-element Vector{Int64}:
 3
 2
 1

'sort` creates a sorted copy, leaving the input data unchanged. Use the high-performance version of the sort function to modify an existing array.:

julia> a = [2,3,1];

julia> sort!(a);

julia> a
3-element Vector{Int64}:
 1
 2
 3

Instead of sorting the array directly, you can calculate a permutation of the array’s indexes, which will put it in sorted order.:

julia> v = randn(5)
5-element Array{Float64,1}:
  0.297288
  0.382396
 -0.597634
 -0.0104452
 -0.839027

julia> p = sortperm(v)
5-element Array{Int64,1}:
 5
 3
 4
 1
 2

julia> v[p]
5-element Array{Float64,1}:
 -0.839027
 -0.597634
 -0.0104452
  0.297288
  0.382396

Arrays can be sorted according to an arbitrary transformation of their values.:

julia> sort(v, by=abs)
5-element Array{Float64,1}:
 -0.0104452
  0.297288
  0.382396
 -0.597634
 -0.839027

Or in the reverse order by converting:

julia> sort(v, by=abs, rev=true)
5-element Array{Float64,1}:
 -0.839027
 -0.597634
  0.382396
  0.297288
 -0.0104452

If necessary, you can select a sorting algorithm.:

julia> sort(v, alg=InsertionSort)
5-element Array{Float64,1}:
 -0.839027
 -0.597634
 -0.0104452
  0.297288
  0.382396

All functions related to sorting and ordering are based on the "less than" ratio, which defines https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings [strict weak order] of processed values. The isless function is called by default, but the relationship can be specified using the keyword lt. This is a function that takes two array elements and returns true if and only if the first argument is 'less than' the second. For more information, see the description sort! and in the section Alternative arrangements.

Sorting functions

sort!(A; dims::Integer, alg::Algorithm=defalg(A), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sorts the multidimensional array A in the dimension dims'. For a description of possible named arguments, see the section on the one-dimensional version. `sort!.

For information about sorting array slices, see the description sortslices.

Compatibility: Julia 1.1

This feature requires a Julia version of at least 1.1.

Examples

julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
 4  3
 1  2

julia> sort!(A, dims = 1); A
2×2 Matrix{Int64}:
 1  2
 4  3

julia> sort!(A, dims = 2); A
2×2 Matrix{Int64}:
 1  2
 3  4
sort!(A; dims::Integer, alg::Algorithm=defalg(A), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sort the multidimensional array A along dimension dims. See the one-dimensional version of sort! for a description of possible keyword arguments.

To sort slices of an array, refer to sortslices.

Compatibility: Julia 1.1

This function requires at least Julia 1.1.

Examples

julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
 4  3
 1  2

julia> sort!(A, dims = 1); A
2×2 Matrix{Int64}:
 1  2
 4  3

julia> sort!(A, dims = 2); A
2×2 Matrix{Int64}:
 1  2
 3  4
sort(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Option sort!, which returns a sorted copy of v, leaving v unchanged.

Examples

julia> v = [3, 1, 2];

julia> sort(v)
3-element Vector{Int64}:
 1
 2
 3

julia> v
3-element Vector{Int64}:
 3
 1
 2
sort(A; dims::Integer, alg::Algorithm=defalg(A), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sorts a multidimensional array A in a given dimension. For a description of possible named arguments, see the description sort!.

For information about sorting array slices, see the description sortslices.

Examples

julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
 4  3
 1  2

julia> sort(A, dims = 1)
2×2 Matrix{Int64}:
 1  2
 4  3

julia> sort(A, dims = 2)
2×2 Matrix{Int64}:
 3  4
 1  2
sortperm(A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

Returns a permutation vector or array I in which the elements A[I] are placed in sorted order in the specified dimension. If A has multiple dimensions, the named argument dims' must be specified. The order is set using the same named arguments as for `sort!. The permutation is guaranteed to be stable, even if the sorting algorithm is unstable: the indexes of equal elements will be arranged in ascending order.

See also the description sortperm!, partialsortperm, invperm and indexin. For information about sorting array slices, see the description sortslices.

Compatibility: Julia 1.9

A method that accepts dims requires a Julia version of at least 1.9.

Examples

julia> v = [3, 1, 2];

julia> p = sortperm(v)
3-element Vector{Int64}:
 2
 3
 1

julia> v[p]
3-element Vector{Int64}:
 1
 2
 3

julia> A = [8 7; 5 6]
2×2 Matrix{Int64}:
 8  7
 5  6

julia> sortperm(A, dims = 1)
2×2 Matrix{Int64}:
 2  4
 1  3

julia> sortperm(A, dims = 2)
2×2 Matrix{Int64}:
 3  1
 2  4
InsertionSort

Uses an insertion sorting algorithm.

Insertion sort goes through one element of the collection at a time, inserting each element into the correct sorted position in the output vector.

Specifications:

  • Stability: The order of elements that are considered equal is preserved (for example, "a" and "A" when case-insensitive letters are sorted).

  • Execution in a place in memory.

  • Square production_ in the number of items to be sorted: well suited for small collections, but should not be used for large ones.

MergeSort

Specifies that the sorting function should use the merge sorting algorithm. Merge sort divides a collection into subcollections and repeatedly merges them, sorting each subcollection at each stage until the entire collection is recomposed into a sorted view.

Specifications:

  • Stability: The order of elements that are considered equal is preserved (for example, "a" and "A" when case-insensitive letters are sorted).

  • The execution is out of place in memory.

  • Sorting strategy "divide and conquer".

  • Good performance_ for large collections, but usually not as fast as QuickSort.

QuickSort

Specifies that the sorting function should use a quicksort algorithm that is not stable.

Specifications:

  • Non-stability: The order of elements that are considered equal is not preserved (for example, "a" and "A" when case-insensitive letters are sorted).

  • Execution in a place in memory.

  • Divide and conquer: A sorting strategy similar to MergeSort.

  • Good performance for large collections.

PartialQuickSort{T <: Union{Integer,OrdinalRange}}

Specifies that the sorting function should use a partial quicksort algorithm. PartialQuickSort(k) resembles QuickSort, but it requires searching and sorting only the elements that, if fully sorted by v, would fall into v[k].

Specifications:

  • Non-stability: The order of elements that are considered equal is not preserved (for example, "a" and "A" when case-insensitive letters are sorted).

  • Execution in a place in memory.

  • Divide and conquer: A sorting strategy similar to MergeSort.

Note that PartialQuickSort(k) does not necessarily sort the entire array. Examples:

julia> x = rand(100);

julia> k = 50:100;

julia> s1 = sort(x; alg=QuickSort);

julia> s2 = sort(x; alg=PartialQuickSort(k));

julia> map(issorted, (s1, s2))
(true, false)

julia> map(x->issorted(x[k]), (s1, s2))
(true, true)

julia> s1[k] == s2[k]
true
sortperm!(ix, A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

Similarly sortperm, but accepts a pre-allocated vector or array of indexes ix with the same axes as A. ix is initialized with the values LinearIndices(A).

If any modified argument is placed in the same memory area as any other argument, the behavior may be unexpected.
Compatibility: Julia 1.9

A method that accepts dims requires a Julia version of at least 1.9.

Examples

julia> v = [3, 1, 2]; p = zeros(Int, 3);

julia> sortperm!(p, v); p
3-element Vector{Int64}:
 2
 3
 1

julia> v[p]
3-element Vector{Int64}:
 1
 2
 3

julia> A = [8 7; 5 6]; p = zeros(Int,2, 2);

julia> sortperm!(p, A; dims=1); p
2×2 Matrix{Int64}:
 2  4
 1  3

julia> sortperm!(p, A; dims=2); p
2×2 Matrix{Int64}:
 3  1
 2  4
sortslices(A; dims, alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sorts the slices of array `A'. The mandatory named argument `dims' must be an integer or a tuple of integers. It sets the dimensions in which the slices are sorted.

For example, if A is a matrix, dims=1 will sort rows, dims=2 will sort columns. Note that the default comparison function in one-dimensional slices performs lexicographic sorting.

For information about the other named arguments, see the documentation on sort!.

Examples

julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1) # Сортировка строк
3×3 Matrix{Int64}:
 -1   6  4
  7   3  5
  9  -2  8

julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1, lt=(x,y)->isless(x[2],y[2]))
3×3 Matrix{Int64}:
  9  -2  8
  7   3  5
 -1   6  4

julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1, rev=true)
3×3 Matrix{Int64}:
  9  -2  8
  7   3  5
 -1   6  4

julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2) # Сортировка столбцов
3×3 Matrix{Int64}:
  3   5  7
 -1  -4  6
 -2   8  9

julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2, alg=InsertionSort, lt=(x,y)->isless(x[2],y[2]))
3×3 Matrix{Int64}:
  5   3  7
 -4  -1  6
  8  -2  9

julia> sortslices([7 3 5; 6 -1 -4; 9 -2 8], dims=2, rev=true)
3×3 Matrix{Int64}:
 7   5   3
 6  -4  -1
 9   8  -2

Higher dimensions

'sortslices` naturally extends to higher dimensions. For example, if A is a 2x2x2 array, sortslices(A, dims=3)`will sort the slices in the third dimension by passing the 2x2 slices `A[:, :, 1] and A[:,:, 2] to the comparison function. Note that although there is no default order for slices of higher dimensions, it can be specified using the named argument by or `lt'.

If dims is a tuple, the order of measurements in dims is relative and indicates the linear order of the slices. For example, if A is three-dimensional and dims has the value (1, 2), the orders of the first two dimensions are changed so that the slices (of the remaining third dimension) are sorted. If dims has the value (2, 1), the same slices are used, but the resulting order will be row-by-row.

Examples of higher dimensions

julia> A = [4 3; 2 1 ;;; 'A' 'B'; 'C' 'D']
2×2×2 Array{Any, 3}:
[:, :, 1] =
 4  3
 2  1

[:, :, 2] =
 'A'  'B'
 'C'  'D'

julia> sortslices(A, dims=(1,2))
2×2×2 Array{Any, 3}:
[:, :, 1] =
 1  3
 2  4

[:, :, 2] =
 'D'  'B'
 'C'  'A'

julia> sortslices(A, dims=(2,1))
2×2×2 Array{Any, 3}:
[:, :, 1] =
 1  2
 3  4

[:, :, 2] =
 'D'  'C'
 'B'  'A'

julia> sortslices(reshape([5; 4; 3; 2; 1], (1,1,5)), dims=3, by=x->x[1,1])
1×1×5 Array{Int64, 3}:
[:, :, 1] =
 1

[:, :, 2] =
 2

[:, :, 3] =
 3

[:, :, 4] =
 4

[:, :, 5] =
 5

issorted(v, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Checks whether the collection is in sorted order. Named arguments change the sorting order, as described in the documentation on sort!.

Examples

julia> issorted([1, 2, 3])
true

julia> issorted([(1, "b"), (2, "a")], by = x -> x[1])
true

julia> issorted([(1, "b"), (2, "a")], by = x -> x[2])
false

julia> issorted([(1, "b"), (2, "a")], by = x -> x[2], rev=true)
true

julia> issorted([1, 2, -2, 3], by=abs)
true
searchsorted(v, x; by=identity, lt=isless, rev=false)

Returns the range of indexes in v where the values are equivalent to x, or an empty range located at the insertion point if v does not contain values equivalent to x. The vector v must be sorted in the order determined by the named arguments. For the meaning of named arguments and the definition of equivalence, see the description sort!. Note that the by function is applied to the desired value of x, as well as to the values in `v'.

The range is usually found by binary search, but optimized implementations exist for some input data.

See also the description searchsortedfirst, sort!, insorted, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # одно совпадение
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # несколько совпадений
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # нет совпадений, вставить в середину
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # нет совпадений, вставить в конец
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # нет совпадений, вставить в начало
1:0

julia> searchsorted([1=>"one", 2=>"two", 2=>"two", 4=>"four"], 2=>"two", by=first) # сравнить ключи пар
2:3
searchsortedfirst(v, x; by=identity, lt=isless, rev=false)

Returns the index of the first value in v that is not ordered before x'. If all values in `v are ordered before x, returns `lastindex(v) +1'.

The vector v must be sorted in the order determined by the named arguments. When inserting (insert!) x by the returned index, the sorted order is preserved. For the meaning and ways to use named arguments, see the description sort!. Note that the by' function is applied to the desired value of `x, as well as to the values in `v'.

The index is usually found by binary search, but optimized implementations exist for some input data.

See also the description searchsortedlast, searchsorted, findfirst.

Examples

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4) # одно совпадение
3

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5) # несколько совпадений
4

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3) # нет совпадений, вставить в середину
3

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 9) # no matches, insert at the end
7

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0) # no matches, insert at the beginning
1

julia> searchsortedfirst([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare keys of pairs
3
searchsortedlast(v, x; by=identity, lt=isless, rev=false)

Returns the index of the last value in v, which is not ordered after x'. If all values in `v are ordered after x, returns `firstindex(v) - 1'.

The vector v must be sorted in the order determined by the named arguments. When inserting (insert!) x immediately after the returned index, the sorted order is preserved. For the meaning and ways to use named arguments, see the description sort!. Note that the by function is applied to the desired value of x, as well as to the values in `v'.

The index is usually found by binary search, but optimized implementations exist for some input data.

Examples

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # одно совпадение
3

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # несколько совпадений
5

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # нет совпадений, вставить в середину
2

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # нет совпадений, вставить в конец
6

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # нет совпадений, вставить в начало
0

julia> searchsortedlast([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # сравнить ключи пар
2
insorted(x, v; by=identity, lt=isless, rev=false) -> Bool

Determines whether the vector v contains any value equivalent to x'. The vector `v must be sorted in the order determined by the named arguments. For the meaning of named arguments and the definition of equivalence, see the description sort!. Note that the by function is applied to the desired value of x, as well as to the values in `v'.

Verification is usually performed by binary search, but optimized implementations exist for some input data.

See also the description in.

Examples

julia> insorted(4, [1, 2, 4, 5, 5, 7]) # одно совпадение
true

julia> insorted(5, [1, 2, 4, 5, 5, 7]) # несколько совпадений
true

julia> insorted(3, [1, 2, 4, 5, 5, 7]) # нет совпадений
false

julia> insorted(9, [1, 2, 4, 5, 5, 7]) # нет совпадений
false

julia> insorted(0, [1, 2, 4, 5, 5, 7]) # нет совпадений
false

julia> insorted(2=>"TWO", [1=>"one", 2=>"two", 4=>"four"], by=first) # сравнить ключи пар
true
Compatibility: Julia 1.6

insured was added in Julia 1.6.

 
partialsort!(v, k; by=identity, lt=isless, rev=false)

Partially sorts the vector v in place so that the value with index k (or a range of adjacent values, if k is a range) is in the position it would be in if the array were fully sorted. If k is a single index, this value is returned. If k is a range, an array of values in these indexes is returned. Note that partialsort! does not perform a complete sorting of the input array.

For information about named arguments, see the documentation on sort!.

Examples

julia> a = [1, 2, 4, 3, 4]
5-element Vector{Int64}:
 1
 2
 4
 3
 4

julia> partialsort!(a, 4)
4

julia> a
5-element Vector{Int64}:
 1
 2
 3
 4
 4

julia> a = [1, 2, 4, 3, 4]
5-element Vector{Int64}:
 1
 2
 4
 3
 4

julia> partialsort!(a, 4, rev=true)
2

julia> a
5-element Vector{Int64}:
 4
 4
 3
 2
 1
partialsort(v, k, by=identity, lt=isless, rev=false)

Option partialsort!, which copies v before it is partially sorted, thereby returning the same result as partialsort!, but leaving v unchanged.

partialsortperm(v, k; by=identity, lt=isless, rev=false)

Returns a partial permutation I of the vector v, so that v[I] returns the values of the fully sorted version of v at index k. If k is a range, the index vector is returned. If 'k` is an integer, one index is returned. The order is set using the same named arguments as for sort!. The permutation is stable: the indexes of equal elements will be arranged in ascending order.

This function is equivalent to calling sortperm(...)[k], but is more efficient.

Examples

julia> v = [3, 1, 2, 1];

julia> v[partialsortperm(v, 1)]
1

julia> p = partialsortperm(v, 1:3)
3-element view(::Vector{Int64}, 1:3) with eltype Int64:
 2
 4
 3

julia> v[p]
3-element Vector{Int64}:
 1
 1
 2
partialsortperm!(ix, v, k; by=identity, lt=isless, rev=false)

Similarly partialsortperm', but accepts a pre-allocated index vector `ix of the same size as that of v, which is used to store (permute) the indexes of `v'.

ix is initialized with the indexes v.

(Usually the indexes of v will be in the range 1:length(v)', although if `v has a different type of array with indexes that do not start with one, such as OffsetArray, the same indexes should be used in ix.)

After returning, ix is guaranteed to have k indexes in sorted positions, as shown below.

partialsortperm!(ix, v, k);
v[ix[k]] == partialsort(v, k)

The returned value is the 'k` th element of the index vector ix if k is an integer, or the representation of ix if k is a range.

If any modified argument is placed in the same memory area as any other argument, the behavior may be unexpected.

Examples

julia> v = [3, 1, 2, 1];

julia> ix = Vector{Int}(undef, 4);

julia> partialsortperm!(ix, v, 1)
2

julia> ix = [1:4;];

julia> partialsortperm!(ix, v, 2:3)
2-element view(::Vector{Int64}, 2:3) with eltype Int64:
 4
 3

Sorting algorithms

Currently, four sorting algorithms are publicly available in the basic version of Julia:

By default, the sort family of functions uses stable sorting algorithms that work quickly with most input data. The exact choice of algorithm is an implementation feature that allows for improved performance in the future. Currently, depending on the type, size, and composition of the input data, a hybrid of RadixSort, ScratchQuickSort, InsertionSort, and CountingSort is used. Implementation details may vary, but they are now available in the extended help for ??Base.DEFAULT_STABLE and the docstrings of the internal sorting algorithms specified there.

You can explicitly specify your preferred algorithm using the keyword alg (for example, sort!(v, alg=PartialQuickSort(10:20))) or reconfigure the default sorting algorithm for custom types by adding a specialized method to the Base.Sort.defalg function. For example, InlineStrings.jl defines the following method:

Base.Sort.defalg(::AbstractArray{<:Union{SmallInlineStrings, Missing}}) = InlineStringSort
Compatibility: Julia 1.9

The default sorting algorithm (returned by Base.Sort.defalg) is guaranteed to be stable starting with Julia 1.9. Previous versions had unstable edge cases when sorting numeric arrays.

Alternative arrangements

By default, sort, searchsorted and related functions use isless to compare two elements to determine which one should be the first. The abstract type Base.Order.Ordering provides a mechanism for defining alternative orderings for the same set of elements: When calling a sorting function, for example, sort!, an instance of Ordering can be specified with the named argument order.

The Ordering instances define the order using the function Base.Order.lt `, which works as a generalization of `isless'. The action of this function with custom orderings (`Ordering') must satisfy all the conditions https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings [strict weak order]. See the description `sort! with information and examples of valid and invalid lt functions.

Base.Order.Ordering

An abstract type representing a strict weak order in a certain set of elements. For more information, see the description sort!.

To compare two elements according to the ordering, use Base.Order.lt.

lt(o::Ordering, a, b) -> Bool

Checks whether a is smaller than b, according to the ordering of `o'.

ord(lt, by, rev::Union{Bool, Nothing}, order::Ordering=Forward)

Creates an object Ordering based on the same arguments that the function uses sort!. First, the elements are transformed using the by function (this can be identity), and then compared according to the lt function or the existing order' ordering. The `lt should be isless or be a function that follows the same rules as the lt parameter of the function sort!. Finally, the final order is reversed if `rev=true'.

Transfer of an lt other than isless together with an order other than Base.Order.Forward or Base.Order.Reverse, prohibited. Otherwise, all parameters are independent and can be used together in all possible combinations.

Base.Order.Forward

The default order is according to isless.

ReverseOrdering(fwd::Ordering=Forward)

A shell that reverses the order.

For a given Ordering of o, the following is true for all a, b:

lt(ReverseOrdering(o), a, b) == lt(o, b, a)
Base.Order.Reverse

Reverses the order according to isless.

By(by, order::Ordering=Forward)

Ordering, which applies order to the elements after their transformation by the by function.

Lt(lt)

Ordering, which calls lt(a, b) to compare items. The lt must follow the same rules as the lt parameter of the function. sort!.

Perm(order::Ordering, data::AbstractVector)

Ordering for indexes of data where i is less than j if data[i] is less than data[j] according to order'. If `data[i] and data[j] are equal, i and j are compared by numeric value.