schedule2019-01-23

眺めていられるクイックソートのシミュレーション|JavaScript

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

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

クイックソートなんていくらでも動画やgifがあるからいらないって?作ってみたいからいいんですよ。 p5.jsで作りました。 是非、眺めてやって下さい。

ブラウザはChromeを推奨!

クイックソート

クイックソートは分割統治アルゴリズムの一種です。

bunkasu

分割統治アルゴリズムは上図のように、配列を分割して細かくしながら問題を解決していく手法です。 この種のアルゴリズムの計算量はO(nlogn)O(n \log n)です。

クイックソートでは、要素から基準値(ピボット)を選びそれと比較して小さい要素を左大き要素を右へ交換して問題を小さく分割していきます。 (降順では左右を反対にする)

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

  1. 走査する配列長が0か1の場合戻る。
  2. 走査する範囲の中央の要素をピボットとして選ぶ。
  3. ピボットと比べ、大きい要素は左へ小さい要素は右へ交換する。
  4. 左右2つに配列を分割してこの関数を再帰的に繰り返す。

2のピボットを選ぶ基準は中央の要素でなくても良い。 参考書では右端でした。

シミュレーション

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

  • 黄色 : ピボット
  • 横棒 : ピボットの高さ
  • 青色 : 左の交換する要素
  • 赤色 : 右の交換する要素
  • うっすらと明るいのが走査範囲。

色はピボットを優先しているので、左右の交換する要素はわかりづらいかも。

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

O(nlogn)=44.31O(n \log n) = 44.31なので、大体あってるかな。

コード

中核となるアルゴリズムのコードがこちら。 手順と同じコメントをつけた。

// クイックソート
function quickSort(start, end, array) {
  if (end - start < 2) {
    // 1. 走査する配列長が0か1の場合戻る。
    return;
  }

  console.log(start, end);
  // 2. 走査する範囲の中央の要素をピボットとして選ぶ。
  let pivot = Math.floor((start + end) / 2);
  let pivot_height = array[pivot];
  // 走査範囲の左と右端を渡す
  let left = start;
  let right = end;


  while (left < right) {
    // 3. ピボットと比べ、大きい要素は左へ小さい要素は右へ交換する。
    while (array[left] < pivot_height) left++; // 左側の基準値より大きい位置まで移動
    while (array[right] > pivot_height) right--; // 右側の基準値より小さい位置まで移動

    if (left < right) {
      // 交換を記録する
      record(left, right, start, end, pivot_height, array);
      // leftがrightを超えていない場合、leftとrightを交換
      swap(left, right, array);
    } else {
      //leftがrightを超えたら走査範囲の比較を止める
      break;
    }
  }

  // 4. 左右2つに配列を分割してこの関数を再帰的に繰り返す。
  quickSort(start, left - 1, array);
  quickSort(right, end, array);

  return true;
}


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

record()は要素の交換順序を記録するための関数。 全て計算してからp5.jsで描画している。

  1. のピボットを選ぶ方法は末端でもよい。
// 2. 走査する範囲の末端の要素をピボットとして選ぶ。
  let pivot = end;
  let pivot_height = array[pivot];

クイックソートの計算量

クイックソートの平均計算量はO(nlogn)O(n \log n)です。 しかし、最大または最小値をピボットとして選び続けると最悪O(n2)O(n^2)になってしまいます。

ちょうど半分に分割していく方が計算量が少なくなるため、走査範囲の中央値メディアン)をピボットとして選びたい。 改善案としては、配列からランダムに3つ選びその中央値をピボットとする方法もある。

p5.jsで描画する

p5.jsのコードが複雑になってしまった。 ソート順序を全て計算してからp5.jsで描画している。

html

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

<script src="/images/posts/68/quicksort.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>

quicksort.js

quickSort()swap()を省略してる。 mapに交換した記録を格納して、draw()で描画している。

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

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

// 初期化
function ini() {
  let array = [];
  map = [];
  count = 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);

  let pivot = Math.floor((array.length - 1) / 2);
  let pivot_height = array[pivot];
  record(null, null, 0, length - 1, pivot_height, array);

  // 先に交換順序を計算しておく。
  sorted = quickSort(0, array.length - 1, array);
  // ソート完了
  record(null, null, -100, 0, -10000, array);
  console.log(map);
}

// 配列をシャッフル
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(1);
  background(color(212, 236, 234));
  // 描画を繰り返さない。
  ini();
}

let swither = 0;
function draw() {
  if (sorted && count < map.length) {
    // canvasを更新
    background(color(212, 236, 234));
    let m = map[count];
    drawRnage(m.range);
    drawBar(m.array, m.pivot_height, m.swap);
    drawHeight(m.range, m.pivot_height);
    document.getElementById('count').innerHTML = count > 0  ? count - 1 : 0;
    count++;
  }
}

// 比較する高さを描画
function drawHeight(range, height) {
  const grid_pixel = 10;
  const margin_left = 4;
  const y = 350 - (grid_pixel * height) + 5;
  let left = (grid_pixel + margin_left) * range.srart + 2;
  let width = (grid_pixel + margin_left) * (range.end - range.srart + 1);

  stroke(126);
  line(left, y, left + width, y);
}

// 走査範囲を表示
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, pivot_height, 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 (array[i] === pivot_height) {
      // 基準値の色 バーの色
      fill(color(191, 164, 65));
    } else if (i === swap.left) {
      // 左交換の色 バーの色
      fill(color(65, 156, 192));
    } else if (i === swap.right) {
      // 右交換の色 バーの色
      fill(color(191, 65, 155));
    } else {
      // バーの色
      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);
  }
}



// クイックソート
function quickSort(start, end, array) {
  // 省略
}


// 配列の要素を交換する
function swap(left, right, array) {
  // 省略
}

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

終わりに

アルゴリズムの構築は楽だったが、p5jsで描画するのに苦戦した。 先に計算せず、一コマずつdraw()関数の中で計算していこうとしたがあかんかった。 noLoop()redraw()setTimeout()でも躓いている。

p5jsについてもう少しまとめていくか。

おまけ

途中で配列をシャッフルしてバーを描画するだけのものが生み出されたので、 記念にgifを残しておく。

random_bar

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

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

参考

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