・2 min read
pandas.DataFrame().sort_valuesはデフォルトで不安定なソートアルゴリズムを使用する
概要
pandas.DataFrameで任意の列の値を用いてソートを行う際，sort_valuesメソッドを使用するが，デフォルトのソートアルゴリズムはクイックソートであり，不安定なソートになっている。
しかし，状況によってはマージソートなどで安定にソートしたいこともある。その場合は，引数で
kind="mergesort"もしくはkind="stable"を与えることで実現できる。
実装例
以下にソートの対象列に重複する値が多い場合のデータを用意し，
kindを指定しているか否かで結果の違いを確認するサンプルコードを示す。import numpy as np
import pandas as pd
np.random.seed(812)
# 雑にデータを作る。
data = []
for i in range(ord("a"), ord("a") + 1000):
data.append([chr(i), np.random.randint(24, 26)])
df = pd.DataFrame(data, columns=["name", "age"])
print(df.head())
# age 列でソートする
sorted_default_df = df.sort_values("age")
sorted_mergesort_df = df.sort_values("age", kind="mergesort")
print(sorted_default_df.head())
print(sorted_mergesort_df.head())出力は以下のようになる。
name age
0 a 25
1 b 24
2 c 24
3 d 25
4 e 25
name age
666 ˻ 24
352 ǁ 24
819 Δ 24
820 Ε 24
569 ʚ 24
name age
1 b 24
2 c 24
6 g 24
7 h 24
8 i 24結果
DataFrameのindexに注目する。
安定ソートならばname列がbである行が先頭に来るはずが，デフォルトの
sort_values()では666行目が先頭に来ており，そのあとのindexも昇順でも降順でもなくなっている。
対して，kind="mergesort"を指定した場合は，順序が保たれた状態でソートされていることがわかる。クイックソートとマージソートの違いとして，マージソートの使用するメモリはクイックソートの倍必要になることがあげられる。マージソートを使用する際にはメモリが十分に足りていることを確認してから使用すればよいだろう。
