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

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

Отсортировать вектор v на месте. По умолчанию для числовых массивов используется QuickSort, а для других массивов — MergeSort. Вы можете указать используемый алгоритм с помощью ключевого слова alg (см. Алгоритмы сортировки для доступных алгоритмов). Ключевое слово by позволяет предоставить функцию, которая будет применена к каждому элементу перед сравнением; ключевое слово lt позволяет предоставить пользовательскую функцию «меньше»; используйте 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!.

Примеры

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.

Примеры

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 отсортирован.

Примеры

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)

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

Примеры

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 сравниваются по числовому значению.