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

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

Сортирует вектор v на месте. По умолчанию используется стабильный алгоритм: порядок элементов, которые сравниваются как равные, сохраняется. Конкретный алгоритм может быть выбран с помощью ключевого слова alg (см. Алгоритмы сортировки для доступных алгоритмов).

Элементы сначала преобразуются с помощью функции by, а затем сравниваются в соответствии с функцией lt или упорядочением order. Наконец, полученный порядок меняется на обратный, если rev=true (это сохраняет прямую стабильность: элементы, которые сравниваются как равные, не меняют порядок). Текущая реализация применяет преобразование by перед каждым сравнением, а не один раз на элемент.

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

Взаимоотношения между двумя элементами определяются следующим образом (с заменой «меньше» и «больше», когда rev=true):

• x меньше y, если lt(by(x), by(y)) (или Base.Order.lt(order, by(x), by(y))) возвращает true.
• x больше y, если y меньше x.
• x и y эквивалентны, если ни один из них не меньше другого («несравнимые» иногда используется как синоним к «эквивалентным»).

Результат sort! отсортирован в том смысле, что каждый элемент больше или равен предыдущему.

Функция lt должна определять строгое слабое упорядочение, то есть она должна быть

• иррефлексивной: lt(x, x) всегда возвращает false,
• асимметричной: если lt(x, y) возвращает true, то lt(y, x) возвращает false,
• транзитивной: lt(x, y) && lt(y, z) подразумевает lt(x, z),
• транзитивной в эквивалентности: !lt(x, y) && !lt(y, x) и !lt(y, z) && !lt(z, y) вместе подразумевают !lt(x, z) && !lt(z, x). Другими словами: если x и y эквивалентны, и y и z эквивалентны, то x и z должны быть эквивалентны.

Например, < является допустимой функцией lt для значений Int, но ≤ нет: она нарушает иррефлексивность. Для значений Float64 даже < является недопустимым, так как нарушает четвёртое условие: 1.0 и NaN эквивалентны, а также NaN и 2.0, но 1.0 и 2.0 не эквивалентны.

См. также sort, sortperm, sortslices, partialsort!, partialsortperm, issorted, searchsorted, insorted, Base.Order.ord.

Примеры

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")

julia> sort(0:3, by=x->x-2, order=Base.Order.By(abs)) # same as sort(0:3, by=abs(x->x-2))
4-element Vector{Int64}:
 2
 1
 3
 0

julia> sort([2, NaN, 1, NaN, 3]) # correct sort with default lt=isless
5-element Vector{Float64}:
   1.0
   2.0
   3.0
 NaN
 NaN

julia> sort([2, NaN, 1, NaN, 3], lt=<) # wrong sort due to invalid lt. This behavior is undefined.
5-element Vector{Float64}:
   2.0
 NaN
   1.0
 NaN
   3.0

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=defalg(A), 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(A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

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

См. также sortperm!, partialsortperm, invperm, indexin. Для сортировки срезов массива обратитесь к sortslices.

Примеры

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

julia> A = [8 7; 5 6]
2×2 Matrix{Int64}:
 8  7
 5  6

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

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

InsertionSort

Используйте алгоритм сортировки вставками.

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

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

• стабильная: сохраняет порядок элементов, которые сравниваются как равные

(например, "a" и "A" в сортировке букв, игнорирующей регистр).

• выполняется на месте в памяти.
• квадратичная производительность по количеству элементов, подлежащих сортировке:

Хорошо подходит для небольших коллекций, но не следует использовать для больших.

MergeSort

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

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

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

QuickSort

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

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

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

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

Указывает, что функция сортировки должна использовать частичный алгоритм быстрой сортировки. PartialQuickSort(k) похож на QuickSort, но только требуется найти и отсортировать элементы, которые попали бы в v[k] при полной сортировке v.

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

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

Обратите внимание, что PartialQuickSort(k) не обязательно сортирует весь массив. Например,

julia> x = rand(100);

julia> k = 50:100;

julia> s1 = sort(x; alg=QuickSort);

julia> s2 = sort(x; alg=PartialQuickSort(k));

julia> map(issorted, (s1, s2))
(true, false)

julia> map(x->issorted(x[k]), (s1, s2))
(true, true)

julia> s1[k] == s2[k]
true

sortperm!(ix, A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

Аналогично sortperm, но принимает предварительно выделенный вектор или массив индексов ix с теми же axes что и A. ix инициализируется, содержащим значения LinearIndices(A).

Примеры

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

julia> A = [8 7; 5 6]; p = zeros(Int,2, 2);

julia> sortperm!(p, A; dims=1); p
2×2 Matrix{Int64}:
 2  4
 1  3

julia> sortperm!(p, A; dims=2); p
2×2 Matrix{Int64}:
 3  1
 2  4

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) отсортирует срезы по 3-й размерности, передавая 2x2 срезы A[:, :, 1] и A[:, :, 2] функции сравнения. Обратите внимание, что по умолчанию нет порядка для многомерных срезов, но вы можете использовать ключевые аргументы by или lt для указания такого порядка.

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

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

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)

Проверяет, отсортирована ли коллекция. Ключевые слова изменяют порядок, который считается отсортированным, как описано в документации 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

julia> issorted([1, 2, -2, 3], by=abs)
true

searchsorted(v, x; by=identity, lt=isless, rev=false)

Возвращает диапазон индексов в v, где значения эквивалентны x, или пустой диапазон в точке вставки, если v не содержит значений, эквивалентных x . Вектор v должен быть отсортирован в соответствии с порядком, заданным ключевыми словами. См. sort! для значения ключевых слов и определения эквивалентности. Обратите внимание, что функция by применяется к искомому значению x и значениям в v.

Диапазон обычно находится с помощью бинарного поиска, но существуют оптимизированные реализации для некоторых входных данных.

См. также: searchsortedfirst, sort!, insorted, 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

julia> searchsorted([1=>"one", 2=>"two", 2=>"two", 4=>"four"], 2=>"two", by=first) # compare the keys of the pairs
2:3

searchsortedfirst(v, x; by=identity, lt=isless, rev=false)

Возвращает индекс первого значения в v , больше или равного x. Если x больше всех значений в v, возвращает lastindex(v) + 1.

Вектор v должен быть отсортирован в соответствии с порядком, заданным ключевыми словами. Вставка insert! по возвращённому индексу сохранит отсортированный порядок. См. sort! для значения ключевых слов и определения «больше чем» и эквивалентности. Обратите внимание, что функция by применяется к искомому значению x и значениям в v.

Индекс обычно находится с помощью бинарного поиска, но существуют оптимизированные реализации для некоторых входных данных.

См. также: 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

julia> searchsortedfirst([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare the keys of the pairs
3

searchsortedlast(v, x; by=identity, lt=isless, rev=false)

Возвращает индекс последнего значения в v , меньшего или равного x. Если x меньше всех значений в v, функция возвращает firstindex(v) - 1.

Вектор v должен быть отсортирован в соответствии с порядком, заданным ключевыми словами. См. sort! для значения ключевых слов и определения «меньше чем» и эквивалентности. Обратите внимание, что функция by применяется к искомому значению x и значениям в v.

Индекс обычно находится с помощью бинарного поиска, но существуют оптимизированные реализации для некоторых входных данных

Примеры

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

julia> searchsortedlast([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare the keys of the pairs
2

insorted(x, v; by=identity, lt=isless, rev=false) -> Bool

Определяет, содержит ли вектор v какое-либо значение, эквивалентное x . Вектор v должен быть отсортирован в соответствии с порядком, заданным ключевыми словами. См. sort! для значения ключевых слов и определения эквивалентности. Обратите внимание, что функция by применяется к искомому значению x и значениям в v.

Проверка обычно выполняется с помощью бинарного поиска, но существуют оптимизированные реализации для некоторых входных данных.

См. также 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

julia> insorted(2=>"TWO", [1=>"one", 2=>"two", 4=>"four"], by=first) # compare the keys of the pairs
true

partialsort!(v, k; by=identity, lt=isless, rev=false)

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

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

Примеры

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=identity, lt=isless, rev=false)

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

partialsortperm(v, k; by=ientity, lt=isless, 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=identity, lt=isless, rev=false)

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

ix инициализируется значениями индексов v.

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

По возвращении 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)
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 или функцией, которая подчиняется тем же правилам, что и параметр lt функции sort!. Наконец, полученный порядок инвертируется, если 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 должно подчиняться тем же правилам, что и параметр lt метода sort!.

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

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