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

В 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(v), 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

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