ソート
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 を指定すると、by 関数の結果が lt 関数で比較されます。さらに 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(A),
lt=isless,
by=identity,
rev::Bool=false,
order::Ordering=Forward)
多次元配列 A を dims 番目の次元に沿ってソートします。ソートが完了すると、A の dims 番目の次元を取り出すスライスがソート済みとなります。キーワード引数の説明は sort! を参照してください。
配列のスライスをソートするには sortslices を使ってください。
この関数は Julia 1.1 以降でサポートされます。
例
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)
ソートした v のコピーを返すバージョンの sort! です。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 を dims 番目の次元に沿ってソートします。ソートが完了すると、A の dims 番目の次元を取り出すスライスがソート済みとなります。キーワード引数の説明は 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)
v[I] がソート済みとなるような置換ベクトル 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 ── 定数
Base.Sort.PartialQuickSort ── 型
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) # 行をソート
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) # 列をソート
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 は高次元へ自然に拡張されます。例えば 2x2x2 の配列 A に対する 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)
ベクトルがソートされているかどうかを判定します。どのような順序がソートされているとみなされるかは sort と同様にキーワード引数 lt, by, rev で指定されます。
例
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)
キーワード引数 by, lt, rev が規定する順序でソートされている a を受け取り、その順序による比較で x と等しいとみなされる a の要素の添え字を (二分探索で) 検索して返します。x と等しい a の要素が存在しなければ、挿入できる位置を示した空の区間を返します。
例
julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # 単一マッチ
3:3
julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # 複数マッチ
4:5
julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # マッチ無し、要素の間への挿入
3:2
julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # マッチ無し、末尾への挿入
7:6
julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # マッチ無し、先頭への挿入
1:0
Base.Sort.searchsortedfirst ── 関数
searchsortedfirst(a, x; by=<transform>, lt=<comparison>, rev=false)
キーワード引数 by, lt, rev が規定する順序でソートされている a を受け取り、その順序による比較で x 以上とみなされる最初の a の要素の添え字を (二分探索で) 検索して返します。x がa のどの要素よりも大きいときは length(a) + 1 を返します。
例
julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4)
3
julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5)
4
julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3)
3
julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 9)
7
julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0)
1
Base.Sort.searchsortedlast ── 関数
searchsortedlast(a, x; by=<transform>, lt=<comparison>, rev=false)
キーワード引数 by, lt, rev が規定する順序でソートされている a を受け取り、その順序による比較で x 以下とみなされる最後の a の要素の添え字を (二分探索で) 検索して返します。x がa のどの要素より小さいときは 0 を返します。
例
julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # 単一マッチ
3
julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # 複数マッチ
5
julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # マッチ無し、要素の間への挿入
2
julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # マッチ無し、末尾への挿入
6
julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # マッチ無し、先頭への挿入
0
Base.Sort.partialsort! ── 関数
partialsort!(v, k; by=<transform>, lt=<comparison>, rev=false)
キーワード引数 by, lt, rev が規定する順序を使って、ベクトル v を部分的にソートします。処理後の v では、添え字 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)
部分的ソートの前に v のコピーを作成するバージョンの partialsort! です。つまり partialsort! と同じ値を返しますが、v は改変されません。
Base.Sort.partialsortperm ── 関数
partialsortperm(v, k; by=<transform>, lt=<comparison>, rev=false)
v を完全にソートした配列における添え字 k の要素が v[I] となるような部分的な置換 I を返します。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 を受け取ります。ix は x と同じサイズである必要があり、v の添え字 (またはその置換) が格納されます。
添え字ベクトル ix が v の添え字 (または置換) で初期化されているなら、initialized を true に設定するべきです。
initialized が false (デフォルト値) だと、ix は v の添え字を含むよう初期化されます。
initialized が true にもかかわらず ix が v の添え字 (またはその置換) でないとき、partialsortperm! の振る舞いは未定義となります。
多くの場合で v の添え字は 1:length(v) です。ただし v が 1 始まりの添え字を使っていない (OffsetArray のような) 型の場合には、ix は同じ添え字 (またはその置換) を値に持つ同じ添え字の OffsetArray である必要があります。
関数が返った後の ix は、関数に渡された k に対して次の条件を満たすことが保証されています:
partialsortperm!(ix, v, k);
v[ix[k]] == partialsort(v, k)
返り値は k が整数なら ix の k 番目の要素であり、k が区間なら ix へのビューです。
例
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, initialized=true)
2-element view(::Array{Int64,1}, 2:3) with eltype Int64:
4
3
ソートアルゴリズム
Julia Base で利用可能なソートアルゴリズムは次の四つです:
InsertionSort は \(O(n^2)\) の安定なソートアルゴリズムです。非常に小さな n に対する効率が優れており、QuickSort は内部で InsertionSort を使用します。
QuickSort は \(O(n \log n)\) のソートアルゴリズムです。インプレースに実行でき非常に高速ですが、安定ではありません ──つまり、比較によって等しいとみなされる要素がソートされる最初の配列における順序と同じ順序で並ぶとは限りません。QuickSort は整数や浮動小数点数といった数値の配列に対するデフォルトのアルゴリズムです。
PartialQuickSort(k) は QuickSort と似ていますが、出力の配列は一部しかソートされません。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 が使われるのは、QuickSort の方が高速なことに加えて、数値型では不安定なソートと安定なソートを区別できないためです (ただし配列に対する改変を何らかの方法で記録するときは区別できます)。安定性の保証には無視できないコストがかかるので、もし安定性が不必要なら sort!(v, alg=QuickSort) などとして別のアルゴリズムを指定してください。
Julia がデフォルトのソートアルゴリズムを選択するメカニズムは Base.Sort.defalg 関数を通して実装されるので、特定の配列型に対してソート関数で使うデフォルトのソートアルゴリズムの登録が可能です。例えば sort.jl では、二つのメソッドが登録されています:
defalg(v::AbstractArray) = MergeSort
defalg(v::AbstractArray{<:Number}) = QuickSort
数値型の配列のように、ソートの安定性という概念が存在しない (比較で等しいとみなされる要素が区別できない) 配列型に対しては、デフォルトのアルゴリズムを不安定なものにすべきである可能性があります。