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

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

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, dim::Integer; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, initialized::Bool=false)

Сортировка многомерного массива A по заданному измерению. См. sort! для описания возможных ключевых аргументов.

Примеры

julia> A = [4 3; 1 2]
2×2 Array{Int64,2}:
 4  3
 1  2

julia> sort(A, 1)
2×2 Array{Int64,2}:
 1  2
 4  3

julia> sort(A, 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)

Возвращает вектор перестановок индексов v, который упорядочивает его по возрастанию. Укажите alg для выбора определенного алгоритма сортировки (см. Алгоритмы сортировки). По умолчанию используется MergeSort, и поскольку он устойчив, полученная перестановка будет первой в лексикографическом порядке, которая упорядочивает входной массив — т. е. индексы равных элементов появляются в порядке возрастания. Если вы выберите неустойчивый алгоритм сортировки, такой как QuickSort, может быть возвращена другая перестановка, которая упорядочивает массив. Порядок задается с помощью тех же ключевых слов, что и для 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.Sort.sortrowsФункция

sortrows(A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Сортировка строк матрицы A по лексикографическому порядку. См. sort! для описания возможных ключевых аргументов.

Примеры

julia> sortrows([7 3 5; -1 6 4; 9 -2 8])
3×3 Array{Int64,2}:
 -1   6  4
  7   3  5
  9  -2  8

julia> sortrows([7 3 5; -1 6 4; 9 -2 8], lt=(x,y)->isless(x[2],y[2]))
3×3 Array{Int64,2}:
  9  -2  8
  7   3  5
 -1   6  4

julia> sortrows([7 3 5; -1 6 4; 9 -2 8], rev=true)
3×3 Array{Int64,2}:
  9  -2  8
  7   3  5
 -1   6  4

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

sortcols(A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Сортировка столбцов матрицы A по лексикографическому порядку. См. sort! для описания возможных ключевых аргументов.

Примеры

julia> sortcols([7 3 5; 6 -1 -4; 9 -2 8])
3×3 Array{Int64,2}:
  3   5  7
 -1  -4  6
 -2   8  9

julia> sortcols([7 3 5; 6 -1 -4; 9 -2 8], 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> sortcols([7 3 5; 6 -1 -4; 9 -2 8], rev=true)
3×3 Array{Int64,2}:
 7   5   3
 6  -4  -1
 9   8  -2

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

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.select!Функция

select!(v, k, [by=<transform>,] [lt=<comparison>,] [rev=false])

Частичная сортировка вектора v на месте, в соответствии с порядком, указанным в by, lt и rev, таким образом, что значение с индексом k (или диапазон смежных значений, если k — диапазон) находится в позиции, где оно бы появилось, если бы массив был полностью отсортирован с помощью неустойчивого алгоритма. Если k — один индекс, то возвращается это значение; если k — диапазон, возвращается массив значений в этих индексах. Обратите внимание, что select! не полностью сортирует входной массив.

Примеры

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

julia> select!(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> select!(a, 4, rev=true)
2

julia> a
5-element Array{Int64,1}:
 4
 4
 3
 2
 1

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

select(v, k, [by=<transform>,] [lt=<comparison>,] [rev=false])

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

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

selectperm(v, k, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])

Возвращает частичную перестановку вектора v, согласно порядку, заданному by, lt и rev, так что v[output] возвращает первые k (или диапазон смежных значений, если k является диапазоном) значения полностью отсортированной версии v. Если k — это одиночный индекс (целое число), возвращается массив первых k индексов; если k — это диапазон, возвращается массив этих индексов. Обратите внимание, что обработка целочисленных значений для k отличается от select тем, что она возвращает вектор из k элементов вместо только k-го элемента. Также обратите внимание, что это эквивалентно, но более эффективно, чем вызов sortperm(...)[k].

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

selectperm!(ix, v, k, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false,] [initialized=false])

Аналогично selectperm, но принимает предварительно выделенный вектор индексов 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{T<:Number}(v::AbstractArray{T}) = QuickSort

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