●双方向バブルソート

※上記の広告は60日以上更新のない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で戻る。


名前:
コメント:


ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。