schedule2019-02-11

眺めていられる数え上げソートのシミュレーション|JavaScript

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

今回は数え上げソートinsertion sort)です。 以前作ったクイックソートバブルソートと原理が異なるので視覚化に悩みましたが、わかりやさを優先で作ってみます。

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

ブラウザはChromeを推奨!

数え上げソート (counting sort)

数え上げソートは要素の比較をせずに並び替えます。 整列の計算量はO(n)O(n)と性能も良いですが、整列する要素が1からKの整数であるという前提のもと成り立ちます。

基本的な考え方は、要素XXに対してXX未満の要素の数を数えて、その情報を元に要素の順番を決めます。 例えば、要素XX未満の数が10あるなら、XXは11番目になります。

整列する配列Aの他に2つの配列を使います。 並べ替えた出力の配列Bと、一時的に要素の情報を格納する配列Cです。 配列Cの長さは、配列Aの要素の最大値Kの長さです。

  • 計算量はO(n)O(n)
  • 要素未満の数を数えて順序を決める
  • 配列を3つ
    • 並べ替える配列A
    • 出力の配列B
    • 一時的な配列C
  • 配列Cの長さは要素の最大値K

これを改良したものに、バケットソートがある。

シミュレーション

わかりやすくするため、これまでと前提を変えます。

1から30までのランダムな値を持つ配列Aを並べ替えます。 3段に表示して、上からA, C, Bの配列です。

  • 1段目:並べ替える配列A
  • 2段目:一時的な情報の配列
  • 3段目:出力の配列
  • 赤色:アクセスしている要素

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

数え上げソートのコード

数え上げソートの中核となるソースコードです。 for文がいくつかありますが、1重なので計算量がO(n)O(n)であることが解ります。

// 数え上げソート
function countingSort(A) {
  // 要素の最大値
  let K = max(A);
  let length = A.length

  // 出力配列
  let B = new Array(length).fill(0);
  // 1~Kを格納する一時保存配列
  let C = new Array(K+1).fill(0);
  
  for(let i = 0; i < length; i++){
    // 値ごとの個数を数える
    C[A[i]] = C[A[i]] + 1;
  }

  for(let j = 1; j < K+1; j++){
    // その値未満の個数を計算
    C[j] = C[j] + C[j-1];
  }
  
  for(let i = length - 1; i >= 0; i--){
    // AからBへ適切な番号へ要素を渡す
    B[C[A[i]] - 1] = A[i];
    C[A[i]] = C[A[i]] - 1;
  }

  return true
}

配列Cで1からKの整数を取り扱うため、CはK+1K+1の長さにしている。

全体のソースコード

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

<script src="/images/posts/89/counting-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>

counting-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(getRandomInt(length));
  // }
  // 配列の初期化
  for (let i = 0; i < length; i++) {
    array.push(i + 1);
  }
  array = shuffle(array);

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

function getRandomInt(max) {
  // ランダムな配列
  return Math.ceil(Math.random() * Math.floor(max));
}

// 配列をシャッフル
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(434, 800);
  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.A, m.a, 350);
    drawCounter(m.C, m.c);
    drawBar(m.B, m.b, 750);
    frame++;
    document.getElementById('count').innerHTML = count > 0  ? count - 1 : 0;
    count++;
  }
}

// バーを表示
function drawBar(array, selected, under) {
  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];

    if(array[i] === 0){
      fill(color(50, 50, 50));
      rect(left, under, grid_pixel, 1);
      continue;
    }

    // 枠線の色
    stroke(0, 0, 0);
    // 通常のバーの色
    fill(color(237, 235, 213));
    if(selected === i){
      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 drawCounter(array, selected){
  const under = 425;
  const grid_pixel = 12;
  const margin_left = 2;

  textSize(8);
  for (let i = 0; i < array.length; i++){
    let left = (grid_pixel + margin_left) * i + 2;
    let height = under - grid_pixel;
    noStroke();
    fill(color(237, 235, 213));
    if(i === selected){
      fill(color(191, 65, 155));
    }
    rect(left, under - grid_pixel * 2 + 1, grid_pixel, grid_pixel + 2);

    // 数値
    fill(50)
    text(str(array[i]), left + 2, height);
  }
}

// 数え上げソート
function countingSort(A) {
  // 要素の最大値
  let K = max(A);
  let length = A.length

  // 出力配列
  let B = new Array(length).fill(0);
  // 1~Kを格納する一時保存配列
  let C = new Array(K+1).fill(0);

  record(A, -1, B, -1, C, -1);
  
  for(let i = 0; i < length; i++){
    // 値ごとの個数を数える
    C[A[i]] = C[A[i]] + 1;
    record(A, i, B, -1, C, A[i]);
  }

  for(let j = 1; j < K+1; j++){
    // その値未満の個数を計算
    C[j] = C[j] + C[j-1];
    record(A, -1, B, -1, C, j);
  }
  
  for(let i = length - 1; i >= 0; i--){
    // AからBへ適切な番号へ要素を渡す
    B[C[A[i]] - 1] = A[i];
    C[A[i]] = C[A[i]] - 1;
    record(A, i, B, C[A[i]] - 1, C, A[i]);
  }

  record(A, -1, B, -1, C, -1);
  return true
}

function record(A, a, B, b, C, c){
  // 各配列の記録
  map.push({
    A : A.slice(),
    a : a,
    B : B.slice(),
    b : b,
    C : C.slice(),
    c : c
  });
}

初めて文字列を使った。 下のような使い方で文字列も出力できる。

textSize(8);
  // 数値
  fill(50)
  // text('text', left, height);
  text('text', 10, 10);

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

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

参考

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