Pythonで独自ソートの実装

Pythonのリストにあるsortメソッドは、自然な順序でソートしてくれるものであるが、そうではないソートを行いたいときがある。そのようなソートを行うには、sortメソッドに比較のための関数を渡してやればよい。まずは、比較によく用いられる関数を見てみよう。

>>> help(cmp)
Help on built-in function cmp in module __builtin__:

cmp(...)
    cmp(x, y) -> integer
    
    Return negative if xy.
>>> help(list.sort)
Help on method_descriptor:

sort(...)
    L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;
    cmp(x, y) -> -1, 0, 1
>>> help(sorted)
Help on built-in function sorted in module __builtin__:

sorted(...)
    sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list

cmp関数は2つの引数を評価した結果を返すというものである。第1引数が第2引数より小さければ負、同じなら0、大きければ正の値を返すようになっている。

リストのsortメソッドには3つの引数を与えることができる。cmpは比較のための関数である。keyはソートの基準となる対象を指定するものである。例えば文字列のソートで2文字目以降でソートしたいという場合にはlambda x:x[1:]とすることになる。この場合、xはソート対象となるオブジェクトに相当する。reverseは昇順・降順を指定するものである。デフォルトでは昇順に並べることになる。

sortedは反復可能なオブジェクトであれば、ソートすることができる。例えば、辞書のvalueで辞書をソートするときにはこれを利用するとよい。cmpなどのオプションはlist.sortと同様の意味を持つ。

これを踏まえて、以前Javaでも書いた文字列の長さ順にソートするということを行ってみる。なお、sortメソッドはstable sort(安定なソート)なので、同じ値(=文字列の長さが同じ)が複数ある場合は、先に出てきたものが先に並べられるようになっている。

# -*- encoding: utf-8 -*-

def cmp_len(s1, s2):
    return cmp(len(s1), len(s2)) # 文字列の長さで比較するための関数

langs = ["Python", "LISP", "Haskell", "C", "Java"]

langs.sort(cmp=cmp_len, reverse=True)
print langs #徐々に文字列の長さが短くなっていくリストになる

dic = {"NumPy":"numerical analysis",
       "sphinx":"documentation generator",
       "django":"web"}

sdic = sorted(dic.items(), cmp=cmp_len, key=lambda x:x[1])
# 説明文が短い順に並べ替えられている
print sdic

表示される結果は次の通り。

['Haskell', 'Python', 'LISP', 'Java', 'C']
[('django', 'web'), ('NumPy', 'numerical analysis'), ('sphinx', 'documentation generator')]