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

В 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.

Функции сортировки

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

Отсортировать вектор v на месте. QuickSort используется по умолчанию для числовых массивов, а MergeSort используется для других массивов. Вы можете указать алгоритм для использования с помощью ключевого слова alg (см. Алгоритмы сортировки для доступных алгоритмов). Ключевое слово by позволяет предоставить функцию, которая будет применяться к каждому элементу перед сравнением; ключевое слово lt позволяет предоставить пользовательскую функцию «меньше чем»; используйте rev=true для изменения порядка сортировки на обратный. Эти опции независимы и могут быть использованы вместе во всех возможных комбинациях: если указаны как by, так и lt, функция lt применяется к результату функции by; rev=true инвертирует любой порядок, заданный ключевыми словами by и lt.

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

Вариант функции sort!, который возвращает отсортированную копию v, оставляя v неизменной.

sort(A, dim, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])

Отсортировать многомерный массив A по заданной размерности.

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

Возвращает вектор перестановок индексов v, который упорядочивает его по возрастанию. Укажите alg для выбора конкретного алгоритма сортировки (см. Алгоритмы сортировки). MergeSort используется по умолчанию, и поскольку он устойчив, полученная перестановка будет первой лексикографически, которая упорядочивает входной массив — т. е. индексы равных элементов появляются в порядке возрастания. Если вы выберете неустойчивый алгоритм сортировки, такой как QuickSort, может быть возвращена другая перестановка, упорядочивающая массив. Порядок задаётся с помощью тех же ключевых слов, что и для sort!.

См. также sortperm!().

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

Как sortperm, но принимает предварительно выделенный вектор индексов ix. Если initialized равно false (по умолчанию), ix инициализируется значениями 1:length(v).

См. также sortperm().

sortrows(A, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])

Отсортировать строки матрицы A лексикографически.

sortcols(A, [alg=<algorithm>,] [by=<transform>,] [lt=<comparison>,] [rev=false])

Отсортировать столбцы матрицы A лексикографически.

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

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

Проверить, отсортирован ли вектор в порядке возрастания. Ключевые слова by, lt и rev изменяют, какой порядок считается отсортированным, так же, как и для sort.

searchsorted(a, x, [by=<transform>,] [lt=<comparison>,] [rev=false])

Возвращает диапазон индексов a, которые сравниваются как равные x согласно порядку, заданному ключевыми словами by, lt и rev, предполагая, что a уже отсортирован в этом порядке. Возвращает пустой диапазон, расположенный в точке вставки, если a не содержит значений, равных x.

searchsortedfirst(a, x, [by=<transform>,] [lt=<comparison>,] [rev=false])

Возвращает индекс первого значения в a больше или равно x, согласно заданному порядку. Возвращает length(a)+1 если x больше всех значений в a.

searchsortedlast(a, x, [by=<transform>,] [lt=<comparison>,] [rev=false])

Возвращает индекс последнего значения в a меньше или равно x, согласно заданному порядку. Возвращает 0 если x меньше всех значений в a.

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

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

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

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

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]

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

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