ソートアルゴリズム - データサイエンス関連+αのメモ

ソートアルゴリズムはデータを特定の順序に並び替えるアルゴリズム。用途やデータの特性によって最適な手法が異なる。

主要アルゴリズムの比較¶

アルゴリズム	最悪	平均	最良	空間	安定	in-place
バブルソート	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	✓	✓
選択ソート	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	✗	✓
挿入ソート	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	✓	✓
マージソート	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	✓	✗
クイックソート	$O(n^2)$	$O(n\log n)$	$O(n\log n)$	$O(\log n)$	✗	✓
ヒープソート	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	✗	✓
計数ソート	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	✓	✗
基数ソート	$O(d(n+b))$	$O(d(n+b))$	$O(d(n+b))$	$O(n+b)$	✓	✗

選択の指針¶

汎用: Python の sorted() / list.sort()（Timsort）を使う
小配列 / ほぼソート済み: 挿入ソート
最悪保証が必要 + in-place: ヒープソート
安定 + 最悪保証: マージソート
実用最速（平均）: クイックソート（median-of-3 や乱択ピボット）
整数 + 値域が小さい: 計数ソート
整数 + 値域が広い: 基数ソート