Sorting and Related Functions
Julia には、値の配列をソートしたり、すでにソート済みの配列を操作したりするための、豊富で柔軟な API が用意されています。デフォルトでは、Julia は適切なアルゴリズムを選び、昇順にソートします。
julia> sort([2,3,1])
3-element Vector{Int64}:
1
2
3降順にソートすることもできます。
julia> sort([2,3,1], rev=true)
3-element Vector{Int64}:
3
2
1sort は、入力を変更せずにソート済みのコピーを作成します。既存の配列を変更するには、ソート関数の「bang」版を使います。
julia> a = [2,3,1];
julia> sort!(a);
julia> a
3-element Vector{Int64}:
1
2
3配列を直接ソートする代わりに、配列をソート済みの順序に並べ替えるインデックスの順列を計算できます。
julia> v = [0.297288, 0.382396, -0.597634, -0.0104452, -0.839027]
5-element Vector{Float64}:
0.297288
0.382396
-0.597634
-0.0104452
-0.839027
julia> p = sortperm(v)
5-element Vector{Int64}:
5
3
4
1
2
julia> v[p]
5-element Vector{Float64}:
-0.839027
-0.597634
-0.0104452
0.297288
0.382396配列の値に任意の変換を適用した結果に基づいて、配列をソートすることもできます。
julia> sort(v, by=abs)
5-element Vector{Float64}:
-0.0104452
0.297288
0.382396
-0.597634
-0.839027変換を適用した結果に基づき、降順にソートすることもできます。
julia> sort(v, by=abs, rev=true)
5-element Vector{Float64}:
-0.839027
-0.597634
0.382396
0.297288
-0.0104452必要に応じて、ソートアルゴリズムを選択できます。
julia> sort(v, alg=InsertionSort)
5-element Vector{Float64}:
-0.839027
-0.597634
-0.0104452
0.297288
0.382396ソートや順序に関する関数はすべて、操作対象の値に対するstrict weak orderを定義する「より小さい」関係に依存します。デフォルトではisless関数が呼び出されますが、ltキーワードで関係を指定することもできます。このキーワードには、配列の要素を2つ受け取り、第1引数が第2引数より「小さい」場合に限りtrueを返す関数を指定します。詳しくはsort!とAlternate Orderingsを参照してください。
Sorting Functions
Base.sort! — Function
sort!(A; dims::Integer, alg::Base.Sort.Algorithm=Base.Sort.defalg(A), lt=isless, by=identity, rev::Bool=false, order::Base.Order.Ordering=Base.Order.Forward)多次元配列Aを、次元dimsに沿ってソートします。指定可能なキーワード引数については、1次元版のsort!を参照してください。
配列のスライスをソートする方法については、sortslicesを参照してください。
Examples
julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
4 3
1 2
julia> sort!(A, dims = 1); A
2×2 Matrix{Int64}:
1 2
4 3
julia> sort!(A, dims = 2); A
2×2 Matrix{Int64}:
1 2
3 4sort!(v; alg::Base.Sort.Algorithm=Base.Sort.defalg(v), lt=isless, by=identity, rev::Bool=false, order::Base.Order.Ordering=Base.Order.Forward)ベクトル v を並べ替えて、ソート済みにします。
デフォルトでは安定アルゴリズムが使われ、比較結果が等しい要素の順序は保持されます。特定のアルゴリズムは alg キーワードで選択できます(利用可能なアルゴリズムについては Sorting Algorithms を参照)。
まず要素を関数 by で変換し、その後、関数 lt または順序 order に従って比較します。最後に、rev=true の場合は結果の順序を逆にします(この場合も前方安定性は保たれ、比較結果が等しい要素の順序は逆転しません)。現在の実装では、要素ごとに一度だけ変換するのではなく、比較のたびに by 変換を適用します。
lt に isless 以外を指定し、同時に order に Base.Order.Forward または Base.Order.Reverse 以外を指定することはできません。それ以外のオプションは互いに独立しており、あらゆる組み合わせで併用できます。order に「by」変換を含めることもできます。その場合、この変換は by キーワードで定義した変換の後に適用されます。order の値について詳しくは、Alternate Orderings のドキュメントを参照してください。
2つの要素間の関係は、次のように定義されます(rev=true の場合は「小さい」と「大きい」が入れ替わります)。
xは、lt(by(x), by(y))(またはBase.Order.lt(order, by(x), by(y)))が true を返す場合、yより小さいとします。xは、yがxより小さい場合、yより大きいとします。xとyは、どちらも相手より小さくない場合、同値とします(「比較不能」が「同値」の同義語として使われることもあります)。
sort! の結果は、すべての要素が直前の要素より大きいか、または同値であるという意味でソート済みです。
lt 関数は狭義弱順序を定義しなければなりません。つまり、次の性質を満たす必要があります。
- 非反射性:
lt(x, x)は常にfalseを返す。 - 非対称性:
lt(x, y)がtrueを返すなら、lt(y, x)はfalseを返す。 - 推移性:
lt(x, y) && lt(y, z)ならばlt(x, z)。 - 同値関係の推移性:
!lt(x, y) && !lt(y, x)と!lt(y, z) && !lt(z, y)がともに成り立つなら、!lt(x, z) && !lt(z, x)が成り立つ。言い換えると、xとyが同値で、yとzも同値なら、xとzも同値でなければなりません。
たとえば、< は Int の値に対する有効な lt 関数ですが、≤ は非反射性に違反するため有効ではありません。Float64 の値では、< も第4の条件に違反するため無効です。1.0 と NaN は同値であり、NaN と 2.0 も同値ですが、1.0 と 2.0 は同値ではありません。
関連項目:sort、sortperm、sortslices、partialsort!、partialsortperm、issorted、searchsorted、insorted、Base.Order.ord。
Examples
julia> v = [3, 1, 2]; sort!(v); v
3-element Vector{Int64}:
1
2
3
julia> v = [3, 1, 2]; sort!(v, rev = true); v
3-element Vector{Int64}:
3
2
1
julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v
3-element Vector{Tuple{Int64, String}}:
(1, "c")
(2, "b")
(3, "a")
julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v
3-element Vector{Tuple{Int64, String}}:
(3, "a")
(2, "b")
(1, "c")
julia> sort(0:3, by=x->x-2, order=Base.Order.By(abs))
4-element Vector{Int64}:
2
1
3
0
julia> sort(0:3, by=x->x-2, order=Base.Order.By(abs)) == sort(0:3, by=x->abs(x-2))
true
julia> sort([2, NaN, 1, NaN, 3]) # correct sort with default lt=isless
5-element Vector{Float64}:
1.0
2.0
3.0
NaN
NaN
julia> sort([2, NaN, 1, NaN, 3], lt=<) # wrong sort due to invalid lt. This behavior is undefined.
5-element Vector{Float64}:
2.0
NaN
1.0
NaN
3.0Base.sort — Function
sort(A; dims::Integer, alg::Base.Sort.Algorithm=Base.Sort.defalg(A), lt=isless, by=identity, rev::Bool=false, order::Base.Order.Ordering=Base.Order.Forward)多次元配列 A を、指定した次元に沿ってソートします。使用可能なキーワード引数については、sort! を参照してください。
配列のスライスをソートする方法については、sortslices を参照してください。
Examples
julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
4 3
1 2
julia> sort(A, dims = 1)
2×2 Matrix{Int64}:
1 2
4 3
julia> sort(A, dims = 2)
2×2 Matrix{Int64}:
3 4
1 2sort(v; alg::Base.Sort.Algorithm=Base.Sort.defalg(v), lt=isless, by=identity, rev::Bool=false, order::Base.Order.Ordering=Base.Order.Forward)
sort(v::NTuple; kws...)::NTuplesort!の変種で、vのソート済みコピーを返し、v自体は変更しません。
辞書のkeysまたはvaluesに対してsortを呼び出すと、vが収集されてからソートされます。
Examples
julia> v = [3, 1, 2];
julia> sort(v)
3-element Vector{Int64}:
1
2
3
julia> v
3-element Vector{Int64}:
3
1
2
julia> sort(values(Dict('a'=>2, 'b'=>1)))
2-element Vector{Int64}:
1
2Base.sortperm — Function
sortperm(A; alg::Base.Sort.Algorithm=Base.Sort.DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Base.Order.Ordering=Base.Order.Forward, [dims::Integer])指定された次元に沿って A[I] をソートした順序に並べる置換ベクトルまたは配列 I を返します。A の次元数が 1 より大きい場合は、キーワード引数 dims を指定する必要があります。順序の指定には、sort! と同じキーワードを使用します。ソートアルゴリズムが不安定な場合でも、置換は安定であることが保証されます。つまり、等しい要素のインデックスは昇順に並びます。
関連項目: sortperm!、partialsortperm、invperm、indexin。配列のスライスをソートする方法については、sortslices を参照してください。
Examples
julia> v = [3, 1, 2];
julia> p = sortperm(v)
3-element Vector{Int64}:
2
3
1
julia> v[p]
3-element Vector{Int64}:
1
2
3
julia> A = [8 7; 5 6]
2×2 Matrix{Int64}:
8 7
5 6
julia> sortperm(A, dims = 1)
2×2 Matrix{Int64}:
2 4
1 3
julia> sortperm(A, dims = 2)
2×2 Matrix{Int64}:
3 1
2 4Base.Sort.InsertionSort — Constant
InsertionSort挿入ソートアルゴリズムを使用します。
挿入ソートはコレクションを1要素ずつ走査し、各要素を出力ベクトル内の正しい位置に挿入して、整列済みの状態にします。
特徴:
- 安定: 比較結果が等しい要素の順序を保持します
(たとえば、大文字と小文字を区別しない文字のソートにおける「a」と「A」)。
- メモリ上で インプレース に動作します。
- ソートする要素数に対して 二次時間 で動作します。
小規模なコレクションには適していますが、大規模なコレクションには使用しないでください。
Base.Sort.MergeSort — Constant
MergeSortソート関数でマージソートアルゴリズムを使用するよう指定します。マージソートでは、コレクションを複数の部分コレクションに分割し、各段階でそれぞれをソートしながら繰り返しマージして、最終的にコレクション全体をソート済みの状態に再構成します。
特徴:
- 安定: 比較結果が等しい要素の順序を保持します(例:大文字と小文字を区別しない文字のソートにおける「a」と「A」)。
- メモリ上で インプレースではない。
- 分割統治法によるソート戦略。
- 大規模なコレクションでも 高い性能を発揮しますが、通常は
QuickSortほど高速ではありません。
Base.Sort.QuickSort — Constant
QuickSortソート関数でクイックソートアルゴリズムを使用することを指定します。このアルゴリズムは安定ではありません。
特徴:
- 安定ではない: 比較結果が等しい要素の順序を保持しません(たとえば、大文字と小文字を区別しない文字のソートでは、「a」と「A」の順序が保持されません)。
- メモリ上でインプレースに処理します。
- 分割統治法:
MergeSortに似たソート戦略です。 - 大規模なコレクションでも高い性能を発揮します。
Base.Sort.PartialQuickSort — Type
PartialQuickSort{T <: Union{Integer,OrdinalRange}}ソート関数に部分クイックソートアルゴリズムを使うよう指定します。PartialQuickSort(k)はQuickSortに似ていますが、vを完全にソートした場合にv[k]に入る要素だけを見つけてソートすれば十分です。
特徴:
- 安定ではない: 比較結果が等しい要素の順序を保持しません(たとえば、大文字と小文字を区別しない文字のソートにおける「a」と「A」)。
- メモリ上でインプレースに処理します。
- 分割統治法: ソート戦略は
MergeSortに似ています。
PartialQuickSort(k)は、配列全体をソートするとは限りません。たとえば、
julia> x = rand(100);
julia> k = 50:100;
julia> s1 = sort(x; alg=QuickSort);
julia> s2 = sort(x; alg=PartialQuickSort(k));
julia> map(issorted, (s1, s2))
(true, false)
julia> map(x->issorted(x[k]), (s1, s2))
(true, true)
julia> s1[k] == s2[k]
trueBase.Sort.sortperm! — Function
sortperm!(ix, A; alg::Base.Sort.Algorithm=Base.Sort.DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Base.Order.Ordering=Base.Order.Forward, [dims::Integer])sortpermと同様ですが、あらかじめ確保されたインデックスベクトルまたは配列ixを受け取ります。この配列は、Aと同じaxesを持つ必要があります。ixは、値LinearIndices(A)を含むように初期化されます。
Examples
julia> v = [3, 1, 2]; p = zeros(Int, 3);
julia> sortperm!(p, v); p
3-element Vector{Int64}:
2
3
1
julia> v[p]
3-element Vector{Int64}:
1
2
3
julia> A = [8 7; 5 6]; p = zeros(Int,2, 2);
julia> sortperm!(p, A; dims=1); p
2×2 Matrix{Int64}:
2 4
1 3
julia> sortperm!(p, A; dims=2); p
2×2 Matrix{Int64}:
3 1
2 4Base.sortslices — Function
sortslices(A; dims, alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)配列 A のスライスをソートします。必須のキーワード引数 dims には、整数または整数のタプルを指定します。これは、スライスをソートする対象の次元を指定します。
たとえば、A が行列の場合、dims=1 は行を、dims=2 は列をソートします。1次元スライスに対するデフォルトの比較関数は、辞書順でソートすることに注意してください。
その他のキーワード引数については、sort! のドキュメントを参照してください。
Examples
julia> sortslices([7 3 5; -1 6 4; 9 -2 8], dims=1) # Sort rows
3×3 Matrix{Int64}:
-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 Matrix{Int64}:
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 Matrix{Int64}:
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 Matrix{Int64}:
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 Matrix{Int64}:
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 Matrix{Int64}:
7 5 3
6 -4 -1
9 8 -2Higher dimensions
sortslices は、高次元にも自然に拡張できます。たとえば、A が 2×2×2 の配列の場合、sortslices(A, dims=3) は第3次元に沿ったスライスをソートし、2×2 のスライス A[:, :, 1] と A[:, :, 2] を比較関数に渡します。高次元スライスにはデフォルトの順序がありませんが、by または lt キーワード引数を使って順序を指定できます。
dims がタプルの場合、dims における次元の順序が重要であり、スライスの線形順序を指定します。たとえば、A が3次元で、dims が (1, 2) の場合、残りの第3次元のスライスがソートされるように、最初の2次元の順序が入れ替えられます。代わりに dims が (2, 1) の場合も同じスライスが対象になりますが、結果は行優先の順序になります。
Higher dimensional examples
julia> A = [4 3; 2 1 ;;; 'A' 'B'; 'C' 'D']
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] =
5Order-Related Functions
Base.issorted — Function
issorted(itr, lt=isless, by=identity, rev::Bool=false, order::Base.Order.Ordering=Base.Order.Forward)コレクションがソート済みかどうかを判定します。キーワード引数によって、ソート済みとみなす順序を変更できます。詳しくはsort!のドキュメントを参照してください。
Examples
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
julia> issorted([1, 2, -2, 3], by=abs)
trueBase.Sort.searchsorted — Function
searchsorted(v, x; by=identity, lt=isless, rev=false)v内でxと等価な値がある場合は、そのインデックス範囲を返します。vにxと等価な値がない場合は、挿入位置を示す空の範囲を返します。ベクトルvは、キーワードで定義される順序に従ってソートされている必要があります。キーワードの意味と等価性の定義については、sort!を参照してください。by関数は、検索対象の値xだけでなく、v内の値にも適用されることに注意してください。
通常は二分探索で範囲を見つけますが、一部の入力には最適化された実装が用意されています。
関連項目: searchsortedfirst、sort!、insorted、findall。
Examples
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 (empty range)
julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6 (empty range)
julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0 (empty range)
julia> searchsorted([1=>"one", 2=>"two", 2=>"two", 4=>"four"], 2=>"two", by=first) # compare the keys of the pairs
2:3Base.Sort.searchsortedfirst — Function
searchsortedfirst(v, x; by=identity, lt=isless, rev=false)vの値のうち、xより前に並んでいない最初の値のインデックスを返します。vのすべての値がxより前に並んでいる場合は、lastindex(v) + 1を返します。
ベクトルvは、キーワードで定義された順序に従ってソートされている必要があります。返されたインデックスにxをinsert!すると、ソート順が保たれます。キーワードの意味と使い方については、sort!を参照してください。by関数は、検索対象の値xだけでなく、v内の値にも適用されることに注意してください。
インデックスは通常、二分探索で求められますが、一部の入力には最適化された実装が用意されています。
関連項目: searchsortedlast、searchsorted、findfirst。
Examples
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
julia> searchsortedfirst([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare the keys of the pairs
3Base.Sort.searchsortedlast — Function
searchsortedlast(v, x; by=identity, lt=isless, rev=false)vのうち、xより後に並ばない最後の値のインデックスを返します。vのすべての値がxより後に並ぶ場合は、firstindex(v) - 1を返します。
ベクトルvは、キーワードで定義された順序に従ってソートされている必要があります。返されたインデックスの直後にinsert!ing xを挿入すると、ソート順が保たれます。キーワードの意味と使い方については、sort!を参照してください。by関数は、検索対象の値xだけでなく、v内の値にも適用されることに注意してください。
インデックスは通常、二分探索で求められますが、一部の入力には最適化された実装があります。
Examples
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
julia> searchsortedlast([1=>"one", 2=>"two", 4=>"four"], 3=>"three", by=first) # compare the keys of the pairs
2Base.Sort.insorted — Function
insorted(x, v; by=identity, lt=isless, rev=false)::Boolベクトル v に、x と等価な値が含まれているかどうかを判定します。ベクトル v は、キーワードで定義される順序に従ってソートされている必要があります。キーワードの意味と等価性の定義については、sort! を参照してください。検索対象の値 x にも、v 内の値と同様に、by 関数が適用される点に注意してください。
通常は二分探索で判定しますが、一部の入力には最適化された実装が用意されています。
in も参照してください。
Examples
julia> insorted(4, [1, 2, 4, 5, 5, 7]) # single match
true
julia> insorted(5, [1, 2, 4, 5, 5, 7]) # multiple matches
true
julia> insorted(3, [1, 2, 4, 5, 5, 7]) # no match
false
julia> insorted(9, [1, 2, 4, 5, 5, 7]) # no match
false
julia> insorted(0, [1, 2, 4, 5, 5, 7]) # no match
false
julia> insorted(2=>"TWO", [1=>"one", 2=>"two", 4=>"four"], by=first) # compare the keys of the pairs
trueBase.Sort.partialsort! — Function
partialsort!(v, k; by=identity, lt=isless, rev=false, order::Base.Order.Ordering=Base.Order.Forward)ベクトル v を変更し、インデックス k の値(k が範囲の場合は、隣接する値の範囲)が、配列全体をソートした場合に現れる位置に来るようにします。k が単一のインデックスの場合はその値を返し、k が範囲の場合は、それらのインデックスにある値の配列を返します。partialsort! は入力配列を完全にはソートしない場合があることに注意してください。
キーワード引数については、sort! のドキュメントを参照してください。
Examples
julia> a = [1, 2, 4, 3, 4]
5-element Vector{Int64}:
1
2
4
3
4
julia> partialsort!(a, 4)
4
julia> a
5-element Vector{Int64}:
1
2
3
4
4
julia> a = [1, 2, 4, 3, 4]
5-element Vector{Int64}:
1
2
4
3
4
julia> partialsort!(a, 4, rev=true)
2
julia> a
5-element Vector{Int64}:
4
4
3
2
1Base.Sort.partialsort — Function
partialsort(v, k, by=identity, lt=isless, rev=false, order::Base.Order.Ordering=Base.Order.Forward)partialsort! の変種です。v をコピーしてから部分ソートするため、partialsort! と同じものを返しますが、v は変更しません。
Base.Sort.partialsortperm — Function
partialsortperm(v, k; by=identity, lt=isless, rev=false)ベクトル v の部分順列 I を返します。この順列を使うと、v[I] は、v を完全にソートした場合の、インデックス k に対応する値を返します。k が範囲の場合はインデックスのベクトルを返し、k が整数の場合は単一のインデックスを返します。順序は sort! と同じキーワードで指定します。順列は安定しており、等しい要素のインデックスは昇順で並びます。
この関数は sortperm(...)[k] を呼び出すのと同等ですが、より効率的です。
Examples
julia> v = [3, 1, 2, 1];
julia> v[partialsortperm(v, 1)]
1
julia> p = partialsortperm(v, 1:3)
3-element view(::Vector{Int64}, 1:3) with eltype Int64:
2
4
3
julia> v[p]
3-element Vector{Int64}:
1
1
2Base.Sort.partialsortperm! — Function
partialsortperm!(ix, v, k; by=identity, lt=isless, rev=false)partialsortpermと同様ですが、vと同じサイズの、事前に確保されたインデックスベクトルixを受け取ります。このベクトルには、vのインデックス(の順列)が格納されます。
ixには、vのインデックスが初期値として格納されます。
(通常、vのインデックスは1:length(v)ですが、vがOffsetArrayなどの1始まりでないインデックスを持つ代替配列型の場合、ixも同じインデックスを持つ必要があります。)
呼び出しから戻ると、ixでは、kのインデックスがソート後の位置にあることが保証されます。したがって、
partialsortperm!(ix, v, k);
v[ix[k]] == partialsort(v, k)戻り値は、kが整数の場合はixのk番目の要素、kが範囲の場合はixのビューです。
Examples
julia> v = [3, 1, 2, 1];
julia> ix = Vector{Int}(undef, 4);
julia> partialsortperm!(ix, v, 1)
2
julia> ix = [1:4;];
julia> partialsortperm!(ix, v, 2:3)
2-element view(::Vector{Int64}, 2:3) with eltype Int64:
4
3Sorting Algorithms
現在、Julia の Base では、次の4つのソートアルゴリズムが公開されています。
デフォルトでは、sortファミリーの関数は、ほとんどの入力で高速に動作する安定ソートアルゴリズムを使用します。将来の性能向上に備え、具体的にどのアルゴリズムを選ぶかは実装の詳細とされています。現在は、入力の型、サイズ、構成に応じて、RadixSort、ScratchQuickSort、InsertionSort、CountingSortを組み合わせて使用しています。実装の詳細は変更される可能性がありますが、現時点では??Base.DEFAULT_STABLEの拡張ヘルプと、そこに記載されている内部ソートアルゴリズムのdocstringで確認できます。
algキーワードで、使用するアルゴリズムを明示的に指定できます(例:sort!(v, alg=PartialQuickSort(10:20)))。また、Base.Sort.defalg関数に特化メソッドを追加すれば、独自の型に対するデフォルトのソートアルゴリズムを変更できます。たとえば、InlineStrings.jlでは、次のメソッドを定義しています。
Base.Sort.defalg(::AbstractArray{<:Union{SmallInlineStrings, Missing}}) = InlineStringSortBase.Sort.defalgが返すデフォルトのソートアルゴリズムは、Julia 1.9以降、安定であることが保証されています。それ以前のバージョンでは、数値配列のソート時に不安定になるケースがありました。
Alternate Orderings
デフォルトでは、sort、searchsortedなどの関数は、2つの要素を比較してどちらを先に並べるかを決めるために、islessを使用します。Base.Order.Ordering抽象型を使うと、同じ要素集合に対して別の順序を定義できます。sort!のようなソート関数を呼び出す際に、Orderingのインスタンスをorderキーワード引数で指定できます。
Orderingのインスタンスは、Base.Order.lt関数を通じて順序を定義します。この関数はislessを一般化したものです。独自のOrderingに対するこの関数の動作は、strict weak orderのすべての条件を満たす必要があります。有効なlt関数と無効なものの詳細や例については、sort!を参照してください。
Base.Order.Ordering — Type
Base.Order.lt — Function
lt(o::Ordering, a, b)::Boola が、順序 o に従って b より小さいかどうかをテストします。
Base.Order.ord — Function
ord(lt, by, rev::Union{Bool, Nothing}, order::Ordering=Forward)sort!と同じ引数を使って、Orderingオブジェクトを構築します。要素はまず関数by(identityの場合もあります)によって変換され、その後、関数ltまたは既存の順序orderに従って比較されます。ltには、isless、またはsort!のltパラメーターと同じ規則に従う関数を指定してください。最後に、rev=trueの場合は、結果の順序が逆になります。
isless以外のltと、Base.Order.ForwardまたはBase.Order.Reverse以外のorderを同時に渡すことはできません。それ以外のオプションはすべて独立しており、あらゆる組み合わせで併用できます。
Base.Order.Forward — Constant
Base.Order.Forwardislessに従ったデフォルトの順序。
Base.Order.ReverseOrdering — Type
ReverseOrdering(fwd::Ordering=Forward)順序を逆転させるラッパー。
与えられた Ordering o について、すべての a、b に対して、次が成り立つ。
lt(ReverseOrdering(o), a, b) == lt(o, b, a)Base.Order.Reverse — Constant
Base.Order.Reverseislessに従って順序を逆にします。
Base.Order.By — Type
By(by, order::Ordering=Forward)Ordering は、関数 by によって変換された後の要素に order を適用します。
Base.Order.Lt — Type
Lt(lt)要素を比較するために lt(a, b) を呼び出す Ordering。lt は、sort! の lt パラメーターと同じ規則に従う必要があります。
Base.Order.Perm — Type
Perm(order::Ordering, data::AbstractVector)Ordering は、data のインデックスのうち、i が j より小さいものを、data[i] が data[j] より小さい場合に、order に従って並べ替えます。data[i] と data[j] が等しい場合は、i と j を数値として比較します。