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

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

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

Примеры для многомерных случаев

julia> A = [4 3; 2 1 ;;; 'A' 'B'; 'C' 'D']
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. Если все значения в v упорядочены перед x, возвращает lastindex(v) + 1.

Вектор v должен быть отсортирован в соответствии с порядком, определённым ключевыми словами. Вставка x в позицию, возвращённую функцией, сохранит упорядоченность. Обратитесь к 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. Если все значения в v упорядочены после x, возвращает firstindex(v) - 1.

Вектор v должен быть отсортирован в соответствии с порядком, определённым ключевыми словами. Вставка x сразу после возвращённого индекса сохранит упорядоченность. Обратитесь к 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=identity, 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

Абстрактный тип, представляющий строгий слабый порядок на некотором наборе элементов. См. sort! для более подробной информации.

Используйте Base.Order.lt для сравнения двух элементов в соответствии с упорядочением.

lt(o::Ordering, a, b) -> Bool

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