はじめに
こんにちは。開発部の雨です。
今回はどの言語でもよく使われているソートの動きとその実装方法について、全くの初心者の方にもわかりやすく説明したいと思います。
ソートとは？
まず、「ソート」とは何でしょうか？
ソートはリストのデータを決まった順序に並べることです。
一般的に「昇順」と「降順」という2種類の並び方があります。
「ソート」と聞くと、多くの人はまず数字を思い浮かべるかもしれません。
この記事では数字を例に使って説明しますが、文字列やオブジェクトなどもソートの対象になるという点も、ぜひ覚えておいてください。
バブルソート
最初に、バブルソートを説明したいと思います。
バブルソートは一番簡単で直感的なソートアルゴリズムです。
「ソートを実装してください」と言われたとき、多くの人が無意識のうちにこのバブルソートを実装してしまうかもしれません。
泡（バブル）が上に浮かぶようなイメージを持ってください。その泡は数字だと思ってください。
大きいほど、上に浮かびます。
バブルソートの手順
- 現在の位置を0に設定する
- 現在の位置の値と、次の値を比較する
- もし現在の値が次の値より大きい場合、値を交換する（小さい値が下、大きい値が上）
- 現在の位置を次の位置に移動する
- 末尾に到達するまで、ステップ2〜4を繰り返す
- リストの長さを
nとすると、ステップ1〜5をn回繰り返す
例
下 → 上の順番と考えてください。
リスト＝[4, 3, 5, 2]
1回目のループ
現在位置：0
4 > 3 → 交換 → [3, 4, 5, 2]
現在位置：1
4 < 5 → そのまま → [3, 4, 5, 2]
現在位置：2
5 > 2 → 交換 → [3, 4, 2, 5]
2回目のループ
現在位置：0
3 < 4 → そのまま → [3, 4, 2, 5]
現在位置：1
4 > 2 → 交換 → [3, 2, 4, 5]
現在位置：2
4 < 5 → そのまま → [3, 2, 4, 5]
3回目のループ
現在位置：0
3 > 2 → 交換 → [2, 3, 4, 5]
現在位置：1
3 < 4 → そのまま → [2, 3, 4, 5]
現在位置：2
4 < 5 → そのまま → [2, 3, 4, 5]
4回目のループ
現在位置：0
2 < 3 → そのまま → [2, 3, 4, 5]
現在位置：1
3 < 4 → そのまま → [2, 3, 4, 5]
現在位置：2
4 < 5 → そのまま → [2, 3, 4, 5]
何でソートされるのか？その仕組み
大きい値はいつも上に上がる
ステップ2〜4は何をしているかを理解しなければなりません。
ステップ2〜4は大きい値をいつも上にしているんです。
- 現在の位置の値が次の位置の値より大きい場合：交換されて大きい値が上
- 現在の位置の値が次の位置の値より小さい場合：交換されなくて大きい値が上
どちらのケースも大きい値の方が上です。
ステップ4で現在の位置を次の位置に移動すると、現在の位置の値はここまでのリストで一番高い値になります。
それを知ると、末尾に到達したとき、リストの最後の位置の値は必ず一番高い値です。
なぜステップ6が必要なのか？
ループ1回目の結果は [3, 4, 2, 5] でした。
一回目の時は「5」は「4」より大きいので、「4」は浮かびませんでした。
「5」にブロックされて、「4」より小さい値「2」が「4」より上になっていたのです。
でも、2回目では「5」は最後の位置になって、「4」はブロックされず、最後の位置の左まで浮かびました。
2番目に大きい値が正しい位置に浮かぶには、
1番目に大きい値が正しい位置にあるという条件があります。
この仕組みはリストの中のすべての数字に当てはまります。
だから、ステップ6が必須です。
実装(Python)
def bubble_sort_basic(arr):
n = len(arr)
#n回繰り返す
for _ in range(n):
for i in range(n - 1):
if arr[i] > arr[i + 1]:
#次の値が大きい場合、値を交換
arr[i], arr[i + 1] = arr[i + 1], arr[i]
return arr
# 例
lst = [4, 3, 5, 2]
sorted_lst = bubble_sort_basic(lst)
print(sorted_lst) # 出力: [2, 3, 4, 5]
時間計算量を測ろう
時間計算量とはプログラムの速さを測る基準です。
当記事では詳しい説明はしませんが、簡単に言うと、処理するデータの量が増えたときに、処理にかかる時間がどれだけ増えるかを表したものです。
実は、上で紹介したバブルソートの実装は一番効率的な実装ではありません。
でも、そのぶんシンプルなので、時間計算量を理解するにはちょうどいいです。
この実装では、n 回のループの中で、さらにリストのすべての要素をループしています。つまり、ループの回数は n × n 回、すなわち n² 回です。
この実装では、正確には内側のループは n-1 回になりますが、時間計算量の考え方では 「1」などの小さい差は無視してOK です。
なので、n × (n-1) もざっくりと n² として考えます。
たとえば、リスト [4, 3, 5, 2] のように要素数が 4 の場合、4 × 4 = 16 回ループします。
このような処理時間の増え方を、時間計算量 O(n²)（オー・エヌ・ジョウ）と表現します。
まとめ
当記事ではバブルソートを紹介しました。簡単で直感的なアルゴリズムなので、他のソートアルゴリズムよりは遅いです。
そのため、バブルソートは実践に使われていないです。次回は効率的で実践に使われている、マージソートを説明します。
最後に
はつかぜ株式会社では、IT学習や業務に役立つ情報を定期的にお届けしていきたいと思っています。
システム開発のお問い合わせ・ご相談はこちら