シェーカーソートとは、一般的なソートアルゴリズムの1つであり、バブルソートの改良版です。バブルソートと同じく、要素を比較し、必要に応じて入れ替えて、最終的に昇順または降順に並べ替えます。しかし、シェーカーソートでは、要素の比較と交換を左右方向に行い、要素の走査を交互に行うことで、処理の効率を改善しています。
シェーカーソートのアルゴリズムは以下のようになります。
- 配列の先頭から末尾まで要素を比較し、隣り合う2つの要素が順序通りでない場合は交換する。
- 配列の末尾から先頭まで要素を比較し、隣り合う2つの要素が順序通りでない場合は交換する。
- 1.と2.の処理を、配列の先頭と末尾が交差するまで繰り返す。
実例
以下に、シェーカーソートの実例を示します。
例1: 配列 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] の場合
- 1回目の走査: [1, 3, 1, 4, 5, 2, 6, 5, 3, 9]
- 2回目の走査: [1, 1, 3, 4, 2, 5, 3, 5, 6, 9]
- 3回目の走査: [1, 1, 3, 2, 4, 3, 5, 5, 6, 9]
- 4回目の走査: [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]
例2: 配列 [7, 3, 9, 5, 1, 8, 2, 6, 4, 0] の場合
- 1回目の走査: [3, 7, 5, 1, 8, 2, 6, 4, 0, 9]
- 2回目の走査: [3, 5, 1, 7, 2, 4, 0, 6, 8, 9]
- 3回目の走査: [3, 1, 5, 2, 4, 0, 6, 7, 8, 9]
- 4回目の走査: [1, 3, 2, 4, 0, 5, 6, 7, 8, 9]
- 5回目の走査: [1, 2, 3, 0, 4, 5, 6, 7, 8, 9]
- 6回目の走査: [1, 2, 0, 3, 4, 5, 6, 7, 8, 9]
- 7回目の走査: [1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
- 8回目の走査: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
シェーカーソートは、比較の回数が少ないため、要素数が少ない場合にはバブルソートよりも効率的です。しかし、要素数が多い場合にはクイックソートやマージソートなどのより高速なアルゴリズムが適しています。
Pythonでの実装例
以下がPythonでのシェーカーソートの実装例です。
def shaker_sort(arr): left = 0 right = len(arr) - 1 while left < right: for i in range(left, right): if arr[i] > arr[i+1]: arr[i], arr[i+1] = arr[i+1], arr[i] right -= 1 for i in range(right, left, -1): if arr[i-1] > arr[i]: arr[i], arr[i-1] = arr[i-1], arr[i] left += 1 return arr
このコードでは、left変数には配列の先頭のインデックス、right変数には配列の末尾のインデックスを初期値として設定します。次に、leftがrightより小さい間、以下の処理を繰り返します。
- 配列の先頭から末尾まで走査し、隣り合う2つの要素が順序通りでない場合は交換する。
- 配列の末尾から先頭まで走査し、隣り合う2つの要素が順序通りでない場合は交換する。
この処理を1回行うごとに、配列の先頭と末尾から1つずつ要素が正しい位置に移動します。つまり、配列が昇順に並び替えられると、先頭と末尾から1つずつ要素が正しい位置に移動するため、最終的に全体が昇順に並ぶことになります。
最後に、ソートされた配列を返します。
この実装では、内側のforループで配列の要素を比較し、必要に応じて交換しています。左右から走査するため、交互に隣り合う要素を比較することができ、比較回数を減らすことができます。
まとめ
シェーカーソートのメリットは、比較回数が少ないため、要素数が少ない場合にはバブルソートよりも効率的なことです。また、アルゴリズムがシンプルで実装しやすく、安定しています。ただし、要素数が多い場合には効率が悪く、他のアルゴリズムに比べて遅い可能性があります。また、実装が簡単な反面、空間効率が低く、大量のデータを扱う場合には注意が必要です。
