●双方向バブルソート

情報

作者名：ゆちボン
引用元：なでしこプログラム掲示板「なでしこでソートプログラム集」
解説引用元：http://ja.wikipedia.org/wiki/バブルソート
解説引用元：http://ja.wikipedia.org/wiki/シェーカーソート
リンク：●コムソート、●バブルソート、●おいこみソート

概要

双方向バブルソートは、ソートのアルゴリズムの一つ。別名「シェーカーソート(Shaker sort)」。
バブルソートを、効率がよくなるように改良したもの。
バブルソートではスキャンを一方向にしか行わないのに対し、双方向バブルソートでは交互に二方向に行う。
バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n2)である。

安定：●
速度：最低で、o(n^2)

サンプルプログラム

200回、テスト[回数-1]は乱数(200)
テストを双方向バブルソート。
テストをメモ記入。
おわり

//本体

●双方向バブルソート(Aを)
　min=0
　max=配列要素数(A)
　1の間
　　'順方向からスキャン
　　lastswap=min
　　i=min
　　(i<max)の間
　　　もし、A[i]>A[i+1]なら
　　　　tmp=A[i]
　　　　A[i]=A[i+1]
　　　　A[i+1]=tmp
　　　　lastswap=i
　　　i=i+1
　　'最大値の変更
　　max=lastswap
　　もし、min=maxなら、抜ける
　　'逆方向のスキャン
　　i=max
　　(i>min)の間
　　　もし、A[i]<A[i-1]なら
　　　　tmp=A[i]
　　　　A[i]=A[i-1]
　　　　A[i-1]=tmp
　　　　lastswap=i
　　　i=i-1
　　'最小値の変更
　　min=lastswap
　　もし、min=maxなら、抜ける
　Aで戻る。

---

---