Python: リストを並べ替えるsort, sorted

 # 前書き
最近は作るのに掛かりきりであまり学習に時間を割けていません。加えて「なんか微妙実装だなこれ。何か他に良い方法はないんだろうか。」と思うことも増えてきました。
そこでちょっと考えた結果、以前購入してチマチマ読んでいる[Effective Python](https://www.amazon.co.jp/Effective-Python-Specific-Software-Development/dp/0134853989)の復習をこちらで行い、知識を身に着けようという結論に至りました。
まとめはある程度短く、さっくりとしたものになると思いますので、より詳しく正しい知識を得たい方は原著の方を御覧ください。

 # Sortメソッド
今回の内容はEffective Pythonの"Item14: Sort by Complex Criteria Using the key Parameter"に基づく内容です。先にざっと内容を要約すると、
 - Sortメソッドを使うことで、リストの中身を並べ替えることができる
 - 内部では"<"や">"などの比較演算子が呼び出されているため、これが使えないオブジェクトだとTypeErrorを吐く
 - 自作のクラスなどでSortをしたいときは、自分で特殊メソッドを実装すればよい
 - しない、したくない、できないときは引数keyに関数を指定することで、複数の基準による並べ替えが可能となる
 
といった流れになります。

## リストには雑然としたデータが入ってくる傾向にある
大抵のチュートリアルやWebレッスン、学習書籍で取り上げられているので触ったことがない方はいらっしゃらないと思いますが、復習がてらここから始めます。

まず、Pythonにはリストと呼ばれる組み込みシーケンスが実装されています。シーケンスとは、
 - 最初の要素を0番目とし、以降1,2,3,4...という整数をインデックスとして各要素にアクセスできる
 - lenで長さを取得できる
 
の条件を満たす繰り返し可能なオブジェクトのことですね[^1]。

```python: list.py
lst = ["a", "b", "c"]
print(lst[0])
print(lst[1])
print("------------")
for e in lst:
    print(e)
print(f"length: {len(lst)}")
```
```: 出力
a
b
------------
a
b
c
length: 3
```
中身に格納するのは同じ型のものじゃなくてもokです。

```python: mixed_list.py
lst = [1, 5, 2, "x", "a", "b"]
print(lst[0])
print(lst[1])
print("------------")
for e in lst:
    print(e)
print(f"length: {len(lst)}")
```
```: 出力
1
5
------------
1
5
2
x
a
b
length: 6
```

余談ですが、文字列も組み込みシーケンスの一種です。

```python: string.py
phrase = "abcde燃費"
print(phrase[0])
print(phrase[1])
print("------------")
for l in phrase:
    print(l)
print(f"length: {len(phrase)}")
```
```: 出力
a
b
------------
a
b
c
d
e
燃
費
length: 7
```

で、このリストですが、ミュータブル(変更可能)なオブジェクトなので、中に入るデータの値や個数が予測しづらいときに、わりと雑に使うものだと個人的には思っています(アホほどデカくてメモリを食い切ってしまうようなケースは除き)。一定したデータなら同じ組み込みシーケンスかつイミュータブル(変更不能)なタプルを使う方が良いでしょうしね。

そうなると、リストを使う大体の場合において、中身が整然とした状態で並べられていることは期待できないわけです。

たとえば駄菓子屋さんで売上を記録したいとします。お客さんの数は一定ではなく、また一人ひとりのお客さんが買っていってくれる駄菓子の値段も個数も一定ではありません。すると、以下のようなリストが出てきます。

```python: messy_list.py
from random import randint

for _ in range(5):
    dagashi_price = 10 * randint(1, 20)
    number_of_today_customers = randint(1, 20) 
    order_quantities = [randint(1, 10) for _ in range(0, number_of_today_customers)]
    dagashi_prices = list(map(lambda x: x * dagashi_price, order_quantities))
    print(dagashi_prices)
```

```: 出力
[900, 90, 360, 810, 540, 270, 360, 450, 630, 270, 180]
[720, 720, 180, 630, 810, 90, 360, 270, 630, 360, 630, 810, 720, 810, 90, 720, 540, 360, 630, 540]
[1900, 1710, 1710, 1330, 190]
[1280, 480, 1600, 1120, 480, 960, 160, 1280, 640, 800, 960, 960, 960, 1440, 1440, 480, 320, 320]
[810, 540, 900, 180, 540, 810, 810, 900, 450, 630, 450, 180, 900, 630, 810]
```
リストの中身は個数も値もバラバラ。こうなると、特にデータを集計・出力する上で都合が悪いです。そのため、何らかの方法でデータを並べ替える必要が出てきます。

## sort,sortedメソッドを使うことで、リストの中身を並べ替えることができる
そんなときに使うのがsort、あるいはsortedメソッドになります。2つともリストの中身を並べ替えてくれるメソッドですが、ちょっとした違いがあります。ざっくりまとめると、

|  | 対象 | 元のリストを |
|:-:|:-:|:-:|
| sort | リストのみ | 置き換える  |
| sorted | 任意の繰り返し可能なオブジェクト  | 置き換えず新しいリストを返す  |

というものになります[^2]。

それぞれ実際に動かして確認してみます。

まずはsortから。

```python: list_sort.py
lst = [2, 5, 1, 3, 7]
print(lst.sort())
print(lst)
lst2 = ["a", "c", "b", "A"]
print(lst2.sort())
print(lst2)
```

```: 出力
None
[1, 2, 3, 5, 7]
None
['A', 'a', 'b', 'c']
```

いずれも元のリストを置き換えており、sort自体の返り値はNoneであることがわかります。

次にsorted。

```python: list_sorted.py
lst = [2, 5, 1, 3, 7]
print(sorted(lst))
print(lst)
lst2 = ["a", "c", "b", "A"]
print(sorted(lst2))
print(lst2)
```

```: 出力
[1, 2, 3, 5, 7]
[2, 5, 1, 3, 7]
['A', 'a', 'b', 'c']
['a', 'c', 'b', 'A']
```

こちらはsortと違って元のリストを置き換えず、新しいリストを返しています。

## 比較が出来なければ並べ替えようがない
さて、ではここで並べ替えの基準ですが、基本的に比較演算子の定義に則って返されています。

```python: comparison_operator.py
lst1 = [3, 1]
assert 3 > 1
print(sorted(lst1))
lst2 = ["c", "a"]
assert "c" > "a"
lst2.sort()
print(lst2)
```

```: 出力
[1, 3]
['a', 'c']
```

つまり、並べ替えの基準が無いオブジェクトでは、当然sort,sortedのいずれも用いることができません。

```python: dagashi_daisuki.py
class Dagashi:
    def __init__(self, name, price):
        self._name = name
        self._price = price


dagashi1 = Dagashi(name="タラタラしてんじゃね～よ", price=50)
dagashi2 = Dagashi(name="ベビースターラーメンミニ", price=30)
dagashi3 = Dagashi(name="キャベツ太郎", price=20)
dagashi_list = [dagashi1, dagashi2, dagashi3]
sorted(dagashi_list)
```

```: 出力
TypeError: '<' not supported between instances of 'Dagashi' and 'Dagashi'
```

"駄菓子のインスタンス同士の比較がサポートされてないぞ"というよく見る感じのタイプエラーです。これを解決するための方法はいくつかあります。

### NamedTupleの採用
たとえば、中で大したことをやる予定がない。単に格納のために必要なクラスなのであれば、NamedTupleを継承するとよいでしょう。

```python: dagashi_with_named_tuple.py
from typing import NamedTuple

class Dagashi(NamedTuple):
    name : str
    price : int

dagashi1 = Dagashi(name="タラタラしてんじゃね～よ", price=50)
dagashi2 = Dagashi(name="ベビースターラーメンミニ", price=30)
dagashi3 = Dagashi(name="キャベツ太郎", price=20)
dagashi_list = [dagashi1, dagashi2, dagashi3]
sorted(dagashi_list)
```

```: 出力
[Dagashi(name='キャベツ太郎', price=20),
 Dagashi(name='タラタラしてんじゃね～よ', price=50),
 Dagashi(name='ベビースターラーメンミニ', price=30)]
```

またこれも余談なのですが、NamedTupleを継承したクラスの並べ替えは、

```python: reversed_definition_dagashi_with_named_tuple.py
from typing import NamedTuple

class Dagashi(NamedTuple):
    price: int
    name: str

dagashi1 = Dagashi(name="タラタラしてんじゃね～よ", price=50)
dagashi2 = Dagashi(name="ベビースターラーメンミニ", price=30)
dagashi3 = Dagashi(name="キャベツ太郎", price=20)
dagashi4 = Dagashi(name="パリッとおいしい!カレーせん", price=20)
dagashi_list = [dagashi1, dagashi2, dagashi3, dagashi4]
sorted(dagashi_list)
```

```: 出力
[Dagashi(price=20, name='キャベツ太郎'),
 Dagashi(price=20, name='パリッとおいしい!カレーせん'),
 Dagashi(price=30, name='ベビースターラーメンミニ'),
 Dagashi(price=50, name='タラタラしてんじゃね～よ')]
```

ご覧の通り、定義された順番が先の属性が優先的に判定に利用されます。同一順位の場合は次の属性を参照といった流れです。

このやり方の良いところはシンプルなところです。NamedTupleで属性の型をさくっと指定してあげれば、あとは勝手に並べ替えてくれます。

### 特殊メソッドの実装
他には、特殊メソッドを実装するという手もあるでしょう。比較演算子は内部の特殊メソッドを呼び出すので、対応する特殊メソッドを実装しておけば並べ替えができるようになります。特殊メソッドについては以下のサイト様を参考にしています[^3]。

```python: dagashi_with_special_method.py
class Dagashi:
    def __init__(self, name, price):
        self._name = name
        self._price = price
    
    def __repr__(self):
        return f"Dagashi('{self.name}', {self.price}円)"
        
    @property
    def name(self):
        return self._name
    @property
    def price(self):
        return self._price
        
    def __eq__(self, other):
        if not isinstance(other, Dagashi):
            return NotImplemented
        return self.price == other.price    

    def __lt__(self, other):
        if not isinstance(other, Dagashi):
            return NotImplemented
        return self.price < other.price

    def __ne__(self, other):
        return not self.__eq__(other)

    def __le__(self, other):
        return self.__lt__(other) or self.__eq__(other)

    def __gt__(self, other):
        return not self.__le__(other)

    def __ge__(self, other):
        return not self.__lt__(other)

dagashi1 = Dagashi(name="タラタラしてんじゃね～よ", price=50)
dagashi2 = Dagashi(name="ベビースターラーメンミニ", price=30)
dagashi3 = Dagashi(name="キャベツ太郎", price=20)
dagashi4 = Dagashi(name="パリッとおいしい!カレーせん", price=20)
dagashi_list = [dagashi1, dagashi2, dagashi3, dagashi4]
print(sorted(dagashi_list))
```
```: 出力
[Dagashi('キャベツ太郎', 20円),
 Dagashi('パリッとおいしい!カレーせん', 20円),
 Dagashi('ベビースターラーメンミニ', 30円),
 Dagashi('タラタラしてんじゃね～よ', 50円)]
```

このやり方の良いところは、自分が思うように挙動をカスタマイズできるところです。代わりにクラスが重くなりがちで、実装するのは大変です。
自分も以前に算術演算を含む標準演算子が入った自作クラスを実装しようとしたことがありますが、「よくよく考えると、他のもっと簡単なやり方でよくない？」と思って結局切り替えたことがあります。労力に見合うだけの挙動を必要としているのか？を見極める必要がある難しい方法だと思います。

### keyパラメータの利用
こちらがまさにEffective Pythonで紹介されているものになります。sort,sortedはともにkeyをパラメータに設定できるので、それを使って希望する並び方を実現します。

keyパラメータは単一の引数を受け取り、ソートに利用できる値を返す関数でなければなりません[^2]。NamedTupleは自動的に比較に用いる属性を出してくれましたが、こちらでは自分で指定することになります。

関数をそのまま定義してもよいのですが、結局属性を持ってきてくれればそれでよいので、無名関数がよく使われています。

```python: dagashi_with_key_parameter.py
from pprint import pprint


class Dagashi:
    
    def __init__(self, name, price):
        self._name = name
        self._price = price
    
    def __repr__(self):
        return f"Dagashi('{self._name}', {self._price})"
    
    @property
    def name(self):
        return self._name
    
    @property
    def price(self):
        return self._price

dagashi1 = Dagashi(name="タラタラしてんじゃね～よ", price=50)
dagashi2 = Dagashi(name="ベビースターラーメンミニ", price=30)
dagashi3 = Dagashi(name="キャベツ太郎", price=20)
dagashi4 = Dagashi(name="パリッとおいしい!カレーせん", price=20)

dagashi_list1 = [dagashi1, dagashi2, dagashi3, dagashi4]
sorted_list = sorted(dagashi_list1, key=lambda dagashi: dagashi.name)
pprint(sorted_list)

print("-----------------------")

dagashi_list2 = [dagashi1, dagashi2, dagashi3, dagashi4]
dagashi_list2.sort(key=lambda dagashi: dagashi.name)
pprint(dagashi_list2)
```

```: 出力
[Dagashi('キャベツ太郎', 20),
 Dagashi('タラタラしてんじゃね～よ', 50),
 Dagashi('パリッとおいしい!カレーせん', 20),
 Dagashi('ベビースターラーメンミニ', 30)]
-----------------------
[Dagashi('キャベツ太郎', 20),
 Dagashi('タラタラしてんじゃね～よ', 50),
 Dagashi('パリッとおいしい!カレーせん', 20),
 Dagashi('ベビースターラーメンミニ', 30)]
```

もちろんNamedTupleと併用することも可能です。単に属性の呼び出しを自分で実装するか、NamedTupleにお任せするかの違いに過ぎないからです。

```python: dagashi_with_named_tuple_and_key_parameter.py
from pprint import pprint
from typing import NamedTuple

class Dagashi(NamedTuple):
    name: str
    price: int

dagashi1 = Dagashi(name="タラタラしてんじゃね～よ", price=50)
dagashi2 = Dagashi(name="ベビースターラーメンミニ", price=30)
dagashi3 = Dagashi(name="キャベツ太郎", price=20)
dagashi4 = Dagashi(name="パリッとおいしい!カレーせん", price=20)

dagashi_list1 = [dagashi1, dagashi2, dagashi3, dagashi4]
sorted_list = sorted(dagashi_list1, key=lambda dagashi: dagashi.name)
pprint(sorted_list)

print("-----------------------")

dagashi_list2 = [dagashi1, dagashi2, dagashi3, dagashi4]
dagashi_list2.sort(key=lambda dagashi: dagashi.name)
pprint(dagashi_list2)
```

```: 出力
[Dagashi(name='キャベツ太郎', price=20),
 Dagashi(name='タラタラしてんじゃね～よ', price=50),
 Dagashi(name='パリッとおいしい!カレーせん', price=20),
 Dagashi(name='ベビースターラーメンミニ', price=30)]
-----------------------
[Dagashi(name='キャベツ太郎', price=20),
 Dagashi(name='タラタラしてんじゃね～よ', price=50),
 Dagashi(name='パリッとおいしい!カレーせん', price=20),
 Dagashi(name='ベビースターラーメンミニ', price=30)]
```

ここまで名前を使って並べ替えていましたが、値段を使って並べ替えることも当然可能です。また、sort, sortedにreverse=Trueを指定すれば降順に並べ替えてくれます。

```python: sorted_by_reversed_price.py
from pprint import pprint
from typing import NamedTuple

class Dagashi(NamedTuple):

    name: str
    price: int

dagashi1 = Dagashi(name="タラタラしてんじゃね～よ", price=50)
dagashi2 = Dagashi(name="ベビースターラーメンミニ", price=30)
dagashi3 = Dagashi(name="キャベツ太郎", price=20)
dagashi4 = Dagashi(name="パリッとおいしい!カレーせん", price=20)

dagashi_list1 = [dagashi1, dagashi2, dagashi3, dagashi4]
sorted_list = sorted(dagashi_list1, key=lambda dagashi: dagashi.price, reverse=True)
pprint(sorted_list)

print("-----------------------")

dagashi_list2 = [dagashi1, dagashi2, dagashi3, dagashi4]
dagashi_list2.sort(key=lambda dagashi: dagashi.price, reverse=True)
pprint(dagashi_list2)
```
```: 出力
[Dagashi(name='タラタラしてんじゃね～よ', price=50),
 Dagashi(name='ベビースターラーメンミニ', price=30),
 Dagashi(name='キャベツ太郎', price=20),
 Dagashi(name='パリッとおいしい!カレーせん', price=20)]
-----------------------
[Dagashi(name='タラタラしてんじゃね～よ', price=50),
 Dagashi(name='ベビースターラーメンミニ', price=30),
 Dagashi(name='キャベツ太郎', price=20),
 Dagashi(name='パリッとおいしい!カレーせん', price=20)]
```

## 複数の基準を使って並べ替える
Pythonが提供するsort, sortedはstableであり、元の順番を保存することが保証されています[^2]。そのため、ひとつの並べ替え基準で同じ順番だと判定されるものは、元々の順番のまま出力されます。

上の例でも"キャベツ太郎"と"パリッとおいしい!カレーせん"は値段が同じなので、値段で並べ替えたときの並び順は常に入力順と同じ、つまり"キャベツ太郎"が先になっています。

この性質を利用すると、値段で並べ替えたあと、さらに名前で並べ替えるといった複数の基準での並べ替えもできるようになります。ただし複数回の並べ替えには一点だけ気をつけるべき点があって、それは優先したい基準を使った並べ替えほど後に書く必要がある、ということです。

以下、簡単なクラスを再定義して話を進めていきます。

```python: sorted_with_number_and_alphabet.py
from random import shuffle
from pprint import pprint
from typing import NamedTuple

class NumAndAlphabet(NamedTuple):
    number: int
    alphabet: str

naa1 = NumAndAlphabet(number=5, alphabet="A")
naa2 = NumAndAlphabet(number=5, alphabet="B")
naa3 = NumAndAlphabet(number=2, alphabet="X")
naa4 = NumAndAlphabet(number=4, alphabet="Y")
naa_list = [naa1, naa2, naa3, naa4]
shuffle(naa_list)
print("---------before_sorted-----------")
pprint(naa_list)

sorted_by_number = sorted(naa_list, key=lambda x: x.number)
sorted_by_alphabet_after_number = sorted(sorted_by_number, key=lambda x: x.alphabet)
print("---------number->alphabet---------")
pprint(sorted_by_alphabet_after_number)

sorted_by_alphabet = sorted(naa_list, key=lambda x: x.alphabet)
sorted_by_number_after_alphabet = sorted(sorted_by_alphabet, key=lambda x: x.number)
print("---------alphabet->number----------")
pprint(sorted_by_number_after_alphabet)
```
```: 出力
---------before_sorted-----------
[NumAndAlphabet(number=2, alphabet='X'),
 NumAndAlphabet(number=5, alphabet='B'),
 NumAndAlphabet(number=5, alphabet='A'),
 NumAndAlphabet(number=4, alphabet='Y')]
---------number->alphabet---------
[NumAndAlphabet(number=5, alphabet='A'),
 NumAndAlphabet(number=5, alphabet='B'),
 NumAndAlphabet(number=2, alphabet='X'),
 NumAndAlphabet(number=4, alphabet='Y')]
---------alphabet->number----------
[NumAndAlphabet(number=2, alphabet='X'),
 NumAndAlphabet(number=4, alphabet='Y'),
 NumAndAlphabet(number=5, alphabet='A'),
 NumAndAlphabet(number=5, alphabet='B')]
```

数→アルファベットで並べ替えたときは、アルファベット→数で並べ替えが行われています。一方で、アルファベット→数で並べ替えたときは、数→アルファベットで並べ替えが行われています。つまり、後のsortedで基準に用いた方が並べ替えの優先度が高くなります。これはsortedではなく、sortで並べ替えたときにも同じ挙動を示します。

```python: sort_with_number_and_alphabet.py
from random import shuffle
from pprint import pprint
from typing import NamedTuple

class NumAndAlphabet(NamedTuple):
    number: int
    alphabet: str

naa1 = NumAndAlphabet(number=5, alphabet="A")
naa2 = NumAndAlphabet(number=5, alphabet="B")
naa3 = NumAndAlphabet(number=2, alphabet="X")
naa4 = NumAndAlphabet(number=4, alphabet="Y")
naa_list1 = [naa1, naa2, naa3, naa4]
shuffle(naa_list1)
print("---------before_sorted-----------")
pprint(naa_list1)

naa_list1.sort(key=lambda x: x.number)
naa_list1.sort(key=lambda x: x.alphabet)
print("----------number->alphabet---------")
pprint(naa_list1)

naa_list2 = [naa1, naa2, naa3, naa4]
shuffle(naa_list2)
naa_list2.sort(key=lambda x: x.alphabet)
naa_list2.sort(key=lambda x: x.number)
print("---------alphabet->number----------")
pprint(naa_list2)
```

```: 出力
---------before_sorted-----------
[NumAndAlphabet(number=4, alphabet='Y'),
 NumAndAlphabet(number=5, alphabet='A'),
 NumAndAlphabet(number=5, alphabet='B'),
 NumAndAlphabet(number=2, alphabet='X')]
----------number->alphabet---------
[NumAndAlphabet(number=5, alphabet='A'),
 NumAndAlphabet(number=5, alphabet='B'),
 NumAndAlphabet(number=2, alphabet='X'),
 NumAndAlphabet(number=4, alphabet='Y')]
---------alphabet->number----------
[NumAndAlphabet(number=2, alphabet='X'),
 NumAndAlphabet(number=4, alphabet='Y'),
 NumAndAlphabet(number=5, alphabet='A'),
 NumAndAlphabet(number=5, alphabet='B')]
```

# まとめ
これまで自分の中でフワっとしていたsort,sortedの挙動についてまとめてみました。誤っている点があったり、不明な点があったりする場合はコメント欄にてご指摘いただけると助かります。

今回は以上です。次回もよろしくお願いします。

# 参考サイト, 書籍
 - Slatkin Brett "Effective Python: 90 Specific Ways to Write Better Python (Effective Software Development Series) (English Edition) 2nd 版, Kindle版" ‎ Addison-Wesley Professional 2019/10/25 p.52 ~ p.57
 [^1]: [用語集-シーケンス](https://docs.python.org/ja/3/glossary.html#term-sequence)
 [^2]: [ソート HOW TO](https://docs.python.org/ja/3/howto/sorting.html)
[^3]: [[Python] 独自クラスで比較演算ができるようにする](https://www.yoheim.net/blog.php?q=20171002)