schedule2019-01-28

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

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

今回はバブルソートを改良したシェーカーソートです。 クイックソートバブルソートに引き続き、ぼーっとできるシミュレーションを作りました。

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

ブラウザはChromeを推奨!

シェーカーソート (shaker sort)

バブルソートは隣り合う要素を一方向へ比較しながら整列させていくソート方法でした。 シェーカーソートでは、交互に2方向へスキャンしながらソートしていきます。

交互にスキャンする様子が、カクテルを作るシェーカーに似ていることにちなんだ名前でしょうか。

今回実装した手順は、以下の通りです。

  1. 以下の手順を繰り返す
    1. 順方向に隣り合う要素を比較する。
    2. 左が右の要素に比べ大きい場合交換。
    3. 後方の走査範囲をひとつ狭める。
    4. 走査範囲が0になったらループを抜ける。
    5. 逆方向に隣り合う要素を比較する。
    6. 左が右の要素に比べ大きい場合交換。
    7. 前方の走査範囲をひとつ狭める
    8. 走査範囲が0になったらループを抜ける。

1-1.から1-3が順方向、1-5.から1-7が逆方向の走査です。 1-2.1-6.の交換を小さい場合にすると、降順になります。

シミュレーション

早速、どんな風にソートしているか眺めてみましょう。

  • 黄色 : 比較する要素
  • 青色 : 左の交換する要素
  • 赤色 : 右の交換する要素
  • うっすらと明るいのが走査範囲。

赤と青が出たら交換しているんだなーと思っていただければ良いです。

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

交互に走査しているのがわかります。

改良案

収束が早いので最後の方の走査は空回りしています。 最後に交換した位置まで範囲を狭めていくと、空回りせずに済みます。

もしくは一回の走査で交換がない場合にbreakする手もあります。

シェーカーソートのコード

逆方向の処理があるため、バブルソートに比べコードが長い。

// シェーカーソート
function shakerSort(array) {
  let length = array.length;
  // 走査範囲の初期値
  let start = 0;
  let end = length - 1;

  // 1. 以下の手順を繰り返す
  while(true){
    // 1. 順方向に隣り合う要素を比較する。
    for(let i = start; i < end; i++){
      if(array[i] > array[i + 1]){
        // 2. 左が右の要素に比べ大きい場合交換。
        swap(i, i+1, array);
      }
    }
    // 3. 後方の走査範囲をひとつ狭める。
    end--;
    // 4. 走査範囲が0になったらループを抜ける。
    if(start === end) break;

    // 5. 逆方向に隣り合う要素を比較する。
    for(let i = end; start < i; i--){
      if(array[i-1] > array[i]){
        // 6. 左が右の要素に比べ大きい場合交換。
        swap(i-1, i, array);
      }
    }
    // 7. 前方の走査範囲をひとつ狭める
    start++;
    // 8. 走査範囲が0になったらループを抜ける。
    if(start === end) break;
  }
}

// 配列の要素を交換する
function swap(left, right, array) {
  let tmp = array[left];
  array[left] = array[right];
  array[right] = tmp;
}

3.と7.を最後に交換した位置まで狭めてあげると空回りが減ります。

コードの全容

p5jsでの描画も含めたコードの全容です。

HTML

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

<script src="/images/posts/75/shaker-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>

JavaScript

shaker-sort.js

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 = shakerSort(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];
    drawRnage(m.range);
    drawBar(m.array, m.selected, m.swaped, m.swap);
    if(m.swaped){
      // 交換したターン
      document.getElementById('count').innerHTML = count > 0  ? count - 1 : 0;
      count++;
    }
    frame++;
  }
}

// 走査範囲を表示
function drawRnage(range) {
  const grid_pixel = 10;
  const margin_left = 4;

  // gray
  let left = (grid_pixel + margin_left) * range.srart + 2;
  const under = 20;
  let width = (grid_pixel + margin_left) * (range.end - range.srart + 1);
  let height = 360;

  stroke(222, 246, 244);
  fill(color(222, 246, 244));
  rect(left, under, width, height);
}

// バーを表示
function drawBar(array, selected, swaped, swap) {
  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);
    if (i === selected) {
      // 基準値の色 バーの色
      fill(color(191, 164, 65));
    }else {
      // バーの色
      fill(color(237, 235, 213));
    }
    if(swaped){
      // 交換
      if (i === swap.left) {
        // 左交換の色 バーの色
        fill(color(65, 156, 192));
      } else if (i === swap.right) {
        // 右交換の色 バーの色
        fill(color(191, 65, 155));
      }
    }
    // 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);
  }
}



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

  let start = 0;
  let end = length - 1;

  while(true){
    // forward
    for(let i = start; i < end; i++){
      let swaped = false;
      if(array[i] > array[i + 1]){
        swap(i, i+1, array);
        swaped = true;
      }
      record(swaped, i, i+1, start, end, array);
    }
    end--;
    if(start === end) break;
    // backward
    for(let i = end; start < i; i--){
      let swaped = false;
      if(array[i-1] > array[i]){
        swap(i-1, i, array);
        swaped = true;
      }
      record(swaped, i-1, i, start, end, array);
    }
    start++;
    if(start === end) break;
  }

  record(false, -1, -1, 0, length - 1 , array); // 終了状態
  return true
}


// 配列の要素を交換する
function swap(left, right, array) {
  let tmp = array[left];
  array[left] = array[right];
  array[right] = tmp;
}

// 交換を記録する
function record(swaped, left, right, start, end, array) {
  map.push(
    {
      array: array.concat(), // コピーして渡す
      range: { // 走査範囲
        srart: start,
        end: end,
      },
      selected: right, // 比較している右側
      swaped: swaped, // 交換したか
      swap: {  // 交換記録
        left: left,
        right: right
      }
    });
}

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

シリーズにしていきたい。

参考

アルゴリズムを体系的に学びたい方はオライリーの 入門データ構造とアルゴリズム がおすすめです。