はじめに
こんにちは。デジタルステーション習志野スタッフの荒井です。
今回の記事では、大量の数字の列などを並び替えるときに使う「ソートアルゴリズム」について、今回は、基本的な手法の一つであり、前回紹介したバブルソートの改良版である「シェーカーソート」を紹介したいと思います。
ソートアルゴリズムとは
まず、ソートアルゴリズムとは何か、簡単に説明します。
前提として、アルゴリズムとは、問題を解決するための手順や方法のことを言います。
そして、ソートアルゴリズムとは、大量のデータを、小さい順（昇順）や、大きい順（降順）など特定の並びに整列させるために考え出されたアルゴリズムのことを言います。
PCの処理では、エクスプローラーでのフォルダ管理や、表計算ソフトでの並び替えなど、何かしらのデータを並び替えることが多いです。
そのため、より早く、より少ない試行回数で目的を達成するため、今までに様々な手法が開発されています。
シェーカーソートとは
シェーカーソートは、ソートアルゴリズムの一種で、アルゴリズムの考え方はバブルソートとよく似通っています。
隣接する配列を比較して、昇順または降順に並べ替える方法です。
バブルソートとの違いとしては、バブルソートでは端まで確認した後に配列の先頭から比較しなおしますが、シェーカーソートでは末端から往復するような挙動を取ります。
特徴はバブルソートと同じく、
- 構造が比較的理解しやすい
- 安定して動作する
- 追加のメモリ容量が必要ない（元の配列を変更するため）
- 計算量が多く、処理は遅くなりがち
の4点に加え、バブルソートと比較して無駄が出づらいため、バブルソートより高速になりやすいという特徴を持っています。
実際にやってみる
では、実際にPythonを使って、視覚的にシェーカーソートをやってみましょう。
グラフを扱うので、matplotlibというライブラリを使うと、きれいに作りやすいです。
以下に、サンプルコードを載せておくので、時間がある方はpythonとライブラリをインストールして、.pyファイルで実行してみてください。
import matplotlib.pyplot as plt
import numpy as np
# シェーカーソート関数（リアルタイムでグラフ更新）
def shaker_sort(arr):
left = 0
right = len(arr) - 1
time = 0.05
replace_count = 0
while left < right:
#左から右
for i in range(left, right):
plt.cla() # 前のグラフを消去
rect = plt.bar(range(len(arr)), arr, color='blue') # 現在の状態をバーで表示
rect[i].set_color('red') # 入れ替えをわかりやすくするための色付け
rect[i+1].set_color('yellow') # 入れ替えをわかりやすくするための色付け
#入れ替えが発生した場合
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
# 各ステップごとにグラフを更新
plt.cla() # 前のグラフを消去
rect = plt.bar(range(len(arr)), arr, color='blue') # 現在の状態をバーで表示
rect[i+1].set_color('red') # 入れ替えをわかりやすくするための色付け
rect[i].set_color('yellow') # 入れ替えをわかりやすくするための色付け
replace_count += 1
plt.pause(time) # time秒待つ
#入れ替えるものがなくなったら終了する
if replace_count == 0:
break
replace_count = 0
right -= 1
#右から左
for i in range(right, left, -1):
plt.cla() # 前のグラフを消去
rect = plt.bar(range(len(arr)), arr, color='blue') # 現在の状態をバーで表示
rect[i].set_color('red') # 入れ替えをわかりやすくするための色付け
rect[i-1].set_color('yellow') # 入れ替えをわかりやすくするための色付け
#入れ替えが発生した場合
if arr[i] < arr[i-1]:
arr[i], arr[i - 1] = arr[i - 1], arr[i]
# 各ステップごとにグラフを更新
plt.cla() # 前のグラフを消去
rect = plt.bar(range(len(arr)), arr, color='blue') # 現在の状態をバーで表示
rect[i-1].set_color('red') # 入れ替えをわかりやすくするための色付け
rect[i].set_color('yellow') # 入れ替えをわかりやすくするための色付け
replace_count += 1
plt.pause(time) # time秒待つ
#入れ替えるものがなくなったら終了する
if replace_count == 0:
break
replace_count = 0
left += 1
# 初期のデータ（ランダムな整数のリスト）
data = np.random.randint(1, 300, 50)
# グラフを初期化
plt.figure(figsize=(10, 6))
plt.bar(range(len(data)), data, color='blue') # 初期状態を表示
plt.title('Shaker Sort - Initial State')
plt.show()
plt.ion()
# シェーカーソートを実行
shaker_sort(data)
# ソート終了後に最終的な結果を表示
plt.ioff()
plt.cla()
plt.bar(range(len(data)), data, color='green')
plt.title('Shaker Sort - Sorted')
plt.show()
出力結果は、下の動画のようになります。
往復するので、小さいデータが右側に多くても、バブルソートより少し効率的に運ぶことが出来ています。
ソートしている様子がわかりやすいように、前回よりもデータ数を増やしてみました。
また、今回はデータが整い次第、ソートを切り上げるように改善したため、終了タイミングも少し早くなっています。
今後、紹介したソートアルゴリズムの速度勝負をする記事も投稿する予定です。お楽しみに！
まとめ
今回はこれで以上となります。
シェーカーソートは、バブルソートの考え方を軸に、少しだけ効率化されていました。
バブルソートとデータ数や速度をそろえて、どのくらい差があるかを調べてみるのも面白いかもしれません。
グラフを使って視覚化すると見ていて楽しいものになるので、pythonが使えるのであれば、一度作ってみてもよい経験になると思います。
ぜひ一度、作ってみてください！
デジタルステーション習志野
〒274-0063 船橋市習志野台4-1-7 習志野駅前郵便局2F
047-769-7545
