初めまして、大学院生をしているhinoと申します。
今回はAtCoderの過去問を解いていて、多次元配列の昇順と降順が混ざったソートの方法が知りたくなり、まとめました。
解いていた問題
問題概要
市名とレストランの点数が与えられ、次のような順でレストランを紹介します。
- 市名は辞書順で早い方から紹介
- 同じ市に複数のレストランがある際には点数の高い方から紹介
この問題は市名を昇順ソートし、点数を降順ソートすることで目的の並び方にすることができるのですが、多次元配列の昇順と降順が混在するソートになってしまうためその実装について考えてみました。
例として問題のテストケース1を考えてみます。
data = [['khabarovsk', 20], ['moscow', 10], ['kazan', 50], ['kazan', 35], ['moscow', 60], ['khabarovsk', 40]]
同時に昇順・降順ソートは指定できないので、別々に行ってみます。
#市名について昇順ソート
data = sorted(data, key=lambda x: x[0])
#点数について降順ソート
data = sorted(data, key=lambda x: x[1], reverse=True)
print(data)
> [['moscow', 60], ['kazan', 50], ['khabarovsk', 40], ['kazan', 35], ['khabarovsk', 20], ['moscow', 10]]
このように順序が乱れるためうまくいきません。
そこで調べてみたところ、Pythonのリファレンスに次のような記述がありました。
ソートの安定性と複合的なソート
ソートは、 安定 (stable) であることが保証されています。これはレコードの中に同じキーがある場合、元々の順序が維持されるということを意味します.......
この素晴しい性質によって複数のソートを段階的に組み合わせることができます。例えば、学生データを grade の降順にソートし、さらに age の昇順にソートしたい場合 には、まず age でソートし、次に grade でもう一度ソートします:
どうも、降順を優先すると良さそうとのことですので試してみましょう。
data = sorted(data, key=lambda x: x[1], reverse=True)
data = sorted(data, key=lambda x: x[0])
print(data)
> [['kazan', 50], ['kazan', 35], ['khabarovsk', 40], ['khabarovsk', 20], ['moscow', 60], ['moscow', 10]]
目的通りのソートができました！！
...ただ、１行で書きたいなと思うんですよね...。
そこで思いついたのが 正数を降順ソートにしたいなら負数を昇順ソートすればよいということです。
data = sorted(data, key=lambda x: (x[0], -x[1]))
print(data)
> [['kazan', 50], ['kazan', 35], ['khabarovsk', 40], ['khabarovsk', 20], ['moscow', 60], ['moscow', 10]]
この方法でも無事に目的のソートができました。多分ですが、こちらの方がマイナスを取るだけという簡単な方法かつ１行で書けるので、バグらせにくいのかなと思います。