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

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

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

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

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

Для сортировки массива на месте используйте «bang» версию функции sort:

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

julia> sort!(a);

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

Все функции сортировки и связанные с порядком функции полагаются на отношение «меньше чем», определяющее общий порядок на значениях, которые должны быть обработаны. Функция isless вызывается по умолчанию, но отношение можно указать с помощью ключевого слова lt.

Функции сортировки

Base.sort!Функция

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

Base.sortФункция

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! для описания возможных ключевых аргументов.

Примеры

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

Base.sortpermФункция

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

Base.Sort.sortperm!Функция

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

Base.sortslicesФункция

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) отсортирует срезы в 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

Функции, связанные с порядком

Base.issortedФункция

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

Base.Sort.searchsortedФункция

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Возвращает диапазон индексов a, которые сравниваются как равные x (с использованием двоичного поиска) в соответствии с порядком, заданным ключевыми словами by, lt и rev, предполагая, что a уже отсортирован в этом порядке. Возвращает пустой диапазон, расположенный в точке вставки, если a не содержит значений, равных x.

Примеры

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

julia> searchsorted(a, 4)
5:4

julia> searchsorted(a, 4, rev=true)
1:1

Base.Sort.searchsortedfirstФункция

searchsortedfirst(a, x; by=<transform>, lt=<comparison>, rev=false)

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

Примеры

julia> searchsortedfirst([1, 2, 4, 5, 14], 4)
3

julia> searchsortedfirst([1, 2, 4, 5, 14], 4, rev=true)
1

julia> searchsortedfirst([1, 2, 4, 5, 14], 15)
6

Base.Sort.searchsortedlastФункция

searchsortedlast(a, x; by=<transform>, lt=<comparison>, rev=false)

Возвращает индекс последнего значения в a меньше или равного x, в соответствии с заданным порядком. Возвращает 0 если x меньше всех значений в a. a предполагается отсортированным.

Примеры

julia> searchsortedlast([1, 2, 4, 5, 14], 4)
3

julia> searchsortedlast([1, 2, 4, 5, 14], 4, rev=true)
5

julia> searchsortedlast([1, 2, 4, 5, 14], -1)
0

Base.Sort.partialsort!Функция

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

Base.Sort.partialsortФункция

partialsort(v, k, by=<transform>, lt=<comparison>, rev=false)

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

Base.Sort.partialsortpermФункция

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

Base.Sort.partialsortperm!Функция

partialsortperm!(ix, v, k; by=<transform>, lt=<comparison>, rev=false, initialized=false)

Подобно partialsortperm, но принимает предварительно выделенный вектор индексов ix. Если initialized равно false (по умолчанию), ix инициализируется значениями 1:length(ix).

Сортировочные алгоритмы

В настоящее время в базовой Julia доступны четыре сортировочных алгоритма:

• InsertionSort
• QuickSort
• PartialQuickSort(k)
• MergeSort

InsertionSort — это стабильный сортировочный алгоритм со сложностью O(n^2). Он эффективен для очень малых n и используется внутри QuickSort.

QuickSort — это сортировочный алгоритм со сложностью O(n log n), выполняемый на месте, очень быстрый, но нестабильный — то есть элементы, которые считаются равными, не сохранят тот же порядок, в котором они первоначально были в массиве, подлежащем сортировке. QuickSort является алгоритмом по умолчанию для числовых значений, включая целые числа и числа с плавающей точкой.

PartialQuickSort(k) подобен QuickSort, но выходной массив сортируется только до индекса k, если k является целым числом, или в диапазоне k, если k является OrdinalRange. Например:

x = rand(1:500, 100)
k = 50
k2 = 50:100
s = sort(x; alg=QuickSort)
ps = sort(x; alg=PartialQuickSort(k))
qs = sort(x; alg=PartialQuickSort(k2))
map(issorted, (s, ps, qs))             # => (true, false, false)
map(x->issorted(x[1:k]), (s, ps, qs))  # => (true, true, false)
map(x->issorted(x[k2]), (s, ps, qs))   # => (true, false, true)
s[1:k] == ps[1:k]                      # => true
s[k2] == qs[k2]                        # => true

MergeSort — это стабильный сортировочный алгоритм со сложностью O(n log n), но не выполняется на месте — он требует временного массива размером в половину входного массива — и обычно не так быстр, как QuickSort. Это алгоритм по умолчанию для нечисловых данных.

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

Механизм выбора алгоритмов сортировки по умолчанию в Julia реализован с помощью функции Base.Sort.defalg. Он позволяет зарегистрировать определённый алгоритм в качестве значения по умолчанию для всех функций сортировки для конкретных массивов. Например, вот два метода по умолчанию из sort.jl:

defalg(v::AbstractArray) = MergeSort
defalg(v::AbstractArray{<:Number}) = QuickSort

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