Сортировка и связанные функции

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

Отсортируйте вектор v на месте. QuickSort используется по умолчанию для числовых массивов, а MergeSort — для других массивов. Вы можете указать используемый алгоритм с помощью ключевого слова alg (см. Алгоритмы сортировки для доступных алгоритмов). Ключевое слово by позволяет указать функцию, которая будет применена к каждому элементу перед сравнением; ключевое слово lt позволяет указать пользовательскую функцию «меньше» (обратите внимание, что для каждой x и y, только одна из lt(x,y) и lt(y,x) может вернуть true); используйте rev=true для изменения порядка сортировки на обратный. Эти параметры независимы и могут быть использованы вместе во всех возможных комбинациях: если заданы и by, и lt, функция lt применяется к результату функции by; rev=true инвертирует порядок, заданный ключевыми словами by и lt.

Примеры

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

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

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v
3-element Vector{Tuple{Int64, String}}:
 (1, "c")
 (2, "b")
 (3, "a")

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v
3-element Vector{Tuple{Int64, String}}:
 (3, "a")
 (2, "b")
 (1, "c")

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

Отсортируйте многомерный массив A по размерности dims. См. sort! для описания возможных ключевых аргументов.

Для сортировки срезов массива обратитесь к sortslices.

Примеры

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)

Вариант sort!, который возвращает отсортированную копию v, оставив v неизменным.

Примеры

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=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Отсортируйте многомерный массив A по заданной размерности. См. sort! для описания возможных ключевых аргументов.

Для сортировки срезов массива обратитесь к sortslices.

Примеры

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(v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Возвращает вектор перестановки I, который упорядочивает v[I] по возрастанию. Порядок задаётся теми же ключевыми словами, что и в sort!. Перестановка гарантированно устойчива, даже если алгоритм сортировки неустойчив, что означает, что индексы равных элементов появляются в порядке возрастания.

См. также sortperm!, partialsortperm, invperm, indexin.

Примеры

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

InsertionSort

Указывает, что функция сортировки должна использовать алгоритм сортировки вставкой. Сортировка вставкой проходит по коллекции по одному элементу за раз, вставляя каждый элемент в его правильное, отсортированное положение в выходном списке.

Характеристики:

• устойчивая: сохраняет порядок элементов, которые сравниваются как равные (например, «a» и «A» при сортировке букв, игнорирующей регистр).
• на месте в памяти.
• квадратичная производительность по количеству элементов для сортировки: подходит для небольших коллекций, но не следует использовать для больших.

MergeSort

Указывает, что функция сортировки должна использовать алгоритм сортировки слиянием. Сортировка слиянием делит коллекцию на подколлекции и многократно сливает их, сортируя каждую подколлекцию на каждом шаге, пока вся коллекция не будет перекомбинирована в отсортированном виде.

Характеристики:

• устойчивая: сохраняет порядок элементов, которые сравниваются как равные (например, «a» и «A» при сортировке букв, игнорирующей регистр).
• не на месте в памяти.
• разделяй и властвуй стратегия сортировки.

QuickSort

Указывает, что функция сортировки должна использовать алгоритм быстрой сортировки, который не устойчив.

Характеристики:

• не устойчивая: не сохраняет порядок элементов, которые сравниваются как равные (например, «a» и «A» при сортировке букв, игнорирующей регистр).
• на месте в памяти.
• разделяй и властвуй: стратегия сортировки, аналогичная MergeSort.
• хорошая производительность для больших коллекций.

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

Указывает, что функция сортировки должна использовать алгоритм частичной быстрой сортировки. Частичная быстрая сортировка возвращает наименьшие k элементов, отсортированных от наименьшего к наибольшему, находя их и сортируя их с помощью QuickSort.

Характеристики:

• не устойчивая: не сохраняет порядок элементов, которые сравниваются как равные (например, «a» и «A» при сортировке букв, игнорирующей регистр).
• на месте в памяти.
• разделяй и властвуй: стратегия сортировки, аналогичная MergeSort.

sortperm!(ix, v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, initialized::Bool=false)

Как sortperm, но принимает предварительно выделенный вектор индексов ix. Если initialized равно false (по умолчанию), ix инициализируется содержащими значения 1:length(v).

Примеры

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

sortslices(A; dims, alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Сортировка срезов массива A. Требуемый ключевой аргумент dims должен быть либо целым числом, либо кортежем целых чисел. Он определяет размерность(и), по которым сортируются срезы.

Например, если A является матрицей, dims=1 будет сортировать строки, dims=2 будет сортировать столбцы. Обратите внимание, что по умолчанию функция сравнения для одномерных срезов сортирует лексикографически.

Для остальных ключевых аргументов см. документацию sort!.

Примеры

julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1) # Sort rows
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) # Sort columns
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

Многомерные массивы

sortslices естественным образом обобщается на многомерные массивы. Например, если A является трёхмерным массивом 2x2x2, sortslices(A, dims=3) будет сортировать срезы внутри третьей размерности, передавая двумерные срезы A[:, :, 1] и A[:, :, 2] функции сравнения. Обратите внимание, что, хотя для многомерных срезов нет порядка по умолчанию, вы можете использовать ключевые аргументы by или lt для указания такого порядка.

Если dims является кортежем, порядок размерностей в dims важен и определяет линейный порядок срезов. Например, если A трёхмерный, а dims равен (1, 2), то порядок первых двух измерений переставляется таким образом, чтобы срезы (оставшейся третьей размерности) были отсортированы. Если dims равен (2, 1) вместо этого, те же срезы будут взяты, но порядок результата будет строчно-главным.

Примеры с многомерными массивами

julia> A = permutedims(reshape([4 3; 2 1; 'A' 'B'; 'C' 'D'], (2, 2, 2)), (1, 3, 2))
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)

Проверка, отсортирован ли вектор. Ключевые слова lt, by и rev изменяют понятие сортировки так же, как и для sort.

Примеры

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

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Возвращает диапазон индексов a, которые равны x (используя двоичный поиск) в соответствии с порядком, заданным ключевыми словами by, lt и rev, предполагая, что a уже отсортирован в этом порядке. Возвращает пустой диапазон в точке вставки, если a не содержит значений, равных x.

См. также: insorted, searchsortedfirst, sort, findall.

Примеры

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

searchsortedfirst(a, x; by=<transform>, lt=<comparison>, rev=false)

Возвращает индекс первого значения в a больше или равно x, согласно указанному порядку. Возвращает length(a) + 1 если x больше всех значений в a. Предполагается, что a отсортирован.

См. также: searchsortedlast, searchsorted, findfirst.

Примеры

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4) # single match
3

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5) # multiple matches
4

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3

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

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1

searchsortedlast(a, x; by=<transform>, lt=<comparison>, rev=false)

Возвращает индекс последнего значения в a меньше или равно x, согласно указанному порядку. Возвращает 0 если x меньше всех значений в a. Предполагается, что a отсортирован.

Примеры

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # single match
3

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # multiple matches
5

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
2

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
6

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
0

insorted(a, x; by=<transform>, lt=<comparison>, rev=false) -> Bool

Определяет, содержится ли элемент в заданном отсортированном наборе, в том смысле, что он == одному из значений набора в соответствии с порядком, заданным ключевыми словами by, lt и rev, предполагая, что a уже отсортирован в этом порядке, см. sort для ключевых слов.

См. также in.

Примеры

julia> insorted(4, [1, 2, 4, 5, 5, 7]) # single match
true

julia> insorted(5, [1, 2, 4, 5, 5, 7]) # multiple matches
true

julia> insorted(3, [1, 2, 4, 5, 5, 7]) # no match
false

julia> insorted(9, [1, 2, 4, 5, 5, 7]) # no match
false

julia> insorted(0, [1, 2, 4, 5, 5, 7]) # no match
false

partialsort!(v, k; by=<transform>, lt=<comparison>, rev=false)

Частичная сортировка вектора v на месте, в соответствии с порядком, заданным by, lt и rev, так что значение в индексе k (или диапазоне смежных значений, если k является диапазоном) находится в позиции, где оно появилось бы, если бы массив был полностью отсортирован с помощью нестабильного алгоритма. Если k является одиночным индексом, это значение возвращается; если k является диапазоном, возвращается массив значений в этих индексах. Обратите внимание, что partialsort! не полностью сортирует входной массив.

Примеры

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=<transform>, lt=<comparison>, rev=false)

Вариант partialsort!, который копирует v перед частичной сортировкой, тем самым возвращая то же самое, что и partialsort!, но оставляя v неизменным.

partialsortperm(v, k; by=<transform>, lt=<comparison>, rev=false)

Возвращает частичную перестановку I вектора v, так что v[I] возвращает значения полностью отсортированной версии v в индексе k. Если k является диапазоном, возвращается вектор индексов; если k целое число, возвращается одиночный индекс. Порядок задаётся теми же ключевыми словами, что и для sort!. Перестановка устойчива, т.е. индексы равных элементов появляются в порядке возрастания.

Обратите внимание, что эта функция эквивалентна, но эффективнее, чем вызов sortperm(...)[k].

Примеры

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=<transform>, lt=<comparison>, rev=false, initialized=false)

Подобно partialsortperm, но принимает предварительно выделенный вектор индексов ix того же размера, что и v, который используется для хранения (перестановки) индексов v.

Если вектор индексов ix инициализирован индексами v (или их перестановкой), initialized должен быть установлен на true.

Если initialized равен false (по умолчанию), то ix инициализируется, содержащий индексы v.

Если initialized равен true, но ix не содержит (перестановку) индексов v, поведение partialsortperm! не определено.

(Обычно, индексы v будут 1:length(v), хотя если v имеет альтернативный тип массива с индексами, не начинающимися с единицы, например, OffsetArray, ix, то ix также должен быть массивом OffsetArray с теми же индексами, и должен содержать в качестве значений (перестановку) этих индексов.)

По возвращении гарантируется, что ix имеет индексы k в своих отсортированных позициях, так что

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

Возвращаемое значение — k-й элемент ix, если k является целым числом, или представление в ix, если k является диапазоном.

Примеры

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, initialized=true)
2-element view(::Vector{Int64}, 2:3) with eltype Int64:
 4
 3

Base.Order.Ordering

Абстрактный тип, представляющий тотальный порядок на некотором наборе элементов.

Используйте Base.Order.lt для сравнения двух элементов в соответствии с порядком.

lt(o::Ordering, a, b)

Проверить, меньше ли a b в соответствии с порядком o.

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

Создать объект Ordering из тех же аргументов, что и sort!. Элементы сначала преобразуются функцией by (которая может быть identity), а затем сравниваются по функции lt или по существующему порядку order. lt должна быть isless или функцией, которая подчиняется аналогичным правилам. Наконец, результирующий порядок инвертируется, если rev=true.

Передача lt отличного от isless вместе с order отличным от Base.Order.Forward или Base.Order.Reverse запрещена, в противном случае все опции независимы и могут быть использованы вместе во всех возможных комбинациях.

Base.Order.Forward

Порядок по умолчанию согласно isless.

ReverseOrdering(fwd::Ordering=Forward)

Обёртка, которая инвертирует порядок.

Для данного Ordering o, следующее выполняется для всех a, b:

lt(ReverseOrdering(o), a, b) == lt(o, b, a)

Base.Order.Reverse

Обратный порядок согласно isless.

By(by, order::Ordering=Forward)

Ordering который применяет order к элементам после их преобразования функцией by.

Lt(lt)

Ordering который вызывает lt(a, b) для сравнения элементов. lt должен подчиняться тем же правилам, что и реализации isless.

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

Ordering на индексах data, где i меньше j если data[i] меньше data[j] согласно order. В случае, когда data[i] и data[j] равны, i и j сравниваются по числовому значению.