schedule2019-01-28

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

simulationアルゴリズムJavaScriptp5js

私は書いたコードのログが流れてるところをぼーっと眺めるのが好きです。シミュレーション途中のグラフや画像が変わっていくのも大好きです。

そんな訳で、前回のクイックソートに引き続きぼーっとできるシミュレーションを作りました。今回はアルゴリズムの基礎からバブルソートのシミュレーションです。

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

ブラウザはChromeを推奨！

バブルソート

バブルソートは隣り合う要素を比較しながら整列させていくソート方法。

バブルは泡の意味で、並べ替えの過程で下から上へ要素が移動していく様を表しています。実際にシミュレーションを見てみると、その様がわかる気がしてきます。

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

後ろから順に隣り合う要素を比較する。
左が右の要素に比べ大きい場合交換。
走査範囲を前からひとつ狭める

3.は走査範囲の中で一番小さい値が先頭に来て比較が不要になるため、範囲を狭めています。 2.の交換を小さい場合にすると、降順になります。

シミュレーション

とりあえず、どんな風にソートしているか眺めてみましょう。

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

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

リスタートボタンで再度計算します。

左から順に値が決まっていくのがわかります。また、交換回数がかなり多い。

バブルソートのコード

クイックソートと比べてかなりスッキリとしたコードになりました。２重のfor文になっています。内部のfor文は、後ろから操作するためindexを１ずつ減らしています。

// バブルソート
function babbleSort(array) {
  let length = array.length;

  for(let i = 0; i < length; i++ ){ // 3. 走査範囲を前からひとつ狭める
    for(let j = length - 1; i < j; j--){
      // 1. 後ろから順に隣り合う要素を比較する。
      if(array[j-1] > array[j]){
        // 2. 左が右の要素に比べ大きい場合交換。
        swap(j-1, j, array);
      }
    }
  }
}


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

外側のfor文を無くして１重にすることも可能ですが、比較が不要になった範囲も走査してしまうため無駄が生じます。

シミュレーション用のコードは所々に配列の記録用の関数を使っています。

コードの全容

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/babblesort.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

babblesort.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 = babbleSort(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 babbleSort(array) {
  let length = array.length;
  record(false, -1, -1, 0, length - 1 , array); // 初期状態

  for(let i = 0; i < length; i++ ){ // 3. 走査範囲を前からひとつ狭める
    for(let j = length - 1; i < j; j--){
      // 1. 後ろから順に隣り合う要素を比較する。
      let swaped = false;
      if(array[j-1] > array[j]){
        // 2. 左が右の要素に比べ大きい場合交換。
        swap(j-1, j, array);
        swaped = true;
      }
      record(swaped, j-1, j, i, length - 1 , array);
    }
  }
  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
      }
    });
}