低速アルゴリズム

  

シェーカーソート

 シェーカーソートは、基本原理はバブルソートを用いる。
バブルソートの場合、常に左から右へ比較を行い右側に最大値をもってきている。シェーカーソートは、左から右へ比較を行い最大値を固定した後は、逆に右から左へ比較を行い最小値を左側に固定する。この操作を繰り返し行なうことにより、データの並べ換えを実現する。理解を深めるために、下記に例を示そう。


  49   66   11   37   84   6   22   73
まず、左から右へバブルソートを行い、一番右側に最大値を固定する。  

 49   11   37    66   6   22   73   84
  
次に、固定した84を除いて、右から左へ向かってバブルソートを行なう。

  6   49   11   37   66   22   73   84
すると、一番左側に最小データが固定される。つづいて、固定された6と84を除いて左から右へ向かってバブルソートを行なう。

 6   11   37   49   22   66   73   84
73が84を除いた最大値として固定される。さらに、右から左へ向かってバブルソートを行なう。

 6   11   22   37   49   66   73   84
11が6を除いた最小値として固定される。以下、上記操作を繰り返しおこなう。


  6   11   22   37   49   66   73   84

  6   11   22   37   49   66   73   84

  6   11   22   37   49   66   73   84

  6   11   22   37   49   66   73   84

上記例では、固定された数値には赤色を付けて、固定される順番がわかりやすくした。

戻る

アプレットに戻る

a93sj030@j.dendai.ac.jp