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

В 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.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) отсортирует фрагменты внутри 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

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