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

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) отсортирует срезы по третьему измерению, передавая срезы 2x2 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, в соответствии с указанным порядком. Возвращает lastindex(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, в соответствии с указанным порядком. Возвращает firstindex(a) - 1, если 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, то 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 сравниваются по числовому значению.