「●双方向バブルソート」の編集履歴（バックアップ）一覧はこちら
「●双方向バブルソート」(2009/05/31 (日) 17:26:11) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*情報
作者名：ゆちボン
引用元：[[なでしこプログラム掲示板「なでしこでソートプログラム集」>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()
----
*情報
作者名：ゆちボン
引用元：[[なでしこプログラム掲示板「なでしこでソートプログラム集」>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()
----
