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

Pythonで色々な順番でソートする方法(sort, sorted)

tadanori

競技プログラミング(AtCoder)の問題を解く場合などに、いろいろなパターンでソートしたい場合があります。ここでは、ソートのパターンをいくつか紹介します。

はじめに

この記事では、Pythonでソートする方法について解説します。AtCoderの問題などを解く場合に、昇順・降順以外にもいろいろな条件でソートしたい場合があります。この記事では、いくつかのパターンについてソートの書き方を解説します。

ソート(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]

降順ソート

降順ソートを行いたい場合には、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つ以上ある場合

各要素が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つめの要素は降順

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つ目の要素が同値の場合は2つめの要素が大きい順にならんでいることが確認できます。

[[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]]

2つめの要素でソートした後に1つめの要素でソート

まず2つ目の要素でソートし、同値の場合に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つ目の要素でソート後、1つ目の他所で並んでいることが分かります。

[[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]]

複雑なソート

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

$$
\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関数は同値の場合は0、小さい場合は−1、大きな場合は1を返す関数です。

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で昇順でソートされます。

10 5
8 7
10 4
8 7
10 5
2 7
10 8
6 6
2 3
10 5
-
2 3
2 7
6 6
8 7
8 7
10 4
10 5
10 5
10 5
10 8

sortが使えない例(sortedを利用する例)

Pythonではタプルなどの書き換えができない型をソートすることはできません。この場合は、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で使うソートパターンのほとんどを網羅していると思います。

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

記事URLをコピーしました