Pythonのソート
リストのソート
pythonのソートは、リストなどのイテラブルオブジェクトに対して、sort()を実行することで要素の順番を並び替えます。
numbers = [8, 4, 3, 7, 6] numbers.sort() print(numbers) # 実行結果 [3, 4, 6, 7, 8]
lambdaを使ったソート
以下の例では、リストの要素を入れ替えてソートする方法を示しています。
```
list = [{"name": "Bob", "age": 20},
{"name": "Alice", "age": 25},
{"name": "John", "age": 15}]
sorted_list = sorted(list, key=lambda x: x["age"])
print(sorted_list)
```
実行結果：
```
[{'name': 'John', 'age': 15}, {'name': 'Bob', 'age': 20}, {'name': 'Alice', 'age': 25}]
```
numpy配列のソート
numpyには専用のソート関数が用意されています。使い方は以下の通り。
例： import numpy as np # 配列を定義 a = np.array([3, 2, 5, 1, 6, 4]) # ソート a.sort() # 結果を出力 print(a) # 出力結果：[1 2 3 4 5 6]
二次元配列でも、以下のように１回sortを実行するだけで、配列内がソートされます。
```python import numpy as np # 二次元配列を生成 arr = np.array([[7, 8, 5], [4, 3, 9], [2, 1, 6]]) # 昇順にソート arr_sorted = np.sort(arr) # 結果を表示 print(arr_sorted) # [[5 7 8] # [3 4 9] # [1 2 6]] ```
辞書（dict）のソート
辞書型は順序を変えることができません。そのため、sortedで別のリストに指定したソートを反映した辞書を代入します。
dic = {'a': 1, 'b': 3, 'c': 2}
# キーでソートする場合
sorted_dic = sorted(dic.items(), key=lambda x:x[0])
# => [('a', 1), ('b', 3), ('c', 2)]
# 値でソートする場合
sorted_dic = sorted(dic.items(), key=lambda x:x[1])
# => [('a', 1), ('c', 2), ('b', 3)]
set（集合）をソート
Pythonでset（集合）をソートする場合も、sorted()を使います。
```python
# 集合を定義する
my_set = {3, 8, 5, 1, 9}
# 集合をソートする
sorted_set = sorted(my_set)
# ソートされた集合を表示する
print(sorted_set) # [1, 3, 5, 8, 9]
```
sortedは、sortと何が違う？
sortとsortedは、どちらも要素を小さい順に並び替える（ソートする）関数です。何が違うかというと、sortはリスト自身を変更するのに対し、sortedは並び替えた結果を別のリストとして返すんですね。
そのため、sortedは辞書型や集合（set）などの順序のないオブジェクトにも使用することができます。
なお、通常のリストに対して使う場合は、sortもsortedも同じ結果になります。
例： # 数値でソート numbers = [3, 4, 1, 5, 2] sorted_numbers = sorted(numbers) print(sorted_numbers) # 出力: [1, 2, 3, 4, 5] # 文字列でソート strings = ["C", "A", "B", "D"] sorted_strings = sorted(strings) print(sorted_strings) # 出力: ['A', 'B', 'C', 'D']
Pythonのソートの方法
降順にソート
Pythonでソート順を逆（降順にソート）するには、reverse引数をTrueに設定します。
```python # リストを定義します my_list = [1, 4, 6, 2, 8, 3] # 降順にソートします my_list.sort(reverse=True) # ソート結果を表示します print(my_list) # [8, 6, 4, 3, 2, 1] ```
通常ソートのアルゴリズムは「クイックソート」
sort関数を使用する場合、ソートのアルゴリズムは「クイックソート」になります。
list = [5, 3, 2, 8, 1] # リストを降順にソート list.sort(reverse=True) # 結果を表示 print(list) # [8, 5, 3, 2, 1]
クイックソートには、以下のデメリットがあります。
- 最悪の場合において、計算量がO(N2)となり性能が低下します。
- 最も重要なデータが最後に来る可能性があります。
- ピボットの選択方法によって性能が大きく変わります。
場合によっては、別のアルゴリズムのソートを検討する必要があります。
バブルソート
バブルソートは、ループの中で要素を比較して入れ替えながら並びかえをおこなうというアルゴリズム。ロジックがわかりやすいので、学習用の例として使われます。
def bubble_sort(array): n = len(array) for i in range(n): for j in range(n-1, i, -1): if array[j] < array[j-1]: array[j], array[j-1] = array[j-1], array[j] # test array = [2, 3, 4, 1, 5] bubble_sort(array) print(array) # 実行結果 [1, 2, 3, 4, 5]
しかし、バブルソートのアルゴリズムは、順番を入れ替えるための一要素ごとの比較と交換を繰り返すため、要素数が多い場合、効率が悪くなり、時間がかかるというデメリットがあるため、開発現場などで使うことはないと思います。
マージソート（Merge Sort）
Merge Sortは、分割統治法（Divide and Conquer）と呼ばれるアルゴリズムを用いたソートアルゴリズムです。ソートしたい配列を繰り返し分割し、最終的に2つの小さな配列に分割するということを行います。
そして、これら2つの小さな配列をマージして1つの配列に結びつけることで、ソートされた配列を作ることができます。Merge Sortは、非常に効率的なソートアルゴリズムであり、平均計算時間としてΟ(nlogn)という時間複雑度を持っています。
そのものズバリを実行する関数がないため、関数定義して処理を記述しています。
def merge_sort(array): if len(array) <= 1: return array mid = len(array) // 2 left = array[:mid] right = array[mid:] left = merge_sort(left) right = merge_sort(right) return merge(left, right) def merge(left, right): result = [] left_idx, right_idx = 0, 0 while left_idx < len(left) and right_idx < len(right): if left[left_idx] <= right[right_idx]: result.append(left[left_idx]) left_idx += 1 else: result.append(right[right_idx]) right_idx += 1 if left_idx < len(left): result.extend(left[left_idx:]) if right_idx < len(right): result.extend(right[right_idx:]) return result arr = [6, 5, 4, 3, 2, 1] sorted_arr = merge_sort(arr) print(sorted_arr) # [1, 2, 3, 4, 5, 6]
ソート時の比較関数が単純な場合は、lambdaを利用するケースもあります。
Pythonのソートのまとめ
- Pythonのソートは、sort()メソッドで実行できる。辞書型や集合型にはsorted()を使う
- 降順ソートは、reverse=Trueと引数指定することで可能
- sort()のアルゴリズムはクイックソート。lambdaなどを使って別アルゴリズムを実装することもできる