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

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 Array{Int64,1}:
 1
 2
 3

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

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

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v
3-element Array{Tuple{Int64,String},1}:
 (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 Array{Int64,2}:
 4  3
 1  2

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

julia> sort!(A, dims = 2); A
2×2 Array{Int64,2}:
 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 Array{Int64,1}:
 1
 2
 3

julia> v
3-element Array{Int64,1}:
 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 Array{Int64,2}:
 4  3
 1  2

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

julia> sort(A, dims = 2)
2×2 Array{Int64,2}:
 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 Array{Int64,1}:
 2
 3
 1

julia> v[p]
3-element Array{Int64,1}:
 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 Array{Int64,1}:
 2
 3
 1

julia> v[p]
3-element Array{Int64,1}:
 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 Array{Int64,2}:
 -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 Array{Int64,2}:
  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 Array{Int64,2}:
  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 Array{Int64,2}:
  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 Array{Int64,2}:
  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 Array{Int64,2}:
 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

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 Array{Int64,1}:
 1
 2
 4
 3
 4

julia> partialsort!(a, 4)
4

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

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

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

julia> a
5-element Array{Int64,1}:
 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(::Array{Int64,1}, 1:3) with eltype Int64:
 2
 4
 3

julia> v[p]
3-element Array{Int64,1}:
 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(::Array{Int64,1}, 2:3) with eltype Int64:
 4
 3