●双方向バブルソート

「●双方向バブルソート」の編集履歴（バックアップ）一覧に戻る

---

「●双方向バブルソート」を以下のとおり復元します。

---

*情報
作者名：ゆちボン
引用元：[[なでしこプログラム掲示板「なでしこでソートプログラム集」>http://www.himanavi.net/cgi/nade-bbs/cbbs.cgi?mode=al2&namber=940&rev=&no=0]]
解説引用元：[[http://ja.wikipedia.org/wiki/バブルソート>http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88]]
解説引用元：[[http://ja.wikipedia.org/wiki/シェーカーソート>http://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%BC%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%BC%E3%83%88]]

*概要
双方向バブルソートは、ソートのアルゴリズムの一つ。別名「シェーカーソート(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で戻る。

----
#comment()

----

---

復元してよろしいですか？