シェアソート

シェアソート（英: shear-sort）は、ソートのアルゴリズムの一つ。シェアソートでは、データを長方形に並べた上で、各行／各列ごとにソートを行なう。1989年に Isaac D. Scherson らが発表した。安定ではない内部ソートであり、最悪の場合の時間計算量はO(n^1.5)である。各行／各列の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。

アルゴリズム

シェアソートの手順は、${\displaystyle 2\left\lceil \left(\log _{2}{\sqrt {n}}\right)\right\rceil 1}$回の段階に分けられる。

• 奇数番目の段階(1,3,5,7･･･番目の段階)
  • 行ごとに、奇数行目は左側が小さく、偶数行目は右側が小さくなるようにソートする。
• 偶数番目の段階(2,4,6,8･･･番目の段階)
  • 列ごとに、上が小さくなるようにソートする。
• 最後の段階
  • 行ごとに、左側が小さくなるようにソートする。

実装例

動作例

初期データ:

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。

列ごとに上が小さくなるようにソートする。

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。

列ごとに上が小さくなるようにソートする。

奇数行目は左が小さく、偶数行目は右が小さくなるようにソートする。

列ごとに上が小さくなるようにソートする。

最後に、行ごとに左が小さくなるようにソートするとソートが完了する。

関連項目

• 奇偶転置ソート

参照

外部リンク

• Sorting Algorithm Demo