Pythonでソート処理を実装してみた
筈井です。
先週から弊社ではアルゴリズム勉強会を実施しています。
教材に使用しているのは「アルゴリズムとデータ構造」という書籍です。
各章ごとに担当メンバーを割り振り、内容のサマリーを解説しながらメンバー同士でディスカッションするという形で進めています。
第1回目のお題は「ソート」ということで、データをプログラム自身で整理する基本的な方法について学びました。
せっかく学んだので、今回はバブルソート、クイックソート、マージソートという3種類のソートをPythonで実装していこうと思います。
バブルソート
最も単純なソートの手法がバブルソートと呼ばれるものです。
バブルソートは、次のような手順を繰り返すことでデータを整理する手法です。
- 先頭から順番にデータをチェック
- 左右の並びがおかしい箇所があれば入れ替える
- データの最後までたどり着いたら再び先頭から順序をチェックする
- データの先頭から最後まで1度も入れ替えが発生しなければ整理完了
具体的に、1〜5の数字をもつリストでバブルソートの様子を見ていきましょう。
# 先頭から順番に順序をチェックする
[2, 3, 1, 5, 4]
# 3と1の順序がおかしいので入れ替えた
[2, 1, 3, 5, 4]
# 次は5と4の順序もおかしいので入れ替えた
[2, 1, 3, 4, 5]
# 最後まで順序をチェックし終えたので、再び先頭からチェックする
[2, 1, 3, 4, 5]
# 2と1の順序がおかしいので入れ替えた
[1, 2, 3, 4, 5]
# 最後まで順序のチェックが完了
[1, 2, 3, 4, 5]
# 再び先頭から順序をチェックし、順序がおかしい箇所がないのでバブルソート完了
[1, 2, 3, 4, 5]バブルソートを実行する関数をPythonで実装してみると下記のようになります。
リスト内の値を隣の値と比較して、順序がおかしければ入れ替えます。
# coding: UTF-8
import time
import random
def bubble_sort(list):
# リストの要素数が1より大きくなければソートの必要なし
if len(list) <= 1:
return list
# 入れ替えループを抜けるフラグ
exchange_flg = True
while exchange_flg:
exchange_flg = False
for i in range(len(list) - 1):
if list[i] > list[i + 1]:
# 左右の値を入れ替える
list[i], list[i + 1] = list[i + 1], list[i]
exchange_flg = True
return list
if __name__ == "__main__":
list = list(range(1000000))
src = random.sample(list, len(list))
start_time = time.time()
sorted_list = bubble_sort(list)
elapsed_time = time.time() - start_time
print("elapsed_time: {0}[sec]".format(elapsed_time))
クイックソート
バブルソートは「隣の要素より値が大きいか小さいか」を1つずつ判別していくため、計算量が多くなりやすいという特徴があります。
一方、クイックソートは「ある特定の値よりも大きいか小さいか」という観点で全体を一気に処理していくという手法です。クイックソートは実用上最も高速であるとされ、並べ替えのアルゴリズムとして多くのプログラムで利用されています。
具体的なソートの流れは下記のようになります。
# クイックソート開始
# 特定の値を基準に(今回は先頭の6を)、小さい数字は前に、大きい数字は後ろに移動
[6, 9, 3, 5, 8, 1, 4, 7, 0, 2]
# 6の左側には「6よりも小さい数字のグループ」
# 6の右側には「6より大きい数字にグループ」
[3, 5, 1, 4, 0, 2, 6, 9, 8, 7]
# [3, 5, 1, 4, 0, 2]のグループでは3を基準に並び替え
[1, 0, 2, 3, 5, 4, 6, 9, 8, 7]
# [9, 8, 7]のグループでは9を基準に並び替え
[1, 0, 2, 3, 5, 4, 6, 8, 7, 9]
・・・
# 細分化されるグループごとに基準を設けて並び替えを繰り返すことで最終的にソートが完了
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]バブルソートと同様に、クイックソートを実行する関数もPythonで実装してみましょう。
# coding: UTF-8
import time
import random
def quick_sort(list):
# リストの要素数が1より大きくなければソートの必要なし
if len(list) <= 1:
return list
left_list = []
right_list = []
# クイックソートする際の基準をランダムに選択
pivot = random.choice(list)
pivot_count = 0
for num in list:
if num < pivot:
left_list.append(num)
elif num > pivot:
right_list.append(num)
else:
pivot_count += 1
# 左右2つにリストを分割し、quick_sort()関数を再帰的に呼び出す
left_list = quick_sort(left_list)
right_list = quick_sort(right_list)
return left_list + [pivot] * pivot_count + right_list
if __name__ == "__main__":
list = list(range(1000000))
src = random.sample(list, len(list))
start_time = time.time()
sorted_list = quick_sort(list)
elapsed_time = time.time() - start_time
print("elapsed_time: {0}[sec]".format(elapsed_time))
マージソート
クイックソートはバブルソートよりも高効率なソート方法です。
しかしソート対象のデータの並び順が悪いと、結局はバブルソートと変わらないソート効率になってしまいます。
より確実に、効率よくソートする方法がマージソートです。
# マージソート前のリスト
[6, 9, 3, 5, 8, 1, 4, 7, 0, 2]
# リストを半分に分割する
[6, 9, 3, 5, 8][1, 4, 7, 0, 2]
# それぞれを更に分割
[6, 9, 3][5, 8][1, 4, 7][0, 2]
# 全ての要素数が1になるまで分割を繰り返す
[6][9][3][5][8][1][4][7][0][2]
# 隣同士を整列しながら併合
[6, 9][3, 5][1, 8][4, 7][0, 2]
# 更に隣同士を整列・併合
[3, 5, 6, 9][1, 4, 7, 8][0, 2]
[1, 3, 4, 5, 6, 7, 8, 9][0, 2]
# 全体が1つになるまで整列・併合を繰り返す
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]マージソートもPythonで実装してみましょう。
# coding: UTF-8
import time
import random
def merge_sort(list):
# リストの要素数が1より大きくなければソートの必要なし
if len(list) <= 1:
return list
# リストを2つのサブリストに分割
povit = int(round(len(list)/2))
left_sub_list = list[:povit]
right_sub_list = list[povit:]
# 分割したサブリストを、merge_sort()関数を再帰的に呼び出してソート
left = merge_sort(left_sub_list)
right = merge_sort(right_sub_list)
# 2つのサブリストをマージして1つのソート済みリストを作成
return merge_lists(left, right)
def merge_lists(left_list, right_list):
sorted_list = []
while (len(left_list) > 0) and (len(right_list) > 0):
if left_list[0] < right_list[0]:
sorted_list.append(left_list[0])
del left_list[0]
else:
sorted_list.append(right_list[0])
del right_list[0]
if len(left_list) > 0:
sorted_list.extend(left_list)
else:
sorted_list.extend(right_list)
return sorted_list
if __name__ == "__main__":
list = list(range(1000000))
src = random.sample(list, len(list))
start_time = time.time()
sorted_list = merge_sort(list)
elapsed_time = time.time() - start_time
print("elapsed_time: {0}[sec]".format(elapsed_time))
実行速度
ここまでバブルソート、クイックソート、マージソートを実行するPythonコードを作成してきました。
最後に下記のコードとプログラム実行速度を比較してみます。参考に、Python組み込みのソート関数(sorted)も実行してみましょう。
# coding: UTF-8
import time
import random
if __name__ == "__main__":
list = list(range(1000000))
src = random.sample(list, len(list))
start_time = time.time()
sorted_list = sorted(list)
elapsed_time = time.time() - start_time
print("elapsed_time: {0}[sec]".format(elapsed_time))
実行結果は以下のようになりました。
$ python bubble_sort.py
elapsed_time: 0.0806891918182[sec]
$ python quick_sort.py
elapsed_time: 3.6704659462[sec]
$ python merge_sort.py
elapsed_time: 63.6543469429[sec]
$ python sorted.py
elapsed_time: 0.0241670608521[sec]バブルソート、クイックソート、マージソートの中では、予想に反してバブルソートのPythonコードが最も速いという結果になりました。
これはPythonでは再帰呼び出しに時間がかかるためだと考えられ、あまり速度が出ないそうです。
それにしてもPythonのソートは早いですね。
終わりに
アルゴリズム勉強会で学んだソートをPythonコードで実装してみました。
実務でソートを自前実装する機会はレアケースですが、何かの参考になれば幸いです。
参考文献
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
参考ページ
Sorting HOW TO
Rosetta Code
ソートアルゴリズムと Python での実装
