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

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

Чтобы отсортировать массив на месте, используйте версию функции 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> 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

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