Pythonのソート
Pythonのソートの仕方
Pythonでリストをソートするには、以下の方法があります。
- リストのメソッドを使用する
- 組み込み関数を使用する
コレ以外にも、「アルゴリズムを手作りでソート」という方法もあります。が、フツーにメソッドや組み込み関数使ったほうが効率が良いでしょう。本気で高速ソートをしたい場合は、その部分だけC言語で速いモジュールとして作り込むケースがあります。
ちなみに、Pythonのsort()メソッドは、Timsortというソートアルゴリズムで、挿入ソートとマージソートの長所を組み合わせたものです。
| アルゴリズム | 時間計算量 | 空間計算量 | 安定性 | 特徴 |
|---|---|---|---|---|
| 挿入ソート | O(n^2) | O(1) | 安定 | データがすでに部分的にソートされている場合に高速 |
| 選択ソート | O(n^2) | O(1) | 不安定 | 常に最小値または最大値を探す |
| シェルソート | O(n log n) | O(1) | 安定 | 挿入ソートを改良したもの |
| クイックソート | O(n log n) | O(log n) | 不安定 | 分割と統合を繰り返す |
| マージソート | O(n log n) | O(n) | 安定 | データを2つの部分に分割してソートする |
| ヒープソート | O(n log n) | O(1) | 不安定 | ヒープ構造を利用する |
各ソートアルゴリズムの特徴です。
- 挿入ソート：データがすでに部分的にソートされている場合に高速
- 選択ソート：常に最小値または最大値を探す
- シェルソート：挿入ソートを改良したもの
- クイックソート：分割と統合を繰り返す
- マージソート：データを2つの部分に分割してソートする
- ヒープソート：ヒープ構造を利用する
Pythonのソートのサンプルコード
リストのメソッドを使用するサンプルコードを紹介します。
リストには、sort()メソッドが用意されています。sort()メソッドを使用すると、リストを昇順にソートできます。
list = [1, 5, 3, 2, 4] list.sort() print(list)
このコードは、リストを昇順にソートします。
出力：
[1, 2, 3, 4, 5]
sort()メソッドには、第二引数として、ソートの順序を指定することができます。
list = [1, 5, 3, 2, 4] list.sort(reverse=True) print(list)
このコードは、リストを降順にソートします。
出力：
[5, 4, 3, 2, 1]
また、sort()メソッドには、キーワード引数として、ソートする基準を指定することができます。
list = ["a", "c", "b"] list.sort(key=len) print(list)
このコードは、リストを文字列の長さでソートします。
出力：
['a', 'b', 'c']
組み込み関数を使用したソートについても紹介します。
組み込み関数には、sorted()関数が用意されています。sorted()関数を使用すると、リストをソートして、新しいリストを返すことができます。
list = [1, 5, 3, 2, 4] sorted_list = sorted(list) print(sorted_list)
このコードは、リストを昇順にソートして、新しいリストを返します。
出力：
[1, 2, 3, 4, 5]
sorted()関数には、第二引数として、ソートの順序を指定することができます。
list = [1, 5, 3, 2, 4] sorted_list = sorted(list, reverse=True) print(sorted_list)
このコードは、リストを降順にソートして、新しいリストを返します。
出力：
[5, 4, 3, 2, 1]
また、sorted()関数には、キーワード引数として、ソートする基準を指定することができます。
list = ["a", "c", "b"] sorted_list = sorted(list, key=len) print(sorted_list)
このコードは、リストを文字列の長さでソートして、新しいリストを返します。
出力：
['a', 'b', 'c']