Sorting and Related Functions

Julia имеет обширный, гибкий API для сортировки и взаимодействия с уже отсортированными массивами значений. По умолчанию Julia выбирает разумные алгоритмы и сортирует в порядке возрастания:

julia> sort([2,3,1])
3-element Vector{Int64}:
 1
 2
 3

Вы также можете сортировать в обратном порядке:

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

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

julia> a = [2,3,1];

julia> sort!(a);

julia> a
3-element Vector{Int64}:
 1
 2
 3

Вместо того чтобы напрямую сортировать массив, вы можете вычислить перестановку индексов массива, которая приведет массив в отсортированный порядок:

julia> v = randn(5)
5-element Array{Float64,1}:
  0.297288
  0.382396
 -0.597634
 -0.0104452
 -0.839027

julia> p = sortperm(v)
5-element Array{Int64,1}:
 5
 3
 4
 1
 2

julia> v[p]
5-element Array{Float64,1}:
 -0.839027
 -0.597634
 -0.0104452
  0.297288
  0.382396

Массивы могут быть отсортированы в соответствии с произвольной трансформацией их значений:

julia> sort(v, by=abs)
5-element Array{Float64,1}:
 -0.0104452
  0.297288
  0.382396
 -0.597634
 -0.839027

Или в обратном порядке с помощью преобразования:

julia> sort(v, by=abs, rev=true)
5-element Array{Float64,1}:
 -0.839027
 -0.597634
  0.382396
  0.297288
 -0.0104452

Если необходимо, можно выбрать алгоритм сортировки:

julia> sort(v, alg=InsertionSort)
5-element Array{Float64,1}:
 -0.839027
 -0.597634
 -0.0104452
  0.297288
  0.382396

Все функции, связанные с сортировкой и порядком, полагаются на отношение "меньше чем", определяющее strict weak order для значений, которые необходимо обработать. Функция isless вызывается по умолчанию, но отношение может быть указано через ключевое слово lt, функцию, которая принимает два элемента массива и возвращает true, если и только если первый аргумент "меньше чем" второй. См. sort! и Alternate Orderings для получения дополнительной информации.

Sorting Functions

Base.sort! — Function

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 не эквивалентны.

Примеры

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)) # то же самое, что sort(0:3, by=abs(x->x-2))
4-element Vector{Int64}:
 2
 1
 3
 0

julia> sort([2, NaN, 1, NaN, 3]) # правильная сортировка с lt по умолчанию = isless
5-element Vector{Float64}:
   1.0
   2.0
   3.0
 NaN
 NaN

julia> sort([2, NaN, 1, NaN, 3], lt=<) # неправильная сортировка из-за недопустимого lt. Это поведение неопределено.
5-element Vector{Float64}:
   2.0
 NaN
   1.0
 NaN
   3.0

Sorting Functions

Order-Related Functions

Sorting Algorithms

Alternate Orderings