昇順や降順に並べ替えするソート関数としてよく使われるnp.sortとnp.argsortを紹介します。

ソートはあらゆる場面で使用する基本アルゴリズムなので、この記事を通して使い方を確認しておきましょう。

np.sort

sort関数は配列の要素を昇順にソートしたものを返しますが、一方でargsort関数はその入れ替えられた配列のインデックスを返します。

まずは、APIドキュメントを確認してみます。

numpy.sort(a, axis=-1, kind=None, order=None)

params:

パラメータ名 型 概要
a array_like
(配列に相当するもの)		 ソートしたい配列を指定します。
axis int もしくは
None		 (省略可能)初期値-1
ソートを行う軸方向を指定します。デフォルトはで最も次元の低いところに沿ってソートします。
kind ‘quicksort’, ‘mergesort’
‘stable’, ‘heapsort’のいずれか		 デフォルトで使用されるソートアルゴリズムはquicksortになります。’stable’と’mergesort’はどちらもTimSortかRadix Sortになり、実際の実装はデータ型によります。
order string
もしくは
stringのリスト		 (省略可能)初期値None
aがフィールドの定義されている配列であったとき、どのフィールドで要素をソートするかを指定します。

returns:

要素がソートされた配列が返されます。

引数として指定できるものは4つあります。第一引数はソートしたい配列を指定します。第二引数であるaxisは、どの軸方向に要素をソートをするかを指定します。デフォルトは最も次元の低いaxis=-1になります。第三、第四引数となっているkindとorderは見慣れないものだと思います。kindはソートする際に用いるアルゴリズムを指定し、orderはどのフィールドを基にソートするかを指定します。

ソートの種類については、後述します。np.sortは、以下のように使用します。

In [1]: import numpy as np

In [2]: a = np.random.randint(0, 100, size = 20)

In [3]: a
Out[3]:
array([29, 54,  0,  8, 71,  6, 69,  9, 96, 52, 91, 86, 28, 49, 99, 37, 32,
       82,  0, 65])

In [4]: np.sort(a)
Out[4]:
array([ 0,  0,  6,  8,  9, 28, 29, 32, 37, 49, 52, 54, 65, 69, 71, 82, 86,
       91, 96, 99])

np.argsort

np.argsortは、ソート結果の配列のインデックスを返します。APIドキュメントは以下の通りです。

numpy.argsort(a, axis=-1, kind=None, order=None)

params:

パラメータ名 型 概要
a array_like
(配列に相当するもの)		 ソートしたい配列を指定します。
axis int もしくは
None		 (省略可能)初期値-1
ソートを行う軸方向を指定します。デフォルトはで最も次元の低いところに沿ってソートします。
kind ‘quicksort’, ‘mergesort’
‘heapsort’のいずれか		 (省略可能)初期値’quicksort’
データの並べ替え方のアルゴリズムを指定します。
order string
もしくは
stringのリスト		 (省略可能)初期値None
aがフィールドの定義されている配列であったとき、どのフィールドで要素をソートするかを指定します。

returns:

ソートされた軸方向内における、配列の要素の元の配列でのインデックスを要素とする配列が返されます。

このように2つのAPIドキュメントを見比べてみると、最後の出力のされ方が異なるだけで引数などは全て一緒となっています。

そのため、まずは2つの関数での共通の性質で、ポイントだと考えられる部分を解説していきたいと思います。

np.argsortは、以下のように使います。

In [1]: import numpy as np

In [2]: a = np.array([1, 3, 2])

In [3]: np.argsort(a)
Out[3]: array([0, 2, 1])

np.argsortを使用すると、ソート後のインデックスが出力されます。

kindパラメータで指定可能なquicksort, mergesort, heapsortについて

np.sort、np.argsortで指定することのできるアルゴリズムはquicksort、mergesort、heapsortの3種類あります。

quicksort

quicksortは、あるしきい値を元に要素を前後で交換、分割を繰り返しながらソートしていく方法です。非常に実用的で、ソートする平均処理時間も一番短いとされています。計算量の平均オーダーは一様分布な配列を整列する場合であれば、O(N\log{N}) となります。

下のアニメーションはquicksortが行われている様子です。スタートボタンを押すと、アルゴリズムの動作の様子が分かります。

stable

stable(安定な並び替え）は要素中に同一の値が複数ある場合に、並び替え前の順序関係が維持されるような並び替え方法になります。NumPyでの以前の実装はmergesortでしたが、現在はより高速なTim Sortや基数ソートが実装されています。 quicksortは不安定な並び替えであり、最悪計算量が大きくなってしまうデメリットがあるため、そのような場合にこちらを選ぶと効果的でしょう。

Tim Sortはマージソートと挿入ソートの派生形のため、ここではよりシンプルなstableソートであるmergesortのアルゴリズムについて解説します。

mergesortは、配列を分割してからまた再び分割したものを結合していくという手法によってソートするアルゴリズムです。

このアルゴリズムは、配列の並べられ方が一様でなくとも安定した処理時間でソートすることが可能です。計算量のオーダーはO(N\log{N})\\\\ となっています。

heapsort

heapsortは、配列の要素を一旦ヒープ木に格納してから、最大の要素（もしくは最小）の要素を順に抜き出していく手法です。こちらも、計算量のオーダーはO(N\log{N}) となっています。

それぞれ具体的にどのようなことが起こっているのかは、以下のサイトを参考にしてください。

クイックソート
マージソート
ヒープソート

どのアルゴリズムを使うべきかについては、基本的にはquicksortで良いと思います。ソート済み配列に適用する場合など、最悪計算量が遅くなる場合があるので、そういった場合にはmergesortやheapsortを検討しましょう。

手元のMacbookで実際に計算時間を比較してみます。それぞれのアルゴリズムで長さnの配列をソートする時間を1000回分記録し、その平均と最大を返します。

import numpy as np
def sort_comparison(n):
     result1 = np.empty(1000)
     for i in range(1000):
         a = np.random.rand(n)
         time1 = time.time()
         b = np.sort(a,kind='quicksort')
         time1 = time.time()- time1
         result1[i] = time1
     result2 = np.empty(1000)
     for i in range(1000):
         a = np.random.rand(n)
         time1 = time.time()
         b = np.sort(a, kind='mergesort')
         time1 = time.time()-time1
         result2[i] = time1
     result3 = np.empty(1000)
     for i in range(1000):
         a = np.random.rand(n)
         time1 = time.time()
         b = np.sort(a,kind='heapsort')
         time1 = time.time() - time1
         result3[i] = time1
     print ("quicksort average {}, max {}".format(np.average(result1), np.max(result1)))
     print ("mergesort average {}, max  {}".format(np.average(result2), np. max(result2)))
     print ("heapsort average {}, max {}".format(np.average(result3), np.max(result3)))

以上のようなコードをtest.pyに保存して、実行すると、以下のようになります。

In [1]: from test import *

In [2]: sort_comparison(100)
quicksort average 1.589488983154297e-05, max 0.0038650035858154297
mergesort average 1.3976812362670898e-05, max 0.0047800540924072266
heapsort average 1.337885856628418e-05, max 5.2928924560546875e-05

In [3]: sort_comparison(1000)
quicksort average 6.856584548950196e-05, max 0.0009419918060302734
mergesort average 6.935572624206543e-05, max 0.0001399517059326172
heapsort average 8.155369758605957e-05, max 0.00017404556274414062

In [4]: sort_comparison(10000)
quicksort average 0.0006785655021667481, max 0.0014460086822509766
mergesort average 0.0007824172973632812, max 0.0016520023345947266
heapsort average 0.0010491831302642822, max 0.002501964569091797

In [5]: sort_comparison(100000)
quicksort average 0.008679111242294311, max 0.022437095642089844
mergesort average 0.010156460285186767, max 0.019762039184570312
heapsort average 0.01377375888824463, max 0.024383068084716797

今回整列をするために用意したのがランダム配列だったので、安定的にquicksortが高速な結果になりました。

引数orderについて

例えば、以下のような配列を作ります。人名と個人番号(ID)、テストでの点数をまとめたものです。

In [2]: values = [('Alice', 25, 9.7), ('Bob', 12, 7.6), ('Catherine', 1, 8.6), ('David', 10, 7.6)]

In [3]: dtype = [('name', 'S10'),('ID', int), ('score', float)]

In [4]: a = np.array(values, dtype=dtype)

この配列で点数について昇順にしたい場合は、orderの出番です。どのフィールドでソートしたいかをorderで指定します。

In [5]: np.sort(a, order= 'score')
Out[5]:
array([(b'Bob', 12,  7.6), (b'David', 10,  7.6), (b'Catherine',  1,  8.6),
       (b'Alice', 25,  9.7)],
      dtype=[('name', 'S10'), ('ID', '<i8'), ('score', '<f8')])

In [6]: np.argsort(a, order = 'score') # もちろん、argsortでもできる。
Out[6]: array([1, 3, 2, 0])

同じ点数の人が二人以上出たら、その中でどうソートするかも指定できます。今回は、IDを元に並べ替えて見ましょう。

In [7]: np.sort(a, order = ['score', 'ID'])
Out[7]:
array([(b'David', 10,  7.6), (b'Bob', 12,  7.6), (b'Catherine',  1,  8.6),
       (b'Alice', 25,  9.7)],
      dtype=[('name', 'S10'), ('ID', '<i8'), ('score', '<f8')])

In [8]: np.argsort(a, order = ['score', 'ID'])
Out[8]: array([3, 1, 2, 0])

詳細な使用例

もう少し細かくパラメータを指定してみましょう。axisで、ソートする軸方向を指定してみます。

In [3]: b = np.random.randint(0, 100, size=20).reshape(4,5)

In [4]: b # bを二次元配列にした。
Out[4]:
array([[44, 27, 50, 58, 47],
       [57, 81, 87, 77, 90],
       [82, 29, 82, 91, 90],
       [10, 97, 62, 34, 59]])

In [5]: np.sort(b) # axisを指定しないと列方向の中でソートをする。  
Out[5]:
array([[27, 44, 47, 50, 58],
       [57, 77, 81, 87, 90],
       [29, 82, 82, 90, 91],
       [10, 34, 59, 62, 97]])

In [6]: np.argsort(b) # argsortも同様。表示されるインデックスが列番号だけになっている。  
Out[6]:
array([[1, 0, 4, 2, 3],
       [0, 3, 1, 2, 4],
       [1, 0, 2, 4, 3],
       [0, 3, 4, 2, 1]])

In [7]: np.sort(b, axis=0) # 次はaxisを指定する。
Out[7]:
array([[10, 27, 50, 34, 47],
       [44, 29, 62, 58, 59],
       [57, 81, 82, 77, 90],
       [82, 97, 87, 91, 90]])

In [8]: np.argsort(b, axis=0)
Out[8]:
array([[3, 0, 0, 3, 0],
       [0, 2, 3, 0, 3],
       [1, 1, 2, 1, 1],
       [2, 3, 1, 2, 2]])

In [9]: c = np.random.randint(0, 100, size = (2, 4, 5))

In [10]: c
Out[10]:
array([[[47, 99, 12,  5,  2],
        [61, 15, 36, 41, 68],
        [21, 83, 92, 61, 63],
        [22, 63, 59, 72, 61]],

       [[25, 48, 99, 25,  5],
        [35, 35, 32, 84, 36],
        [67, 93, 56, 32, 99],
        [31, 90, 57, 43, 73]]])

In [11]: np.sort(c, axis = 0) # 三次元配列でaxis=0方向にソート。
Out[11]:
array([[[25, 48, 12,  5,  2],
        [35, 15, 32, 41, 36],
        [21, 83, 56, 32, 63],
        [22, 63, 57, 43, 61]],

       [[47, 99, 99, 25,  5],
        [61, 35, 36, 84, 68],
        [67, 93, 92, 61, 99],
        [31, 90, 59, 72, 73]]])

In [12]: np.argsort(c, axis=0) # ならべかえる要素が2つずつなのでインデックスは0か1。
Out[12]:
array([[[1, 1, 0, 0, 0],
        [1, 0, 1, 0, 1],
        [0, 0, 1, 1, 0],
        [0, 0, 1, 1, 0]],

       [[0, 0, 1, 1, 1],
        [0, 1, 0, 1, 0],
        [1, 1, 0, 0, 1],
        [1, 1, 0, 0, 1]]])

np.sortとnp.ndarray.sort

np.sortと似たような関数としてnp.ndarray.sortというものがあります。

これは、配列のコピーをソートするのではなく、配列自身をソートする関数となっています。APIドキュメントは以下の通りです。

ndarray.sort(axis=-1, kind=’quicksort’, order = None)

params:

パラメータ名 型 概要
axis int もしくは
None		 (省略可能)初期値-1
ソートを行う軸方向を指定します。デフォルトはで最も次元の低いところに沿ってソートします。
kind ‘quicksort’, ‘mergesort’
‘heapsort’のいずれか		 (省略可能)初期値’quicksort’
データの並べ替え方のアルゴリズムを指定します。
order string
もしくは
stringのリスト		 (省略可能)初期値None
aがフィールドの定義されている配列であったとき、どのフィールドで要素をソートするかを指定します。

配列そのものをソートするだけなので、特に何も値を返すことはありません。使い方自体はnp.sortと全く同じです。

実際のコードを見ていきましょう。

In [116]: a = np.random.randint(0, 100, 20) # 乱数を20個生成。

In [117]: a
Out[117]:
array([69, 89, 38, 99, 29, 72, 70, 51, 42, 49, 20, 21, 16, 37, 66, 51, 59,
       92, 26, 42])

In [118]: np.sort(a) # ソートされた配列が返される。　
Out[118]:
array([16, 20, 21, 26, 29, 37, 38, 42, 42, 49, 51, 51, 59, 66, 69, 70, 72,
       89, 92, 99])

In [119]: a # aの中身は変化ない。
Out[119]:
array([69, 89, 38, 99, 29, 72, 70, 51, 42, 49, 20, 21, 16, 37, 66, 51, 59,
       92, 26, 42])

In [120]: a.sort() # ndarray.sortを使うと、aの中身がソートされる。

In [121]: a
Out[121]:
array([16, 20, 21, 26, 29, 37, 38, 42, 42, 49, 51, 51, 59, 66, 69, 70, 72,
       89, 92, 99])