2024.06.19 2024.08.28

記事内に商品プロモーションを含む場合があります

Pythonのソートパターンを徹底解説！任意の条件でデータをソートする方法

Aru

競技プログラミングでは、特定の条件や複数の条件でデータをソートすることで解きやすくなる問題が存在します。また、実務でも、色々な条件でデータソートを行いたい場合があります。この記事では、Pythonのsortとsortedを使って、さまざまなパターンでデータをソートする方法について紹介します。

Contents

はじめに
色々なソートのパターン
まとめ

はじめに

この記事では、Pythonのプログラムで特定の条件や複数の条件に基づいてデータをソートする方法について解説します。競技プログラミング（AtCoder）の問題などを解く場合、昇順、降順以外の条件でソートしたい場合も多くあります。

実は、Pythonのsort, sortedは結構自由な条件に基づいてソートを行うことが可能です。この記事では、Pythonのソートだけに絞って解説を行いたいと思います。

色々なソートのパターン

昇順ソート

sortを使う方法

まずは、基本となる昇順ソートです。昇順ソートは以下のようなコードで行うことができます。

プログラムを見てわかるように、リスト名.sort()を実行するだけです。これで、リストがソートされます。

import random
a = [random.randint(1, 100) for _ in range(10)]
print(a)
a.sort()
print(a)

[18, 23, 77, 71, 21, 20, 51, 46, 28, 100]
[18, 20, 21, 23, 28, 46, 51, 71, 77, 100]

sortedを使う方法

もし、元となるリストをソートしたくない場合は、sortedを使います。

b=sorted(a)とすると、リストaの要素をソートした結果をリストbとして受け取ることができます。

import random
a = [random.randint(1, 100) for _ in range(10)]
print(a)
b = sorted(a)
print(a)
print(b)

実行結果を見るとわかるように、元のリストはソート前の状態を保ちます。

基本はsortと同じ使い方が可能です。sortedについては、どのような場合に使うのかを後半で少し解説します。

[58, 86, 27, 67, 84, 59, 82, 86, 88, 59]
[58, 86, 27, 67, 84, 59, 82, 86, 88, 59]
[27, 58, 59, 59, 67, 82, 84, 86, 86, 88]

降順ソート

降順ソートを行いたい場合には、reverse=Trueを引数として渡します。これで大きい順にソートされます。

import random
a = [random.randint(1, 100) for _ in range(10)]
print(a)
a.sort(reverse=True)
print(a)

[62, 79, 45, 64, 11, 63, 19, 66, 96, 19]
[96, 79, 66, 64, 63, 62, 45, 19, 19, 11]

要素が2つ以上ある場合のソート

リストの各要素が２つ以上の値からなる場合、sort()を実行すると1つ目の要素で昇順ソートが行われ、1つ目の要素が同じ場合は2つ目の要素で昇順ソートが行われます。

1つ目の要素でソート→同値の場合2つ目・3つ目・・・でソートします。

import random
a = [[random.randint(1, 3), random.randint(1, 2)] for _ in range(10)]
print(a)
a.sort()
print(a)

[[3, 2], [1, 1], [2, 1], [1, 2], [1, 2], [3, 1], [2, 2], [3, 1], [1, 1], [1, 1]]
[[1, 1], [1, 1], [1, 1], [1, 2], [1, 2], [2, 1], [2, 2], [3, 1], [3, 1], [3, 2]]

１つめの要素は昇順、２つめの要素は降順のソート

1つ目の要素は昇順、2つ目の要素は降順でソートしたい場合には、lambdaを利用します。

具体的には、lamda x: (x[0], -x[1])というように、2つ目の要素はマイナスをつけてソート順を指定します。マイナスをつけたことで大きな値ほど小さな値になるので降順にソートされます。

import random
a = [[random.randint(1, 3), random.randint(1, 2)] for _ in range(10)]
print(a)
a.sort(key = lambda x: (x[0], -x[1]))
print(a)

以下は結果です。1つ目の要素が同値の場合は２つめの要素が大きい順にならんでいることが確認できます。

[[1, 2], [3, 2], [3, 1], [2, 1], [2, 1], [2, 1], [3, 2], [1, 2], [1, 2], [3, 1]]
[[1, 2], [1, 2], [1, 2], [2, 1], [2, 1], [2, 1], [3, 2], [3, 2], [3, 1], [3, 1]]

２つめの要素→１つめの要素でソート

まず２つ目の要素でソートし、同値の場合に1つ目の要素でソートしたい場合はlambdaを使ってx[0]とx[1]の評価の順番を入れ替えます。

import random
a = [[random.randint(1, 3), random.randint(1, 2)] for _ in range(10)]
print(a)
a.sort(key = lambda x: (x[1], x[0]))
print(a)

結果を見ると2つ目の要素でソート後、１つ目の他所で並んでいることが分かります。

[[3, 1], [2, 1], [3, 1], [1, 1], [2, 2], [2, 1], [1, 1], [2, 2], [3, 2], [1, 1]]
[[1, 1], [1, 1], [1, 1], [2, 1], [2, 1], [3, 1], [3, 1], [2, 2], [2, 2], [3, 2]]

複雑なソート（cmp_to_keyを使うパターン）

例えば、以下のような比率順にソートしたい場合を考えます。

$$
\frac{a_i[0]}{a_i[1]} < \frac{a_j[0]}{a_j[1]}
$$

割り算を行うと浮動小数点の誤差がでますので誤差を出さずに比較を行いたいです。この場合、式を以下のように乗算の形に変形します。

$$
a_i[0] \times a_j[1] < a_j[0] \times a_i[1]
$$

式を見ると分かりますが、iとjの項が左辺にも右辺にも出現するためlambdaを使う方法では記述できません。

この場合は、functoolsにあるcmp_to_keyを利用すると簡単です。

具体的には、以下のようなcmp関数を定義し、key=cmp_to_key(cmp)とします。

cmp関数は同値の場合は０、小さい場合は−１、大きな場合は１を返す関数です。

import random
from functools import cmp_to_key
a = [[random.randint(1, 100), random.randint(1, 100)] for _ in range(10)]
print(a)

def cmp(a, b) :
    x0 = a[0] * b[1]
    x1 = b[0] * a[1]
    if x0 == x1 : return 0
    if x0 < x1 : return -1
    return 1

a.sort(key = cmp_to_key(cmp))
for e in a:
    print(f"{e}({e[0]/e[1]})")
print()

以下は、比率順に並んでいるかを割り算を実際に行って確認しています。結果を見ると、割り算の大きさが小さい順に並んでいることが分かります。

[[92, 70], [1, 99], [5, 24], [3, 8], [26, 20], [51, 28], [14, 58], [40, 34], [67, 10], [51, 51]]
[1, 99](0.010101010101010102)
[5, 24](0.20833333333333334)
[14, 58](0.2413793103448276)
[3, 8](0.375)
[51, 51](1.0)
[40, 34](1.1764705882352942)
[26, 20](1.3)
[92, 70](1.3142857142857143)
[51, 28](1.8214285714285714)
[67, 10](6.7)

比率でソートで解ける問題は結構ありますので、ソートでかけることを知っていると便利です。

クラスの要素の値でソート

クラスの要素の値でソートする例です。これも、lambdaを用いて記述可能です。

import random
class A:
    def __init__(self, x, y):
        self.x = x
        self.y = y

a = [A(random.randint(1,10), random.randint(1,10)) for _ in range(10)]
for e in a: print(e.x, e.y)
print("-")
a = sorted(a, key = lambda x: (x.x, x.y))
for e in a: print(e.x, e.y)

以下のように、xで昇順、yで昇順でソートされます。

sortが使えない例（sortedを利用する例）

Pythonのsort（）ではタプルなどの書き換えができない型をソートすることはできません。この場合は、sortedを利用します。

sortedは第一引数にソートする対象の変数を入力し、別途戻り値で結果を返します。

新しくソートされたリストなどが生成される点がsortと異なります。

import random

a = tuple(random.randint(1, 100) for _ in range(10))
print(a)
a = sorted(a)
print(a)

(10, 57, 25, 60, 42, 73, 86, 51, 21, 25)
[10, 21, 25, 25, 42, 51, 57, 60, 73, 86]

tupleをlistに変換してからソートするという方法もあります。

まとめ

以上、Pythonでのソートについて解説しました。ここに挙げたパターンで、競技プログラミングなどで使うソートパターンのほとんどを網羅していると思います。参考にしてください。

#AtCoder #python #sort #sorted #ソート