多重キーでのソート

多次元リストのソートってよく使う機能だと思うんですが、pythonのソートってよく考えて作ってあるなぁと関心しました。

例えば、次のような「生徒の成績リスト」があったとします。

# 配列の並び順 [名前],[国語],[算数]
a = [
   ['Tim',     55, 46 ],
   ['Jack',    55, 70 ],
   ['Mathhew', 23, 80 ],
]

そこで、リスト２番目の値である「国語」を、点数が高い順にソートするしたい場合は、以下の用になります。

>>> sorted(a, key=lambda x:x[1], reverse=True)
[['Tim', 55, 46], ['Jack', 55, 70], ['Mathhew', 23, 80]]

ちなみにcmpパラメータではなくkeyパラメータを上書きしたのは高速化のためです、念のため・・・

結果を見ると「Tim」と「Jack」は、国語は55点で同点ですが、算数は「Jack」の方が上です。でも、国語が同点だった場合は、算数の高い方が上にソートしたい場合がありますよね。
つまり、第１キー（国語）と第２キー（算数）による多重キーのソートです。

結論から言いますと、多重キーのソートは以下のとおりです。

>>> sorted(a, key=lambda x:(x[1],x[2]), reverse=True)
[['Jack', 55, 70], ['Tim', 55, 46], ['Mathhew', 23, 80]]

変わった箇所はkeyパラメータに、キーの優先順位順に要素を並べただけです、もの凄い簡単です。

なんでこうなるかと言いますと、標準の比較関数であるcmp()に秘密があります。
cmp(x,y)とは、x＞yだと正の数、x=yだと0、x＜yだと負の数を返すビルトイン関数です。

>>> cmp(0,1)
-1
>>> cmp(1,1)
0
>>> cmp(1,0)
1

このcmp()って、実は引数としてリストも受け付けてくれるんです。
リストの若い要素順に値を比較していき、決着が着くまで比較してくれます。
つまり、こういう事ですね。

cmp([第1キー,第2キー,...],[第1キー,第2キー,...])

ですからkeyパラメータを、キーの優先順位に要素が並んだリスト（タプル）を返す関数を与えれば、多重キーのソートができるのです。

でもデフォルトのkeyパラメータは、多重リストを与えられた場合はリストを返すようになっています。
つまり、キーの優先順位で並べられたリストを与えれば、特別な設定をしなくても、多重キーでのソートになっているのです。

>>> #[第1キー],[第2キー]で並んでいるリスト
... a = [
...     [1,4],
...     [1,3],
...     [1,2],
...     [2,2],
...     [2,1],
... ]
>>> 
>>> #特に設定をせずにソートすれば多重キーのソートとなる
... sorted(a)
[[1, 2], [1, 3], [1, 4], [2, 1], [2, 2]]

ほぉぉ〜、pythonってよくできていますね。
他の言語はどうなっているんでしょうねぇ？
少なくとも、PHPのarray_multisort()は面倒臭いという事だけは知っています(笑)

追記

第1キーは昇順、第2キーは降順にしたい場合があると思います。
そんな時は以下のように、キーに-をつければ降順になります（数値限定です）

>>> #[順位],[点数]
... a = [
...     [1,80],
...     [1,90],
...     [1,20],
...     [2,100],
... ]
>>> 
>>> #第2キーの点数を降順にしたい場合、-をつける
... sorted(a, key=lambda x:(x[0],-x[1]))
[[1, 90], [1, 80], [1, 20], [2, 100]]