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

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

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

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

Для сортировки срезов массива, обратитесь к 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

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.InsertionSortКонстанта

InsertionSort

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

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

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

Base.Sort.MergeSortКонстанта

MergeSort

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

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

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

Base.Sort.QuickSortКонстанта

QuickSort

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

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

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

Base.Sort.PartialQuickSortТип

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

Указывает, что функция сортировки должна использовать алгоритм частичной быстрой сортировки. Частичная быстрая сортировка возвращает k наименьших элементов, отсортированных от наименьшего к наибольшему, найдя и отсортировав их с помощью QuickSort.

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

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

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) отсортирует срезы внутри третьей размерности, передав срезы 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> 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

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, 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

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

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

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

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