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
 1

sort は、入力を変更せずにソート済みのコピーを作成します。既存の配列を変更するには、ソート関数の「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を参照してください。

Julia 1.1

この関数を使用するには、Julia 1.1以降が必要です。

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  4
source
sort!(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.0
source
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 を、指定した次元に沿ってソートします。使用可能なキーワード引数については、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  2
source
sort(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...)::NTuple

sort!の変種で、vのソート済みコピーを返し、v自体は変更しません。

辞書のkeysまたはvaluesに対してsortを呼び出すと、vが収集されてからソートされます。

Julia 1.12

NTupleのソートにはJulia 1.12以降が必要です。

Julia 1.13

キーセットと値イテレータのソートにはJulia 1.13以降が必要です。

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
 2
source
Base.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 を参照してください。

Julia 1.9

dims を受け取るメソッドを使用するには、Julia 1.9 以降が必要です。

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  4
source
Base.Sort.InsertionSort — Constant
InsertionSort

挿入ソートアルゴリズムを使用します。

挿入ソートはコレクションを1要素ずつ走査し、各要素を出力ベクトル内の正しい位置に挿入して、整列済みの状態にします。

特徴:

  • 安定: 比較結果が等しい要素の順序を保持します

(たとえば、大文字と小文字を区別しない文字のソートにおける「a」と「A」)。

  • メモリ上で インプレース に動作します。
  • ソートする要素数に対して 二次時間 で動作します。

小規模なコレクションには適していますが、大規模なコレクションには使用しないでください。

source
Base.Sort.MergeSort — Constant
MergeSort

ソート関数でマージソートアルゴリズムを使用するよう指定します。マージソートでは、コレクションを複数の部分コレクションに分割し、各段階でそれぞれをソートしながら繰り返しマージして、最終的にコレクション全体をソート済みの状態に再構成します。

特徴:

  • 安定: 比較結果が等しい要素の順序を保持します(例:大文字と小文字を区別しない文字のソートにおける「a」と「A」)。
  • メモリ上で インプレースではない。
  • 分割統治法によるソート戦略。
  • 大規模なコレクションでも 高い性能を発揮しますが、通常はQuickSortほど高速ではありません。
source
Base.Sort.QuickSort — Constant
QuickSort

ソート関数でクイックソートアルゴリズムを使用することを指定します。このアルゴリズムは安定ではありません。

特徴:

  • 安定ではない: 比較結果が等しい要素の順序を保持しません(たとえば、大文字と小文字を区別しない文字のソートでは、「a」と「A」の順序が保持されません)。
  • メモリ上でインプレースに処理します。
  • 分割統治法: MergeSortに似たソート戦略です。
  • 大規模なコレクションでも高い性能を発揮します。
source
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]
true
source
Base.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)を含むように初期化されます。

Warning

変更される引数がほかの引数とメモリを共有している場合、予期しない動作になることがあります。

Julia 1.9

dimsを受け取るメソッドの使用には、Julia 1.9以降が必要です。

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  4
source
Base.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  -2

Higher 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] =
 5
source
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)
true
source
Base.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:3
source
Base.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
3
source
Base.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
2
source
Base.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
true
Julia 1.6

insorted は Julia 1.6 で追加されました。

source
Base.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
 1
source
Base.Sort.partialsort — Function
partialsort(v, k, by=identity, lt=isless, rev=false, order::Base.Order.Ordering=Base.Order.Forward)

partialsort! の変種です。v をコピーしてから部分ソートするため、partialsort! と同じものを返しますが、v は変更しません。

source
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
 2
source
Base.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のビューです。

Warning

変更される引数がほかの引数とメモリを共有している場合、予期しない動作になることがあります。

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
 3
source

Sorting 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}}) = InlineStringSort
Julia 1.9

Base.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.Ordering

ある要素集合上の狭義弱順序を表す抽象型です。詳しくはsort!を参照してください。

順序に従って2つの要素を比較するには、Base.Order.ltを使用します。

source
Base.Order.lt — Function
lt(o::Ordering, a, b)::Bool

a が、順序 o に従って b より小さいかどうかをテストします。

source
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を同時に渡すことはできません。それ以外のオプションはすべて独立しており、あらゆる組み合わせで併用できます。

source
Base.Order.ReverseOrdering — Type
ReverseOrdering(fwd::Ordering=Forward)

順序を逆転させるラッパー。

与えられた Ordering o について、すべての a、b に対して、次が成り立つ。

lt(ReverseOrdering(o), a, b) == lt(o, b, a)
source
Base.Order.By — Type
By(by, order::Ordering=Forward)

Ordering は、関数 by によって変換された後の要素に order を適用します。

source
Base.Order.Lt — Type
Lt(lt)

要素を比較するために lt(a, b) を呼び出す Ordering。lt は、sort! の lt パラメーターと同じ規則に従う必要があります。

source
Base.Order.Perm — Type
Perm(order::Ordering, data::AbstractVector)

Ordering は、data のインデックスのうち、i が j より小さいものを、data[i] が data[j] より小さい場合に、order に従って並べ替えます。data[i] と data[j] が等しい場合は、i と j を数値として比較します。

source