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

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 имеет альтернативный тип массива с индексами не с 1, например, 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