schedule2019-03-04

眺めていられるシェルソートのシミュレーション|JavaScript

シミュレーションが好きなので、一通りソートアルゴリズムを実装して眺めて見たい欲求に駆られました。

今回はシェルソートinsertion sort)です。 以前作った挿入ソートの改良版に当たります。

p5.jsで作りました。 是非、眺めてやって下さい。

ブラウザはChromeを推奨!

シェルソート (shell sort)

シェルソートはドナルド・シェルが開発した整列アルゴリズムです。 減少増分ソート(diminishing increment sort)とも呼ばれます。 挿入ソートは既に殆ど整列された配列で効率的に機能するのに対して、シェルソートはより一般化した方法になります。

シェルソートでは、適当な間隔を開けてアルゴリズムの最終ステップまで隣接要素を比較しないようにします。 比較整列アルゴリズムの中で、初めて計算量が2乗未満になった比較アルゴリズム。

  1. 適当な間隔 hhを決める
  2. 間隔 hhをあけて取り出したデータ列に挿入ソートを適用する
  3. 間隔 hhを狭めて、2.を適用する操作を繰り返す
  4. h=1h=1になったら、最後に挿入ソートを適用して終了

間隔hの決め方

hはデータ全体を満遍なくソート出来るように選びます。 例えば、h=4,2,1h=4, 2, 1と選ぶのは良くありません。 h=4h=4h=2h=2のときに並び替える要素が偶数、奇数で偏ってしまうためです。 10個の配列の時、array[0]を含む組み合わせはh=4h=4[0][4][8]h=2h=2[0][2][4][6][8]と重なります。 そこで、hhhi+1=3hi+1h_{i+1}=3h_i+1 となるように選んでいます。 大きさはh<=array.length/9h <= array.length/9としました。

計算量

種類 計算量
最悪計算量 間隔数列に依存する。最もよく知られている計算量:O(nlog2n)O(n \log^2 n)
最良計算量 O(n)O(n)
平均時計算量 間隔数列に依存する
最悪時空間計算量 O(n)O(n)

このアルゴリズムは中規模である程度正しい順序に整列したリストのソートに向いています。

シミュレーション

シェルソートでは比較する範囲がhの倍数に当たります。

  • 濃い黄色比較している高さ
  • 薄緑比較する範囲(hの間隔)

リスタートボタンで再度計算します。初期の配列は毎回ランダム。

最終的にh=1h=1となって挿入ソートをしていることが解ります。

シェルソートのコード

シェルソートの中核となるソースコードです。 最初にhを決めています。

// シェルソート
function shellSort(array) {
  let length = array.length;

  let i, j, h, v;
  // 1. 適当な間隔 hを決める
  for(h = 0; h <= length/9; h = 3*h+1);

  // 4. h=1になったら、最後に挿入ソートを適用して終了
  while(h > 0){
    // 2. 間隔 hをあけて取り出したデータ列に挿入ソートを適用する
    for(i = h; i <= length; i++){
      v = array[i];
      j = i;
      while(j >= h && array[j-h] > v){
        array[j] = array[j-h];
        j -= h;
      }
      array[j] = v;
    }
    // 3. 間隔 hを狭めて、2.を適用する操作を繰り返す
    h = Math.round(h/3);
  }
}

参考書のソースが間違っていたため少し苦労しました。

全体のソースコード

<!-- p5js -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.3/p5.min.js"></script>

<script src="/images/posts/105/shell-sort.js"></script>

<div>
  <div  class="center">配列長: <span id="length">30</span> &nbsp;
    比較回数:<span id="count">0</span>&nbsp;
  </div>
  <div class="center">
    <button type="button" class="button is-primary" onclick="restart();">リスタート</button>
  </div>
  <div id="canvas"  class="has-text-centered"></div>
</div>

<style>
.chart {
  width: 100%;
  height: 400px;
}
.center{
  text-align: center;
  margin: 10px;
}
</style>

shell-sort.js

今までと違って3段組にしている。

let map = [];
let count = 0; // 交換回数
let sorted = false;

// 再描画
function restart() {
  ini();
}

// 初期化
function ini() {
  let array = [];
  map = [];
  count = 0;
  frame = 0;
  sorted = false;

  let length = document.getElementById('length').innerHTML;
  length = parseInt(length);


  // 配列の初期化
  for (let i = 0; i < length; i++) {
    array.push(i + 1);
  }
  array = shuffle(array);

  // 先に交換順序を計算しておく。
  sorted = shellSort(array);
}

// 配列をシャッフル
function shuffle(array) {
  for (let i = array.length - 1; i >= 0; i--) {
    let rand = Math.floor(Math.random() * (i + 1));
    // 配列の数値を入れ替える
    [array[i], array[rand]] = [array[rand], array[i]]
  }
  return array;
}


// p5js
function setup() {
  let canvas = createCanvas(420, 400);
  canvas.parent('canvas');
  // フーレームレートを1/1secにする
  frameRate(10);
  background(color(212, 236, 234));
  // 描画を繰り返さない。
  ini();
}

let frame = 0;
function draw() {
  if (sorted && frame < map.length) {
    // canvasを更新
    background(color(212, 236, 234));

    // 描画
    let m = map[frame];
    drawBar(m.array, m.selected, m.swaped, m.selected_height, m.h, m.i);
    if(m.swaped){
      // 交換したターン
      document.getElementById('count').innerHTML = count > 0  ? count - 1 : 0;
      count++;
    }
    frame++;
  }
}


// バーを表示
function drawBar(array, selected, swaped, selected_height, m_h, m_i) {
  const under = 350;
  const grid_pixel = 10;
  const margin_left = 4;

  for (let i = 0; i < array.length; i++) {
    // gray
    let left = (grid_pixel + margin_left) * i + 2;
    let height = grid_pixel * array[i];

    // 枠線の色
    stroke(0, 0, 0);
    // 通常のバーの色
    fill(color(237, 235, 213));
    
    // rect(left, top, width, height);
    rect(left, under - height, grid_pixel, height);
    fill(color(50, 50, 50));
    rect(left, under - height, grid_pixel, grid_pixel);
    if(i <= m_i && (m_i - i)%m_h == 0){
      // 比較するバーの色
      fill(color(215, 231, 175));
      
      // rect(left, top, width, height);
      rect(left, under - height, grid_pixel, height);
      fill(color(50, 50, 50));
      rect(left, under - height, grid_pixel, grid_pixel);
    }
    // 比較する高さ
    if(selected === i){
      let height = grid_pixel * selected_height;

      fill(color(191, 164, 65));
      rect(left, under - height, grid_pixel, height);
      fill(color(50, 50, 50));
      rect(left, under - height, grid_pixel, grid_pixel);
    }
  }
}

// シェルソート
function shellSort(array) {
  let length = array.length;
  record(false, -1, -1, 0, length - 1 , array); // 初期状態

  let i, j, h, v;
  // 1. 適当な間隔 hを決める
  for(h = 0; h <= length/9; h = 3*h+1);


  // 4. h=1になったら、最後に挿入ソートを適用して終了
  while(h > 0){
    // 2. 間隔 hをあけて取り出したデータ列に挿入ソートを適用する
    for(i = h; i <= length; i++){
      v = array[i];
      j = i;
      while(j >= h && array[j-h] > v){
        array[j] = array[j-h];
        record(true, v, j-h, i, h , array); 
        j -= h;
      }
      array[j] = v;
      record(true, v, j, i, h , array); 
    }
    // 3. 間隔 hを狭めて、2.を適用する操作を繰り返す
    h = Math.round(h/3);
  }
  record(false, -1, -1, 0, length - 1 , array); // 終了状態
  return true
}

// 交換を記録する
function record(swaped, tmp, pivot, i, h, array) {
  map.push(
    {
      swaped: swaped, // 交換したか
      selected: pivot, // 比較している右側
      selected_height: tmp, // 比較している高さ
      i: i,
      h: h,
      array: array.concat(), // コピーして渡す
    });
}

眺めてられるシミュレーション

シリーズになってきた。 ひとまずソートアルゴリズムをどんどん作っていこう。

参考

アルゴリズムを体系的に学びたい方はオライリーの 入門データ構造とアルゴリズム がおすすめです。初版を持っているが、コードの間違いが少々目立つ点は残念。 ただ、解説と計算量が充実している。