
COVID-19が世界中に拡大していき、各国・地域が対応を迫られる中、
ワシントン・ポストからアウトブレイクに対する戦略を比較したシミュレーションが出された。

[コロナウィルスなどのアウトブレイクは、なぜ急速に拡大し、どのように「曲線を平らにする」ことができるのか | The Washington Post](https://www.washingtonpost.com/graphics/2020/health/corona-simulation-japanese/)

[英語版](https://www.washingtonpost.com/graphics/2020/world/corona-simulator/)

このシミュレーションは、戦略がアウトブレイク曲線にどのような影響を与えるかを示している。
シミュレーションはシンプルで現実に即していないかもしれないが、戦略の影響が直感的にわかりやすい。
内容に関しては、ワシントン・ポストの記事を読んでください。

このシミュレーションを見て、別の条件を加えた場合どうなるかいくつかのアイデアが浮かびました。
この記事ではアイデアを検証するため、アウトブレイクのシミュレーションを再現しアイデアを加えています。
また、読んでくださった方が更にアイデアを加えられるようにコードを公開しています。

シミュレーターには[p5.js](https://p5js.org/)を利用しました。
p5.jsはブラウザ上でアニメーションを描画できるライブラリであり、言語はJavaScriptです。
公式サイトにはすぐに実行できるエディターも用意されています。

元記事でも、同じか似たライブラリを利用していると思われるがコードが見つからなかったのと、自身の勉強のため１からコードを書いた。
そのため、細部のパラメータや挙動は全て再現しているわけではありません。
ご了承願います。

## アウトブレイクのシミュレーション

元記事に倣い偽の病気シミュライタスがアウトブレイクする様子を再現します。

このシミュライタスは健康な人が感染している人と接触すると、この健康な人へ感染する。
病気に罹った感染者は時間が経過すると回復する。
回復した人から健康な人へ感染することも、感染者と接触したことで再度感染することもない。

人口200人の町でシミュライタスの感染が拡大する様子です。
住人をランダムに配置して、無作為に移動させます。
最初の感染者は１人です。

![usually](https://github.com/suzu6/outbreak_models/blob/master/gif/usually.gif?raw=true)

[github](https://github.com/suzu6/outbreak_models) / 
[p5.js](https://editor.p5js.org/y.suzumura0604/sketches/xaCz-uRPG)

元記事と異なりgif形式で申し訳ないが、ある程度再現できた。
住人同士が接触したときの動きがおかしいので後で修正します。

このシミュレーションでは感染に対応しなかった場合の患者数の曲線を示しています。
感染に対する対応を取った場合にこの曲線がどのように変化するか、次からのシミュレーションと比較していきます。

## 社会距離戦略を取った場合

ひとつ、元記事にある戦略を再現しました。

感染拡大を抑えるため、公共の場への移動を控え他人と接触する機会が少なるよう人々が行動した場合です。
人口の4分の3が受け入れ、残りの4分の1が継続的に移動を続けたときの影響です。

![stay_75](https://github.com/suzu6/outbreak_models/blob/master/gif/stay_75.gif?raw=true)

多少条件が異なるため元記事ほど低く抑えることはなかったが、感染者数が増加する前に回復した人も増えていき曲線はなだらかです。感染を押さえ込めているように見える。

## 集会が与える影響

この条件から元記事にはない私のアイデアです。

新型コロナウイルスは密閉された空間で空気感染するとも言われています。
とある空間で集会があった場合の影響を可視化してみます。
ただし、シミュライタスは接触感染しか実装していないため次のような枠を用意しました。

この町の真ん中に枠を置く。
この枠は外からは入れるが、中からは出られません。
枠の外の住人は自由に動いているため枠の中に入り、枠の中の人口密度が上がっていく。
一定時間が経過すると枠が消え、住人はもとのように自由に動き回る。

感染者はこの枠の中からスタートする。

![convention](https://github.com/suzu6/outbreak_models/blob/master/gif/convention.gif?raw=true)

まず枠内で感染が拡大し、枠を開放した後に感染者数の伸びが増えています。
通常と比べ曲線のピークは大きく変わりませんが、曲線の傾きが比較的大きい箇所が２段階ある。

初期の新規感染者の増加を抑えることが、曲線をなだらかにすることにつながります。
このシミュレーションでは集会内での感染増加と感染した参加者からの２次感染の様子を示唆していると考えています。

## 地域間の移動を制限した場合

地域・国家間の移動を制限した場合をシミュレーションしてみる。

集会で利用した枠を複数用意して地域と見立てる。
格子状に９つの地域があり、この地域間の移動を制限します。
枠から外へ出られる確率を設定する。
外から内側へは自由に入れる。

地域間の移動を1割まで制限した様子です。

![local](https://github.com/suzu6/outbreak_models/blob/master/gif/local.gif?raw=true)

感染者数の曲線がなだらかになりました。
感染源に距離的に近い地域へ感染が広がっていく様子がわかります。
感染者が居ない地域が最後まで複数残っており、そこは感染源から遠い地域です。
感染源は一つですが位置はランダムでです。

この戦略では、曲線を抑えられることに加えウイルスが拡大するルートを予測することができます。
他の地域と交流が多い中央の地域が感染すると止めることが難しそうです。
無症状者が多くいる病状の場合は経路が推測しやすいため効果的な戦略だと思います。

## 患者が行動を抑えた場合

感染者の隔離、もしくは自発的に自宅待機した場合をシミュレーションしてみます。

感染者は接触の機会を抑えるため、その場で留まり移動を制限する。
他の健康な人と回復した人は変わらず自由に移動する。
また、感染者の内2割が無自覚であり感染期間中も他と同じように自由に移動をするとします。

![pcr](https://github.com/suzu6/outbreak_models/blob/master/gif/pcr.gif?raw=true)

制限がない場合に近い曲線になりました。
感染者の2割が無自覚でも、予想以上に増加数が大きいです。

このシミュレーションだと無自覚感染者からよりも、停止している感染者に向かった健康な人が感染する場合が多いように見えます。
感染者が固まっている場所は、健康な人が感染者に接触しに行ったところ。
また、最初の感染者が端に居る場合のシミュレーションでは、曲線がもっと平らになります。
現実で自宅待機ないし隔離している方に接触する機会はもっと少なくなるため、曲線も更に平坦になるはずです。

## 感染確率を導入する

新型コロナウィルスは感染確率は比較的高いですが、このシミュライタスのように接触したら確実に感染するわけではありません。
次のシミュレーションでは感染確率を取り入れてみます。

感染者と接触した場合に３割の確率で感染するとする。
つまり、１回の接触で感染することもあれば何度接触しても感染しない人もいる。
接触回数が多い人は感染する確率が高くなります。

![infection_rate30](https://github.com/suzu6/outbreak_models/blob/master/gif/infection_rate30.gif?raw=true)

感染率100%に比べ当たり前ですが曲線はなだらかです。
ただし、感染者数が３割以上になると接触する回数も増えるため、増加数も高くなります。
プログラムの不備でごちゃごちゃ接触している住人も居ますが、全体的な傾向としては概ね予想通りです。

では、感染率はこのままにして、集会がある場合を見てみます。
集会を模した枠は以前のものと同じです。

![infection_rate30_convention](https://github.com/suzu6/outbreak_models/blob/master/gif/infection_rate30_convention.gif?raw=true)

感染率100%に近い曲線になりました。
枠内の密集地域では接触回数が外よりも増え、短い間に半数が感染しました。
それらの感染者が外に出たことで、他の健康な人へも感染が拡大しているようすがわかります。

これらの結果から、２つのことが言えそうです。
感染確率が低くても感染者数が一定の割合を超えると増加量も高まる。
また、集会など密集地域では感染者との接触回数が増え感染する確率も高い。

## コードについて
コードはMITライセンスで公開しているので自由に使ってください。

[github](https://github.com/suzu6/outbreak_models) / 
[p5.js](https://editor.p5js.org/y.suzumura0604/sketches/xaCz-uRPG)

p5.jsでは左上の三角をクリックしたら実行できます。
編集や保存してもオリジナルのファイルは変わらないので好きなだけいじってください。

これまで示したシミュレーションは全てパラメータをいじれば再現できます。
最初の`setup()`関数に各パラメータの変数があるのでそれを変えてみてください。
各シミュレーションの設定値やコメントは後で追記するはずです。
先にブラウザで実行できるようにします。
接触がごちゃごちゃするなど、いくつかバグもあるので修正を募集もしてます。


## おわりに

元記事にいくつかのアイデアを加えシミュレーションしてみました。
シミュレーションから得た結果は、受け取り方は各人様々でしょうが、ごく当たり前のことだと思います。
もちろんこのシミュレーションはとてもシンプルなもので、現実に即しているとは言えません。
ただし、当たり前のことも定量的に示せばより精度の高い予測や次の議論へと発展すると期待しています。

この記事を書いたのは、医療や感染症の専門知識を持たないただのプログラマーです。
シミュレーション結果のそれぞれひとつをgifとして掲示しています。
ランダムなパターンの内、恣意的な抽出をしてそれを元に意見を書いているおそれがあります。
所属とは関係なくこのサイトに関する全ては個人の責任です。

[twitter](https://twitter.com/suzu6_py/status/1241280986047901697)

以上、最後までご覧頂きありがとうございます。


コロナウイルスなどがアウトブレイクする様子のシミュレーションをp5jsで作成した

P5jsを使ってk-meansのクラスタリング過程の可視化に挑戦しました。
また、とてもざっくりとした解説を載せます。


## k-meansとは？

データを与えられたk個のクラスタに分類するアルゴリズムです。

クラスタリングする手順は一般的に以下の通り。

1. データをランダムにk個のクラスターに割り振る。
2. クラスターの中心を求める。
3. 各クラスタの中心との距離を求め、一番近い中心のクラスタに割り振ります。
4. 2と3を繰り返してクラスターが変動しなくなれば終了。


step2とstep3のイメージ

![step2](/images/posts/115/step2.png)

step2からstep3へクラスタが更新している。

## k-meansの長短

機械学習の中では**教師なし学習**にあたります。
つまり、ラベル付けなどの作業をしなくても良い感じにデータを分けてくれます。

ただし、以下の点に注意が必要です。

- 最終的なクラスタは初期値に依存する。
- クラスタ数がデータに合わないことがある。

ここでは簡単な説明にとどめます。以下の記事が詳しく解説しています。

- [K meansによるクラスタリングの解説と具体的なクラスタリングの活用方法の紹介](https://www.slideshare.net/takemikami/k-means-55567232)
- [【教師なし学習・クラスタリング】K-means](https://www.hellocybernetics.tech/entry/2017/07/01/091431)

### シミュレーション

実際に動かして体験してみましょう。


**リセット**を押すと大体600個ほどの点群が出来ます。
**ステップ**を押すと「シードの移動」と「クラスタリング」を繰り返して収束していきます。



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

<script src="/images/posts/115/k-means.js"></script>

<div class="p5js">
  <div class="center">
    <button type="button" class="button" onclick="retry();">リトライ</button>&nbsp;
    <button type="button" class="button is-primary" onclick="step();">▶ ステップ</button>&nbsp;
  </div>
  <div  class="center">
    シード数：<span id="count">3</span>&nbsp;
  </div>
  <div id="canvas"  class="has-text-centered"></div>
  <div class="center" id="parameters"></div>
</div>


<style>
.p5js .center{
  text-align: center;
  margin: 10px;
}
.p5js .button{
  text-align: center;
  margin: 10px;
}
</style>

それぞれのクラスターのサイズと位置(x, y)、クラスタ数を表示ししています。

初期配置は`1. データをランダムにk個のクラスターに割り振る。`ではなく、ランダムに初期の点を置いています。
データセットは、前回作成した[２次元の混合分布](https://www.suzu6.net/posts/98-p5js-gaussian)を使ってそれっぽい分布にしています。


## ソースコード全文

読みづらくて申し訳ない。

キャンバスと表示制御部分のhtml

```html

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

<script src="/images/posts/115/k-means.js"></script>

<div class="p5js">
  <div class="center">
    <button type="button" class="button" onclick="retry();">リトライ</button>&nbsp;
    <button type="button" class="button is-primary" onclick="step();">▶ ステップ</button>&nbsp;
  </div>
  <div  class="center">
    シード数：<span id="count">3</span>&nbsp;
  </div>
  <div id="canvas"  class="has-text-centered"></div>
  <div class="center" id="parameters"></div>
</div>


<style>
.p5js .center{
  text-align: center;
  margin: 10px;
}
.p5js .button{
  text-align: center;
  margin: 10px;
}
</style>
```

[k-means.js](http://www.suzu6.net/images/posts/115/k-means.js)

```js
let data = []; // 分類したデータ
let points = []; // 全てのポイント
let seeds = [];

let frame_rate = 10;
let parameter = [];

let canvas_size = {
  width: 400, height: 400
} //px

let bg_color = '#FFFCDB';
let cluster_colors = ['#A40000', '#0075A9', '#007130', '#A4005B', '#B7AA00', '#100964'];

let cluster_size = 3;
let next_step_flg = false;

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

// step
function step() {
  drawView();
}

// 初期化
function ini() {
  parameter = [];
  seeds = iniSeed();
  background(color(bg_color));

  data = createData();
  points = join_dataset(data);
  data = [points];
  drawCluster();
  next_step_flg = true;
}


// シードの初期値
function iniSeed() {
  array = new Array(cluster_size);
  for (let i = 0; i < cluster_size; i++) {
    let x = random(0, canvas_size.width);
    let y = random(0, canvas_size.height);
    array[i] = [x, y];
  }
  return array;
}

// ランダムな混合分布のデータセットを作成
function createData() {
  let clusters = [];
  for (let i = 0; i < 6; i++) {
    let size = int(random(100, 200));
    let x_mean = random(0, canvas_size.width);
    let y_mean = random(0, canvas_size.height);
    let x_stddiv = random(20, 50);
    let y_stddiv = random(20, 50);

    let c = createGaussianDistribution(size, x_mean, x_stddiv, y_mean, y_stddiv);
    clusters.push(c);
  }

  return clusters;
}

// ガウシアン分布から乱数で生成する
function createGaussianDistribution(size, x_mean, x_stddiv, y_mean, y_stddiv) {
  // パラメータ表示用
  parameter.push({
    size: size,
    mean: {
      x: x_mean, y: y_mean
    },
    stddiv: {
      x: x_stddiv, y: y_stddiv
    }
  });
  // 点群のリスト
  let array = [];
  for (let i = 0; i < size; i++) {
    // ガウシアン分布のランダムな値
    let x = randomGaussian(x_mean, x_stddiv);
    let y = randomGaussian(y_mean, y_stddiv);
    // 範囲外のポイントは除く
    if (isOut(x, y)) continue;
    array.push([x, y]);
  }
  return array;
}

// 描画範囲外か判定
function isOut(x, y) {
  if (x < 0 || canvas_size.width < x ||
    y < 0 || canvas_size.height < y) {
    return true;
  }
  return false;
}

function join_dataset(clusters) {
  array = [];
  clusters.forEach(function (element) {
    array = array.concat(element);
  });
  // 元の３次元配列を崩さない様にするため
  return array;
}


// p5js
function setup() {
  let canvas = createCanvas(canvas_size.width, canvas_size.height);
  canvas.parent('canvas');
  // フーレームレートを1/1secにする
  frameRate(frame_rate);

  background(color(bg_color));

  ini();
  drawView();
}


function drawView() {
  // 描画
  // １ステップごと描画
  background(color(bg_color));

  if (next_step_flg) {
    compairePoints();
    drawCluster();
    drawSeedPoints();
  } else {
    moveSeeds();
    displayParameters();
    drawCluster();
    drawSeedPoints();
  }
  next_step_flg = !next_step_flg;
}

// データセットの描画
function drawCluster() {
  for (let i in data) {
    drawPoints(data[i], cluster_colors[i]);
  }
}

// 点の描画
function drawPoints(array, color) {
  let r = 6;
  noStroke();
  fill(color);
  for (let point of array) {
    ellipse(int(point[0]), int(point[1]), r, r);
  }
}

// シードの描画
function drawSeedPoints() {
  let r = 15;
  for (let i in seeds) {
    stroke(cluster_colors[i]);
    strokeWeight(4);
    let point = seeds[i];
    fill('#00000');
    ellipse(int(point[0]), int(point[1]), r, r);
  }
}

function compairePoints() {
  // 空にする。
  data = new Array();
  for (let i in seeds) {
    data.push([]);
  }
  for (let point of points) {
    let min = 100000;
    let j = 0;
    for (let i in seeds) {
      let _min = diffelense(point, seeds[i])
      if (min < _min) continue;
      j = i;
      min = _min;
    }
    data[j].push(point)
  }
}

// 点の距離
function diffelense(p1, p2) {
  return Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2))
}

function moveSeeds() {

  for (let i in data) {
    let sum = [0, 0]

    if (data[i].length < 1) {
      // ポイントが無ければランダム
      seeds[i][0] = random(0, canvas_size.width);
      seeds[i][1] = random(0, canvas_size.width);
      continue;
    }

    for (let point of data[i]) {
      sum[0] += point[0];
      sum[1] += point[1];
    }
    seeds[i][0] = sum[0] / data[i].length;
    seeds[i][1] = sum[1] / data[i].length;
  }
}


// パラメータの表示
function displayParameters() {
  let html = '';
  for (let i in seeds) {
    let txt = '<p style="color:' + cluster_colors[i] + ';">';
    txt += 'サイズ：' + data[i].length + '&nbsp;';
    txt += '位置：(' + seeds[i][0].toFixed(1) + ', ' + seeds[i][1].toFixed(1) + ')';
    txt += '</p>';
    html += txt;
  }
  document.getElementById('parameters').innerHTML = html;
}

```

P5jsでk-meansのクラスタリング過程を可視化する

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

今回は**シェルソート**（**insertion sort**）です。
以前作った[挿入ソート](https://www.suzu6.net/posts/82-insertion-sort/)の改良版に当たります。

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

ブラウザはChromeを推奨！

## シェルソート (shell sort)

シェルソートは[ドナルド・シェル](https://ja.wikipedia.org/wiki/%E3%83%89%E3%83%8A%E3%83%AB%E3%83%89%E3%83%BB%E3%82%B7%E3%82%A7%E3%83%AB)が開発した整列アルゴリズムです。
減少増分ソート（diminishing increment sort）とも呼ばれます。
挿入ソートは既に殆ど整列された配列で効率的に機能するのに対して、シェルソートはより一般化した方法になります。

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

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

### 間隔hの決め方

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

### 計算量

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

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

## シミュレーション

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

- 濃い黄色比較している高さ
- 薄緑比較する範囲（hの間隔）

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


<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>

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

## シェルソートのコード

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

```js
// シェルソート
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);
  }
}
```

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

## 全体のソースコード

```html


<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](/images/posts/105/shell-sort.js)

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

```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 = 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(), // コピーして渡す
    });
}
```


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

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

- [遺伝的浮動(genetic draft)](https://www.suzu6.net/posts/57-genetic-draft)
- [モンテカルロ法で円周率の近似を求める](https://www.suzu6.net/posts/59-montecarlo-pi)
- [クイックソート](https://www.suzu6.net/posts/68-quicksort)
- [バブルソート](https://www.suzu6.net/posts/75-babblesort)
- [シェーカーソート](https://www.suzu6.net/posts/76-shakersort)
- [選択ソート](https://www.suzu6.net/posts/77-selection-sort)
- [挿入ソート](https://www.suzu6.net/posts/82-insertion-sort)

## 参考

- [Wiki](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)
- [シェルソート Algoful](http://algoful.com/Archive/Algorithm/ShellSort)
- [シェルソート（挿入ソートの改良） | Programming Place Plus　アルゴリズムとデータ構造編【整列アルゴリズム】　第５章](https://programming-place.net/ppp/contents/algorithm/sort/005.html)

アルゴリズムを体系的に学びたい方はオライリーの
<a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;">
がおすすめです。初版を持っているが、コードの間違いが少々目立つ点は残念。
ただ、解説と計算量が充実している。

<div class="cstmreba"><div class="booklink-box"><div class="booklink-image"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" ><img src="https://thumbnail.image.rakuten.co.jp/@0_mall/book/cabinet/6341/9784873116341.jpg?_ex=200x200" style="border: none;" /></a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="booklink-info"><div class="booklink-name"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"><div class="booklink-powered-date">posted with <a href="https://yomereba.com" rel="nofollow" target="_blank">ヨメレバ</a></div></div><div class="booklink-detail">ナラシンハ・カルマンチ/黒川利明 オライリー・ジャパン 2013年08月    </div><div class="booklink-link2"><div class="shoplinkrakuten"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >楽天ブックス</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="shoplinkamazon"><a href="https://www.amazon.co.jp/exec/obidos/asin/4873116341/suzu60c-22/" target="_blank" rel="nofollow" >Amazon</a></div><div class="shoplinkkindle"><a href="https://www.amazon.co.jp/gp/search?keywords=%93%FC%96%E5%83f%81%5B%83%5E%8D%5C%91%A2%82%C6%83A%83%8B%83S%83%8A%83Y%83%80&__mk_ja_JP=%83J%83%5E%83J%83i&url=node%3D2275256051&tag=suzu60c-22" target="_blank" rel="nofollow" >Kindle</a></div>                              	  	  	  	  	</div></div><div class="booklink-footer"></div></div></div>

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

k-meansのクラスタリングを可視化するために、偏りのあるデータセットを作成します。
P5jsの関数`randomGaussian()`を使って２次元の混合分布を表現しました。

今回作成したp5jsのGIF

![gif](/images/posts/98/cluster.gif)

## P5jsのランダム関数

P5jsには分布が異なるランダム関数が２種類あります。

- [random()](https://p5js.org/reference/#/p5/random)
- [randomGaussian()](https://p5js.org/reference/#/p5/randomGaussian)

`random()`は一様分布の乱数、`randomGaussian()`はガウス分布（正規分布）をとる乱数を返します。

### ガウス分布

ガウス分布は平均値の付近に集積するような釣鐘型の確率分布です。正規分布とも呼びます。

![wiki](https://upload.wikimedia.org/wikipedia/commons/thumb/7/74/Normal_Distribution_PDF.svg/325px-Normal_Distribution_PDF.svg.png)

平均を$\mu$, 分散を $\sigma^2 > 0$とする（1次元）正規分布とは、確率密度関数が次の形です。

```math
f(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp{-\frac{(x-\mu)^2}{2\sigma^2}}
```

この分布は$N(\mu, \sigma^2)$と表します。

wikiより引用

### randomGaussian()

P5jsの関数[randomGaussian()](https://p5js.org/reference/#/p5/randomGaussian)は、ガウス分布に従った乱数を返します。
使い方は以下の通りです。

引数を渡さずデフォルトでは$N(0, 1)$の標準正規分布を返します。

```js
let x = randomGaussian();
```

平均10、標準偏差10のガウス分布$N(10, 10)$を返すには以下のようにします。

```js
let mean = 10; // 平均
let stddiv = 10; // 標準偏差

let x = randomGaussian(mean, stddiv);
```

標準偏差は英語でstandard deviationです。

平均値から極端に離れた値が帰る確率はかなり低いですが、理論的に返り値に最大最小値はありません。

## ２次元平面にクラスターをプロットする

**k-means**の可視化に利用するため、`randomGaussian()`を使って２次元平面に偏りのあるクラスターのデータセットをプロットします。

各クラスターは、x, y軸それぞれにガウス分布を持つ**多変量正規分布**のクラスタにしています。

![多変量正規分布](https://upload.wikimedia.org/wikipedia/commons/thumb/9/95/Multivariate_normal_sample.svg/300px-Multivariate_normal_sample.svg.png)

出来たものが下の画像です。400×400のキャンバスに５つのクラスターがランダムに現れるようにしました。

程よくバラけたもの。

![cluster1](/images/posts/98/cluster.png)

重なりがあるクラスター。

![cluster2](/images/posts/98/cluster2.png)

k-meansのクラスタ数を5とすると、上の程よくバラけた点群は正確に分類出来そうです。下の点群は、クラスタ数３がちょうど良さそうな感じですね。

### シミュレーション

実際にシミュレーションしているのが下の図です。

ひとつのクラスターに約150個のデータができるようにしています。
**リトライ**を押すと新しいデータセットを作成します。



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

<script src="/images/posts/98/gaussian-distribution.js"></script>

<div class="p5js">
  <div class="center">
    <button type="button" class="button is-primary" onclick="retry();">リトライ</button>&nbsp;
  </div>
  <div  class="center">
    クラスタ数：<span id="count">5</span>&nbsp;
  </div>
  <div id="canvas"  class="has-text-centered"></div>
  <div class="center" id="parameters"></div>
</div>

<style>
.p5js .center{
  text-align: center;
  margin: 10px;
}
.p5js .button{
  text-align: center;
  margin: 10px;
}
</style>

それぞれのクラスターのサイズと重心位置(x_mean, y_mean)、標準偏差（x_stddiv, y_stddiv）を表示ししています。

## ソースコードと解説

### データセットの作成

コードの中でデータセットを作成する部分の解説。

描画するキャンバスのサイズが400×400(px)としているので、その中で程よくバラけるようにパラメータを調節しています。
配列の要素に`[x, y]`となる座標を追加している。
また、キャンバスの範囲外は削除するようにしています。

```js
let canvas_size = { width: 400, height: 400 } //px

// ランダムな混合分布のデータセットを作成
function createData() {
  let clusters = [];
  for (let i = 0; i < 5; i++) {
    let size = int(random(100, 200));
    let x_mean = random(0, canvas_size.width);
    let y_mean = random(0, canvas_size.height);
    let x_stddiv = random(20, 50);
    let y_stddiv = random(20, 50);

    let c = createGaussianDistribution(size, x_mean, x_stddiv, y_mean, y_stddiv);
    clusters.push(c);
  }

  return clusters;
}

// ガウシアン分布から乱数で生成する
function createGaussianDistribution(size, x_mean, x_stddiv, y_mean, y_stddiv) {
  // 点群のリスト
  let array = [];
  for (let i = 0; i < size; i++) {
    // ガウシアン分布のランダムな値
    let x = randomGaussian(x_mean, x_stddiv);
    let y = randomGaussian(y_mean, y_stddiv);
    // 範囲外のポイントは除く
    if (isOut(x, y)) continue;
    array.push([x, y]);
  }
  return array;
}
```

### ソースコード全文

キャンバスと表示制御部分のhtml

```html

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.3/p5.min.js"></script>
<script src="/images/posts/98/gaussian-distribution.js"></script>

<div class="p5js">
  <div class="center">
    <button type="button" class="button is-primary" onclick="retry();">リトライ</button>&nbsp;
  </div>
  <div  class="center">
    クラスタ数：<span id="count">5</span>&nbsp;
  </div>
  <div id="canvas"  class="has-text-centered"></div>
  <div class="center" id="parameters"></div>
</div>

<style>
.p5js .center{
  text-align: center;
  margin: 10px;
}
.p5js .button{
  text-align: center;
  margin: 10px;
}
</style>
```

[gaussian-distribution.js](/images/posts/98/gaussian-distribution.js)

```js
let data = [];
let frame_rate = 10;
let parameter = [];

let canvas_size = { width: 400, height: 400 } //px

let bg_color = '#FFFCDB';
let cluster_colors = ['#A40000', '#0075A9', '#007130', '#A4005B', '#B7AA00', '#100964'];

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

// 初期化
function ini() {
  parameter = [];
  data = createData();
  displayParameters();
}

// パラメータの表示
function displayParameters(){
  let html = '';
  for(let i in parameter){
    let p = parameter[i];
    let txt = '<p style="color:' + cluster_colors[i]+ ';">';
    txt += 'サイズ：' + p.size +'&nbsp;';
    txt += '重心：(' + p.mean.x.toFixed(1) + ', ' + p.mean.y.toFixed(1)+')&nbsp;';
    txt += '標準偏差：(' + p.stddiv.x.toFixed(1) + ', ' + p.stddiv.y.toFixed(1) +')</p>';
    html += txt;
  }
  document.getElementById('parameters').innerHTML = html;
}

// ランダムな混合分布のデータセットを作成
function createData() {
  let clusters = [];
  for (let i = 0; i < 5; i++) {
    let size = int(random(100, 200));
    let x_mean = random(0, canvas_size.width);
    let y_mean = random(0, canvas_size.height);
    let x_stddiv = random(20, 50);
    let y_stddiv = random(20, 50);

    let c = createGaussianDistribution(size, x_mean, x_stddiv, y_mean, y_stddiv);
    clusters.push(c);
  }

  return clusters;
}

// ガウシアン分布から乱数で生成する
function createGaussianDistribution(size, x_mean, x_stddiv, y_mean, y_stddiv) {
  // パラメータ表示用
  parameter.push({ 
    size: size,
    mean: { x: x_mean, y: y_mean },
    stddiv: { x: x_stddiv, y: y_stddiv }
  });
  // 点群のリスト
  let array = [];
  for (let i = 0; i < size; i++) {
    // ガウシアン分布のランダムな値
    let x = randomGaussian(x_mean, x_stddiv);
    let y = randomGaussian(y_mean, y_stddiv);
    // 範囲外のポイントは除く
    if (isOut(x, y)) continue;
    array.push([x, y]);
  }
  return array;
}

// 描画範囲外か判定
function isOut(x, y) {
  if (x < 0 || canvas_size.width < x ||
    y < 0 || canvas_size.height < y) {
    return true;
  }
  return false;
}


// p5js
function setup() {
  let canvas = createCanvas(canvas_size.width, canvas_size.height);
  canvas.parent('canvas');
  // フーレームレートを1/1secにする
  frameRate(frame_rate);

  background(color(bg_color));

  // 描画を繰り返さない。
  ini();
}

function draw() {
  // 描画
  background(color(bg_color));
  drawCluster();
}

// 混合分布の描画
function drawCluster() {
  for (let i in data) {
    drawPoints(data[i], cluster_colors[i]);
  }
}

// 点の描画
function drawPoints(array, color) {
  let r = 6;
  noStroke();
  fill(color);
  for (let point of array) {
    ellipse(int(point[0]), int(point[1]), r, r);
  }
}

```

## 参考

### Webサイト

- [Wikipedia](https://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E5%88%86%E5%B8%83)
- [P5js](https://p5js.org/)

P5jsでガウス分布のデータセットを作成する

雪の結晶をシミュレーションするにはどうしたらよいか、探していたところ**拡散律速凝集**（**DLA**）にたどり着きました。
これを**P5js**でブラウザ上でシミュレーションできるようにしています。

[こちら](http://www.natural-science.or.jp/article/20110405000246.php)を参考に作成しました。

## 拡散律速凝集（Diffusion-limited aggregation; DLA）

**ブラウン運動**する粒子が核となるクラスタに取り込まれクラスタを成長させる過程のことをいいます。
DLA によってできるクラスタは**ブラウン木**と呼ばれる。
下図のようにフラクタルな構造になる。

![wiki-img](/images/posts/90/wiki-img.jpg)

wikiより引用。

今回はこれを目指してコードを書いた。

### 用語説明

- ブラウン運動：浮遊する微粒子が不規則に運動する現象。シミュレーションでの青い粒の動き。
- クラスタ：同種の原子あるいは分子が相互作用によって数個以上の数が結合した物体を指す。シミュレーションでの白い粒の塊。

### DLAシミュレーションのステップ

DLAによるクラスタのシミュレーションは以下のようになります。

1. 中央にクラスタの核を置く。
2. その周りを粒子がブラウン運動している。
3. クラスタにブラウン粒子が隣接すると、粒子は結晶化する。

これを繰り返してクラスタが大きくなります。

### いくつかのパターン

今回のシミュレーションで出来たブラウン木の一部。
結晶の粒子数が40,000を超えたあたりの様子が以下になっています。

![patern1](/images/posts/90/patern1.png)

![patern2](/images/posts/90/patern2.png)

毎回異なるパターンになるので一期一会を楽しんでください。

## シミュレーション

実際にDLAをシミュレーションしているのが下の図です。

- 青い丸：ブラウン運動する粒子
- 白い丸：結晶化したクラスタ



計算量の都合上、クラスタの粒子数が50,000を超えたら停止するようにしています。



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

<script src="/images/posts/90/dla.js"></script>

<div>
  <div class="center">
    <button type="button" class="button is-primary" onclick="restart();">リスタート</button>
  </div>
  <div  class="center">
    クラスタの粒子数：<span id="count">0</span>&nbsp;
  </div>
  <div id="canvas"  class="has-text-centered"></div>
</div>

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

## ソースコードと解説

```js
let flowing_perticles = [];
let fixed_perticles = [];
let initial_size = 300;
let porse = false;
let adsorption_distance = 6; // 吸着距離
let max_size = 50000;


frame_rate = 30;
let canvas_size = {width: 400, height: 400} //px
let center = {
  x: canvas_size.width / 2,
  y: canvas_size.height / 2,
}

let bg_color = null;
let flowing_color = null;
let fixed_color = null;

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

// 初期化
function ini() {
  let array = [];
  fixed_perticles = [new Perticle(canvas_size.width / 2, canvas_size.height / 2)];
  flowing_perticles = setRandomPositions();
  porse = false;
}

// 粒子をランダムに配置する
function setRandomPositions(){
  let array = [];
  let half = Math.floor(canvas_size.height / 2);
  for(let i = 0; i < initial_size; i++){
    let r = random(30, half);
    let theta = random(0, 2*PI);
    let x = int(center.x + r*cos(theta));
    let y = int(center.y + r*sin(theta));
    array.push(new Perticle(x, y));
  }
  return array;
}


// p5js
function setup() {
  let canvas = createCanvas(canvas_size.width, canvas_size.height);
  canvas.parent('canvas');
  // フーレームレートを1/1secにする
  frameRate(frame_rate);

  bg_color = color(10, 10, 10);
  flowing_color = color(0, 163, 245);
  fixed_color = color(159, 217, 246);
  background(bg_color);
  // 描画を繰り返さない。
  ini();
}

function draw() {
  if (!porse) {
    // 粒子の動き
    action();
    
    // 描画
    background(bg_color);
    drawPerticles(flowing_perticles, flowing_color);
    drawPerticles(fixed_perticles, fixed_color);

    document.getElementById('count').innerHTML = fixed_perticles.length;
    if (fixed_perticles.length > max_size){
      // 一定のクラスタ数で止める
      porse = true;
    }
  }else{
    // 停止中はクラスタだけ表示
    background(bg_color);
    drawPerticles(fixed_perticles, fixed_color);
  }
}

// 粒子の動き
function action(){
  // 粒子が動く
  for (let flow of flowing_perticles) {
    flow.move();
  }
  let to_fix = [];
  let remove = [];
  // 新しく結晶化した300個だけ比較する
  let not_compare = Math.max(0, fixed_perticles.length - 10000);

  for(let i in flowing_perticles){
    let flow = flowing_perticles[i];
    // 描画範囲外の判定
    if(is_out(flow)){
      remove.push(i);
      continue;
    }
    // 吸着の判定
    for (let j = fixed_perticles.length - 1; not_compare <= j; j--){
      let fixed = fixed_perticles[j];
      // if(abs(fixed.x - flow.x) > adsorption_distance){
      //   // x軸が吸着距離より離れているとき
      //   continue;
      // }
      if(is_closed(flow, fixed)){
        to_fix.push(flow); // クラスタに追加する粒子
        remove.push(i); // 取り除く粒子
        continue;
      }
    }
  }
  // 吸着した粒子を固定する
  fixed_perticles = fixed_perticles.concat(to_fix);
  // 粒子を除き新たに生成する
  let half = Math.floor(canvas_size.height / 2);
  for(let i of remove){
    // randomな初期値
    let r = random(half / 2, half);
    let theta = random(0, 2*PI);
    let x = int(center.x + r*cos(theta));
    let y = int(center.y + r*sin(theta));
    flowing_perticles[i] = new Perticle(x, y);
  }
}

// 近接したか判定
function is_closed(a, b){
  // ユークリッド距離
  // let d = Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
  // マンハッタン距離
  let d = abs(a.x - b.x) + abs(a.y - b.y);
  if( d < adsorption_distance){
    return true;
  }
  return false;
}

// 描画範囲外か判定
function is_out(a){
  if(a.x < 0 || canvas_size.width < a.x ||
    a.y < 0 || canvas_size.height < a.y){
      return true;
    }
  return false;
}

function drawPerticles(array, color){
  let r = adsorption_distance;
  noStroke();
  fill(color);
  for(let ele of array){
    ellipse(int(ele.x), int(ele.y), r, r);
  }
}


class Perticle{
  constructor(x, y){
    this.x = x;
    this.y = y;
    this.r = 5;
  }
  // ブラウン運動
  move(){
    let r = random(0, this.r);
    let theta = random(0, 2 * PI);
    this.x += r * cos(theta);
    this.y += r * sin(theta);
  }
}
```

## 参考

### Webサイト

- [２－１．DLAによる樹木状クラスタのシミュレーション](http://www.natural-science.or.jp/article/20110405000246.php)
- [Wikipedia](https://ja.wikipedia.org/wiki/%E6%8B%A1%E6%95%A3%E5%BE%8B%E9%80%9F%E5%87%9D%E9%9B%86)
- [P5js](https://p5js.org/)

### 書籍

<a target="_blank"  href="https://www.amazon.co.jp/gp/product/4130627252/ref=as_li_tl?ie=UTF8&camp=247&creative=1211&creativeASIN=4130627252&linkCode=as2&tag=suzu60c-22&linkId=9046198881891368460c22c9f5c6171c"><img border="0" src="//ws-fe.amazon-adsystem.com/widgets/q?_encoding=UTF8&MarketPlace=JP&ASIN=4130627252&ServiceVersion=20070822&ID=AsinImage&WS=1&Format=_SL250_&tag=suzu60c-22" ></a><img src="//ir-jp.amazon-adsystem.com/e/ir?t=suzu60c-22&l=am2&o=9&a=4130627252" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" />

[一般気象学 第2版補訂版](https://amzn.to/2SxItU7)

IoTで気象データを扱うためには、気象のことを知る必要があると思い読んでいる本です。
今回の雪の結晶が出来る過程も詳細に載っています。
今まで工学・情報学の知識に偏っていたので、熱や流体のとらえ方が新鮮で面白いです。

P5jsで拡散律速凝集（DLA）の結晶生成をシミュレーションする

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

今回は**数え上げソート**（**insertion sort**）です。
以前作った[クイックソート](https://www.suzu6.net/posts/68-quicksort)や[バブルソート](https://www.suzu6.net/posts/75-babblesort)と原理が異なるので視覚化に悩みましたが、わかりやさを優先で作ってみます。

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

ブラウザはChromeを推奨！

## 数え上げソート (counting sort)

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

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

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

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

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

## シミュレーション

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

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

- １段目：並べ替える配列A
- ２段目：一時的な情報の配列
- ３段目：出力の配列
- 赤色：アクセスしている要素

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


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

<script src="/js/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>

## 数え上げソートのコード

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

```js
// 数え上げソート
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+1$の長さにしている。

## 全体のソースコード

```js

<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](/images/posts/89/counting-sort.js)

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

```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(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
  });
}

```

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

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


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

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

- [遺伝的浮動(genetic draft)](https://www.suzu6.net/posts/57-genetic-draft)
- [モンテカルロ法で円周率の近似を求める](https://www.suzu6.net/posts/59-montecarlo-pi)
- [クイックソート](https://www.suzu6.net/posts/68-quicksort)
- [バブルソート](https://www.suzu6.net/posts/75-babblesort)
- [シェーカーソート](https://www.suzu6.net/posts/76-shakersort)
- [選択ソート](https://www.suzu6.net/posts/77-selection-sort)
- [挿入ソート](https://www.suzu6.net/posts/82-insertion-sort)

## 参考

- [Wiki](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%BC%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%BC%E3%83%88)

アルゴリズムを体系的に学びたい方はオライリーの
<a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;">
がおすすめです。

<div class="cstmreba"><div class="booklink-box"><div class="booklink-image"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" ><img src="https://thumbnail.image.rakuten.co.jp/@0_mall/book/cabinet/6341/9784873116341.jpg?_ex=200x200" style="border: none;" /></a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="booklink-info"><div class="booklink-name"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"><div class="booklink-powered-date">posted with <a href="https://yomereba.com" rel="nofollow" target="_blank">ヨメレバ</a></div></div><div class="booklink-detail">ナラシンハ・カルマンチ/黒川利明 オライリー・ジャパン 2013年08月    </div><div class="booklink-link2"><div class="shoplinkrakuten"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >楽天ブックス</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="shoplinkamazon"><a href="https://www.amazon.co.jp/exec/obidos/asin/4873116341/suzu60c-22/" target="_blank" rel="nofollow" >Amazon</a></div><div class="shoplinkkindle"><a href="https://www.amazon.co.jp/gp/search?keywords=%93%FC%96%E5%83f%81%5B%83%5E%8D%5C%91%A2%82%C6%83A%83%8B%83S%83%8A%83Y%83%80&__mk_ja_JP=%83J%83%5E%83J%83i&url=node%3D2275256051&tag=suzu60c-22" target="_blank" rel="nofollow" >Kindle</a></div>                              	  	  	  	  	</div></div><div class="booklink-footer"></div></div></div>

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

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

今回は**挿入ソート**（**insertion sort**）です。
[クイックソート](https://www.suzu6.net/posts/68-quicksort)と[バブルソート](https://www.suzu6.net/posts/75-babblesort)に引き続き、ぼーっとできるシミュレーションを作りました。

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

ブラウザはChromeを推奨！

## 挿入ソート (insertion sort)

挿入ソートは整列してある配列に追加要素を適切な場所に挿入するソート方法。
基本挿入法ともいう。

- 平均計算時間・最悪計算時間がともに$O(n2)$と遅い。
- アルゴリズムが単純で実装が容易。
- 安定な内部ソート。
- 連結リストでは処理が早い。

以下の手順でソートしていきます。

1. 挿入する要素を取り出す
2. 適切な挿入位置まで整列済みの要素をずらす
3. 要素を挿入する
4. 配列全体を整列するまでこの処理を前方から繰り返す。

## シミュレーション

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

これまでと表現を変えました。
挿入する要素を比較している要素の前に描いています。

- 黄色 : 挿入する要素
- うっすらと明るいのが整列していない範囲。

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


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

<script src="/images/posts/82/insertion-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>



## 挿入ソートのコード

今回は要素を交換するswap関数を使っていない。


```js

// 挿入ソート
function insertionSort(array) {
  let length = array.length;

  // 4. 配列全体を整列するまでこの処理を前方から繰り返す。
  for(let i = 0; i < length; i++){
    // 1. 挿入する要素を取り出す
    let tmp = array[i];
    if(array[i - 1] > tmp){
      let j = i;
      while(j > 0 && array[j - 1] > tmp){
        // 2. 適切な挿入位置まで整列済みの要素をずらす
        array[j] = array[j - 1];
        j--;
      }
      // 3. 要素を挿入する
      array[j] = tmp;
    }
  }
}

```

普通の配列を使っているため、２．で要素を後方にずらしています。
連結リストを使った場合は途中に要素を追加ができるため、処理時間がかなり短くなります。

## コードの全容

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

### HTML

```html

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

<script src="/images/posts/82/insertion-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

[selection-sort.js](https://www.suzu6.net/images/posts/77/selection-sort.js)

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

  // 4. 配列全体を整列するまでこの処理を前方から繰り返す。
  for(let i = 0; i < length; i++){
    // 1. 挿入する要素を取り出す
    let tmp = array[i];
    if(array[i - 1] > tmp){
      let j = i;
      while(j > 0 && array[j - 1] > tmp){
        // 2. 適切な挿入位置まで整列済みの要素をずらす
        array[j] = array[j - 1];
        j--;
        record(true, tmp, j, i+1, length - 1 , array);        
      }
      // 3. 要素を挿入する
      array[j] = tmp;
      record(false, tmp, j, i+1, length - 1 , array);
    }
  }
  record(false, -1, -1, 0, length - 1 , array); // 終了状態
  return true
}

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

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

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

- [遺伝的浮動(genetic draft)](https://www.suzu6.net/posts/57-genetic-draft)
- [モンテカルロ法で円周率の近似を求める](https://www.suzu6.net/posts/59-montecarlo-pi)
- [クイックソート](https://www.suzu6.net/posts/68-quicksort)
- [バブルソート](https://www.suzu6.net/posts/75-babblesort)
- [シェーカーソート](https://www.suzu6.net/posts/76-shakersort)
- [選択ソート](https://www.suzu6.net/posts/77-selection-sort)
- [挿入ソート](https://www.suzu6.net/posts/82-insertion-sort)

## 参考

- [Wiki](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%BC%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%BC%E3%83%88)

アルゴリズムを体系的に学びたい方はオライリーの
<a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;">
がおすすめです。

<div class="cstmreba"><div class="booklink-box"><div class="booklink-image"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" ><img src="https://thumbnail.image.rakuten.co.jp/@0_mall/book/cabinet/6341/9784873116341.jpg?_ex=200x200" style="border: none;" /></a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="booklink-info"><div class="booklink-name"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"><div class="booklink-powered-date">posted with <a href="https://yomereba.com" rel="nofollow" target="_blank">ヨメレバ</a></div></div><div class="booklink-detail">ナラシンハ・カルマンチ/黒川利明 オライリー・ジャパン 2013年08月    </div><div class="booklink-link2"><div class="shoplinkrakuten"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >楽天ブックス</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="shoplinkamazon"><a href="https://www.amazon.co.jp/exec/obidos/asin/4873116341/suzu60c-22/" target="_blank" rel="nofollow" >Amazon</a></div><div class="shoplinkkindle"><a href="https://www.amazon.co.jp/gp/search?keywords=%93%FC%96%E5%83f%81%5B%83%5E%8D%5C%91%A2%82%C6%83A%83%8B%83S%83%8A%83Y%83%80&__mk_ja_JP=%83J%83%5E%83J%83i&url=node%3D2275256051&tag=suzu60c-22" target="_blank" rel="nofollow" >Kindle</a></div>                              	  	  	  	  	</div></div><div class="booklink-footer"></div></div></div>

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

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

今回は**選択ソート**（**selection sort**）です。
[クイックソート](https://www.suzu6.net/posts/68-quicksort)と[バブルソート](https://www.suzu6.net/posts/75-babblesort)に引き続き、ぼーっとできるシミュレーションを作りました。

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

ブラウザはChromeを推奨！

## 選択ソート (selection sort)


**選択ソート**は交換回数が少なく、簡単に実装できて小さなファイルに適したソートです。
走査範囲から最小の値を見つけ先頭と交換していきます。
ただし、規模が大きいと計算量が悪化します（$O(n^2)$）。

手順は以下の通りです。

1. リスト内の最小値を見つける
2. 現在の位置と交換する。
3. 配列全体を交換するまでこの処理を全ての要素に繰り返す。

[バブルソート](https://www.suzu6.net/posts/75-babblesort)と似ていますが、交換回数がかなり少ないです。

## シミュレーション

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

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

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

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


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

<script src="/images/posts/77/selection-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>

とてもお行儀の良いソートに見える。
このように、最小要素を繰り返し選択するため選択ソートと呼ばれます。
比較回数は多いが、交換回数は配列長より短くなります。

## 選択ソートのコード

for文は２重だが両方とも順方向であるため、理解しやすい。


```js
// 選択ソート
function selectionSort(array) {
  let length = array.length;

  // 3. 配列全体を交換するまでこの処理を全ての要素に繰り返す。
  for(let i = 0; i < length; i++){
    let min = i;
    for(let j = i+1; j < length; j++){
      if(array[j] < array[min]){
        // 1. リスト内の最小値を見つける
        min = j;
      }
    }
    // 2. 現在の位置と交換する。
    swap(i, min, array);
  }
}


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


## コードの全容

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

### HTML

```html

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

<script src="/images/posts/77/selection-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

[selection-sort.js](https://www.suzu6.net/images/posts/77/selection-sort.js)

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

  // 3. 配列全体を交換するまでこの処理を全ての要素に繰り返す。
  for(let i = 0; i < length; i++){
    let min = i;
    let swaped = false;
    for(let j = i+1; j < length; j++){
      if(array[j] < array[min]){
        // 1. リスト内の最小値を見つける
        min = j;
        swaped = true;
      }
      record(false, min, j, i, length - 1 , array);
    }
    // 2. 現在の位置と交換する。
    swap(i, min, array);
    record(swaped, i, min, 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
      }
    });
}
```

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

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

- [遺伝的浮動(genetic draft)](https://www.suzu6.net/posts/57-genetic-draft)
- [モンテカルロ法で円周率の近似を求める](https://www.suzu6.net/posts/59-montecarlo-pi)
- [クイックソート](https://www.suzu6.net/posts/68-quicksort)
- [バブルソート](https://www.suzu6.net/posts/75-babblesort)
- [シェーカーソート](https://www.suzu6.net/posts/76-shakersort)

## 参考

- [Wiki](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%BC%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%BC%E3%83%88)

アルゴリズムを体系的に学びたい方はオライリーの
<a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;">
がおすすめです。

<div class="cstmreba"><div class="booklink-box"><div class="booklink-image"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" ><img src="https://thumbnail.image.rakuten.co.jp/@0_mall/book/cabinet/6341/9784873116341.jpg?_ex=200x200" style="border: none;" /></a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="booklink-info"><div class="booklink-name"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"><div class="booklink-powered-date">posted with <a href="https://yomereba.com" rel="nofollow" target="_blank">ヨメレバ</a></div></div><div class="booklink-detail">ナラシンハ・カルマンチ/黒川利明 オライリー・ジャパン 2013年08月    </div><div class="booklink-link2"><div class="shoplinkrakuten"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >楽天ブックス</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="shoplinkamazon"><a href="https://www.amazon.co.jp/exec/obidos/asin/4873116341/suzu60c-22/" target="_blank" rel="nofollow" >Amazon</a></div><div class="shoplinkkindle"><a href="https://www.amazon.co.jp/gp/search?keywords=%93%FC%96%E5%83f%81%5B%83%5E%8D%5C%91%A2%82%C6%83A%83%8B%83S%83%8A%83Y%83%80&__mk_ja_JP=%83J%83%5E%83J%83i&url=node%3D2275256051&tag=suzu60c-22" target="_blank" rel="nofollow" >Kindle</a></div>                              	  	  	  	  	</div></div><div class="booklink-footer"></div></div></div>

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

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

そんな訳で、前回の[クイックソート](https://www.suzu6.net/posts/68-quicksort)に引き続きぼーっとできるシミュレーションを作りました。
今回はアルゴリズムの基礎から**バブルソート**のシミュレーションです。

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

ブラウザはChromeを推奨！

## バブルソート


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

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

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

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

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

## シミュレーション

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

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

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

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


<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>

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


## バブルソートのコード

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


```js
// バブルソート
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

```html

<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](https://www.suzu6.net/images/posts/75/babblesort.js)

```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
      }
    });
}
```

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

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

- [遺伝的浮動(genetic draft)](https://www.suzu6.net/posts/57-genetic-draft)
- [モンテカルロ法で円周率の近似を求める](https://www.suzu6.net/posts/59-montecarlo-pi)
- [クイックソート](https://www.suzu6.net/posts/68-quicksort)

## 参考

- [Wiki](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)

アルゴリズムを体系的に学びたい方はオライリーの
<a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;">
がおすすめです。

<div class="cstmreba"><div class="booklink-box"><div class="booklink-image"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" ><img src="https://thumbnail.image.rakuten.co.jp/@0_mall/book/cabinet/6341/9784873116341.jpg?_ex=200x200" style="border: none;" /></a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="booklink-info"><div class="booklink-name"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"><div class="booklink-powered-date">posted with <a href="https://yomereba.com" rel="nofollow" target="_blank">ヨメレバ</a></div></div><div class="booklink-detail">ナラシンハ・カルマンチ/黒川利明 オライリー・ジャパン 2013年08月    </div><div class="booklink-link2"><div class="shoplinkrakuten"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >楽天ブックス</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="shoplinkamazon"><a href="https://www.amazon.co.jp/exec/obidos/asin/4873116341/suzu60c-22/" target="_blank" rel="nofollow" >Amazon</a></div><div class="shoplinkkindle"><a href="https://www.amazon.co.jp/gp/search?keywords=%93%FC%96%E5%83f%81%5B%83%5E%8D%5C%91%A2%82%C6%83A%83%8B%83S%83%8A%83Y%83%80&__mk_ja_JP=%83J%83%5E%83J%83i&url=node%3D2275256051&tag=suzu60c-22" target="_blank" rel="nofollow" >Kindle</a></div>                              	  	  	  	  	</div></div><div class="booklink-footer"></div></div></div>

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

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

今回はバブルソートを改良した**シェーカーソート**です。
[クイックソート](https://www.suzu6.net/posts/68-quicksort)と[バブルソート](https://www.suzu6.net/posts/75-babblesort)に引き続き、ぼーっとできるシミュレーションを作りました。

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

ブラウザはChromeを推奨！

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


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

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

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

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

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

## シミュレーション

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

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

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

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


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

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

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

### 改良案

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

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

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

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

```js
// シェーカーソート
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. 走査範囲が０になったらループを抜ける。
    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. 走査範囲が０になったらループを抜ける。
    if(start === end) break;
  }
}

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

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

## コードの全容

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

### HTML

```html

<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](https://www.suzu6.net/images/posts/76/shaker-sort.js)

```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
      }
    });
}
```

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

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

- [遺伝的浮動(genetic draft)](https://www.suzu6.net/posts/57-genetic-draft)
- [モンテカルロ法で円周率の近似を求める](https://www.suzu6.net/posts/59-montecarlo-pi)
- [クイックソート](https://www.suzu6.net/posts/68-quicksort)
- [バブルソート](https://www.suzu6.net/posts/75-babblesort)

## 参考

- [Wiki](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%BC%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%BC%E3%83%88)

アルゴリズムを体系的に学びたい方はオライリーの
<a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;">
がおすすめです。

<div class="cstmreba"><div class="booklink-box"><div class="booklink-image"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" ><img src="https://thumbnail.image.rakuten.co.jp/@0_mall/book/cabinet/6341/9784873116341.jpg?_ex=200x200" style="border: none;" /></a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="booklink-info"><div class="booklink-name"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"><div class="booklink-powered-date">posted with <a href="https://yomereba.com" rel="nofollow" target="_blank">ヨメレバ</a></div></div><div class="booklink-detail">ナラシンハ・カルマンチ/黒川利明 オライリー・ジャパン 2013年08月    </div><div class="booklink-link2"><div class="shoplinkrakuten"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >楽天ブックス</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="shoplinkamazon"><a href="https://www.amazon.co.jp/exec/obidos/asin/4873116341/suzu60c-22/" target="_blank" rel="nofollow" >Amazon</a></div><div class="shoplinkkindle"><a href="https://www.amazon.co.jp/gp/search?keywords=%93%FC%96%E5%83f%81%5B%83%5E%8D%5C%91%A2%82%C6%83A%83%8B%83S%83%8A%83Y%83%80&__mk_ja_JP=%83J%83%5E%83J%83i&url=node%3D2275256051&tag=suzu60c-22" target="_blank" rel="nofollow" >Kindle</a></div>                              	  	  	  	  	</div></div><div class="booklink-footer"></div></div></div>

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

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

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

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

ブラウザはChromeを推奨！

## クイックソート

クイックソートは[分割統治アルゴリズム](http://www.lab2.kuis.kyoto-u.ac.jp/~shuichi/algintro/alg-3s.pdf)の一種です。

![bunkasu](/images/posts/68/bunkatsu.png)

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

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

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

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

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

## シミュレーション

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

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

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

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


<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>

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

## コード

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

```js

// クイックソート
function quickSort(start, end, array) {
  if (end - start < 2) {
    // 1. 走査する配列長が0か１の場合戻る。
    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. 左右２つに配列を分割してこの関数を再帰的に繰り返す。
  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. のピボットを選ぶ方法は末端でもよい。

```js
  // 2. 走査する範囲の末端の要素をピボットとして選ぶ。
  let pivot = end;
  let pivot_height = array[pivot];
```

## クイックソートの計算量

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

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

## p5.jsで描画する

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

html

```html

<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](/images/posts/68/quicksort.js)

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

```js
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](/images/posts/68/random_bar.gif)

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

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

- [遺伝的浮動(genetic draft)](https://www.suzu6.net/posts/57-genetic-draft)
- [モンテカルロ法で円周率の近似を求める](https://www.suzu6.net/posts/59-montecarlo-pi)
- [バブルソート](https://www.suzu6.net/posts/75-babblesort)

## 参考

- [クイックソート - Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88)
- [クイックソート](http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html)
- [JavaScript クイックソート](https://qiita.com/may88seiji/items/a08504d472b5cec5f916)
- [JavaScriptで配列のコピー（値渡し）](https://qiita.com/takahiro_itazuri/items/882d019f1d8215d1cb67)

アルゴリズムを体系的に学びたい方はオライリーの
<a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;">
がおすすめです。

<div class="cstmreba"><div class="booklink-box"><div class="booklink-image"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" ><img src="https://thumbnail.image.rakuten.co.jp/@0_mall/book/cabinet/6341/9784873116341.jpg?_ex=200x200" style="border: none;" /></a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="booklink-info"><div class="booklink-name"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >入門データ構造とアルゴリズム</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"><div class="booklink-powered-date">posted with <a href="https://yomereba.com" rel="nofollow" target="_blank">ヨメレバ</a></div></div><div class="booklink-detail">ナラシンハ・カルマンチ/黒川利明 オライリー・ジャパン 2013年08月    </div><div class="booklink-link2"><div class="shoplinkrakuten"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F12444936%2F" target="_blank" rel="nofollow" >楽天ブックス</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="shoplinkamazon"><a href="https://www.amazon.co.jp/exec/obidos/asin/4873116341/suzu60c-22/" target="_blank" rel="nofollow" >Amazon</a></div><div class="shoplinkkindle"><a href="https://www.amazon.co.jp/gp/search?keywords=%93%FC%96%E5%83f%81%5B%83%5E%8D%5C%91%A2%82%C6%83A%83%8B%83S%83%8A%83Y%83%80&__mk_ja_JP=%83J%83%5E%83J%83i&url=node%3D2275256051&tag=suzu60c-22" target="_blank" rel="nofollow" >Kindle</a></div>                              	  	  	  	  	</div></div><div class="booklink-footer"></div></div></div>

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

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

そんな訳で、前回の[眺めていられるモンテカルロ法で円周率の近似を求めるシミュレーション](https://www.suzu6.net/posts/59-montecarlo-pi)に引き続きぼーっとできるシミュレーションを作りました。
今回は**モンテカルロ法で円周率の近似を求める**シミュレーションです。

ブラウザはChromeを推奨！

## モンテカルロ法

モンテカルロ法とはシミュレーションや数値計算を乱数を用いて行う手法の総称です。ランダム法とも呼ばれる。
例えば、[数値積分](https://www.a.math.ryukoku.ac.jp/~hig/course/compscib_2016/w13.pdf)や統計学の[ブートストラップ法](http://www.math.s.chiba-u.ac.jp/~wang/bootstrap.pdf)もモンテカルロ法の一つとされています。


乱数って何だろう？と疑問に思ったら[【Unity道場スペシャル 2017札幌】乱数完全マスター](https://www.slideshare.net/UnityTechnologiesJapan/unity-2017-81056841)のスライドを読んでください。わかりやすくてかなり面白いです！

## 円周率の求め方

モンテカルロ法を用いて円周率を求める方法は、**円と外接する正方形の面積比**を使います。

面積をS、半径をrとすると、$S_{circle} = \pi r^2$ です。
この円に外接する正方形の面積は $S_{square} = 4r^2$となります。
よって、円と外接する正方形の面積比は $S_{circle} / S_{square} = \pi / 4$ であることがわかりました。

![説明](/images/posts/59/s.png)

ここで、モンテカルロ法を使います。
外接する正方形の範囲に一様に点をプロットした時、円の中にプロットされる確率は面積比と同様に $\pi / 4$ になります。
プロットした点の数(**N**)と円の中の点の数(**x**)の比から、πは $\pi = 4x / N$ で求まるようになる。

たくさん点をプロットしていけば、πにどんどん近似していくはずです。

円周率を求める方法は他にも、[ライプニッツの方法](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%97%E3%83%8B%E3%83%83%E3%83%84%E3%81%AE%E5%85%AC%E5%BC%8F)や[ガウス・ルジャンドルの方法](https://www.google.com/search?q=%E3%82%AC%E3%82%A6%E3%82%B9%E3%83%BB%E3%83%AB%E3%82%B8%E3%83%A3%E3%83%B3%E3%83%89%E3%83%AB%E3%81%AE%E6%96%B9%E6%B3%95&oq=%E3%82%AC%E3%82%A6%E3%82%B9%E3%83%BB%E3%83%AB%E3%82%B8%E3%83%A3%E3%83%B3%E3%83%89%E3%83%AB%E3%81%AE%E6%96%B9%E6%B3%95&aqs=chrome..69i57.267j0j4&sourceid=chrome&ie=UTF-8)などがあります。

## シミュレーション

原理はなんとなく伝わったはずなので、実際に計算するところを眺めて見ましょう。
計算を簡単にするため円と外接する四角の $1/4$ にプロットします。面積比は変わらず $\pi / 4$ です。

円の中の点を緑、外の点を白としています。
試行回数が点をプロットした回数に当たる。
大体４万回ぐらいから3.14...と少数２桁が合うようになります。
案外、収束しないもんなんですね。

下のグラフがπの理論値と計算した値の比較になります。


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


<script src="https://www.amcharts.com/lib/4/core.js"></script>
<script src="https://www.amcharts.com/lib/4/charts.js"></script>
<script src="https://www.amcharts.com/lib/4/themes/material.js"></script>
<script src="https://www.amcharts.com/lib/4/themes/animated.js"></script>

<script src="/images/posts/59/montecarlo.js"></script>

<div>
  <div id="canvas"  class="has-text-centered"></div>
  <button type="button" class="button is-primary" onclick="restart();">再計算</button>
  <div class="m-left-20">πの演算結果：<span id="result">0</span></div>
  <div class="m-left-20">試行回数：<span id="trials">0</span>&nbsp;内側の点の数：<span id="t_inner">0</span>&nbsp;</div>
  <div id="chartdiv" class="chart has-text-centered"></div>
</div>

<style>
.chart {
  width: 100%;
  height: 400px;
}
.m-left-20{
  margin-left: 20px;
}
</style>

## コードの解説

単純に計算結果だけ求める場合は以下のようにします。

**JavaSript**

```js
function calcPi(){
  var trials = 10000; // 試行回数
  var t_inner = 0; // 円内の点の数

  for(var i = 0; i < trials; i++){
    var x = Math.random(); // 0 ~ 1.0の乱数
    var y = Math.random(); // 0 ~ 1.0の乱数
    var r = Math.sqrt(x * x + y * y);

    if(r < 1){
      // 円の内側
      t_inner++;
    }
  }
  // 計算結果
  var result = 4 * t_inner / trials;
  console.log(result);
}
```

円の内側かどうかは$\sqrt{x^2 + y^2} < r$ で判定することができます。
内側の点を数えて、計算します。

**Python**

```python
import random

inner = 0
for i in range(10000):
    x, y = random.random(), random.random()
    if x**2 + y**2 < 1:
        inner += 1
print(inner *4 / 10000)   # 3.1446
```

コード引用：[Remrinのpython攻略日記](http://python-remrin.hatenadiary.jp/entry/2017/05/04/163617)

### シミュレーションのコードについて

基本は上記のアルゴリズムを元に、計算過程を眺められるようグラフなど追加していきました。

### 利用したライブラリ

点のプロットには[p5js](https://p5js.org/)、グラフは[amCharts](https://www.amcharts.com/)を使います。
使い方は、それぞれ公式かこのブログのタグの記事を読んでで見てください。[p5js](https://www.suzu6.net/tags/p5js)と[amCharts](https://www.suzu6.net/tags/amCharts)。

**html**

```html

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


<script src="https://www.amcharts.com/lib/4/core.js"></script>
<script src="https://www.amcharts.com/lib/4/charts.js"></script>
<script src="https://www.amcharts.com/lib/4/themes/material.js"></script>
<script src="https://www.amcharts.com/lib/4/themes/animated.js"></script>


<script src="/images/posts/59/montecarlo.js"></script>

<div>
  
  <div id="canvas"  class="has-text-centered"></div>
  <button type="button" class="button is-primary" onclick="restart();">再計算</button>
  <div class="m-left-20">πの演算結果：<span id="result">0</span></div>
  <div class="m-left-20">試行回数：<span id="trials">0</span>&nbsp;内側の点の数：<span id="t_inner">0</span>&nbsp;</div>
  <div id="chartdiv" class="chart has-text-centered"></div>
</div>

<style>
.chart {
  width: 100%;
  height: 400px;
}
.m-left-20{
  margin-left: 20px;
}
</style>
```

**JavaScript**

全文は[こちら](https://www.suzu6.net/images/posts/59/montecarlo.js)

```js
var t_inner = 0;
var trials = 0;

// p5js
function setup() {
  let canvas = createCanvas(400, 400);
  canvas.parent('canvas');
  background(50);
}

function draw() {
  const width = 400;
  while (true) {
    monteCarlo(width);
    trials++;
    // results
    if (trials % 50 == 0) {
      // 1フレームに50回計算する。
      break;
    }
  }
  let pi = t_inner * 4 / trials;

  // グラフにデータを追加
  addData(pi);
  // 結果表示
  document.getElementById('result').innerHTML = pi;
  document.getElementById('trials').innerHTML = trials;
  document.getElementById('t_inner').innerHTML = t_inner;
}
```

**p5js**では`setup()`でキャンバスを作成して、`draw()`でフレーム処理を行います。
演算速度を早めるため、１フレームに50個の点をプロットしています。


```js
function monteCarlo(width) {
  var x = Math.random(); // 0 ~ 1.0の乱数
  var y = Math.random(); // 0 ~ 1.0の乱数
  var r = Math.sqrt(x * x + y * y);

  let isInner = false;
  if (r < 1) {
    isInner = true;
    t_inner++;
  }
  plotEllipse(x * width, y * width, isInner);
}
```

モンテカルロ法のアルゴリズム部分。
内側の点の数を数えます。

キャンバスの大きさ`width`をかけて、点の座標と内側かどうかを渡す。

```js
function plotEllipse(x, y, isInner) {
  // color of outer points
  let c = color(255);
  if (isInner) {
    // color of inner points
    c = color(25, 254, 0);
  }
  fill(c);
  noStroke();
  ellipse(x, y, 1, 1);
}
```

点を描画する関数。円の内側の点を緑、外側を白とする。
点を描くときは、`point()`ではなく`ellipse()`を使いましょう。

```js
var series_calc = null;
var series_pi = null;

function createResultChart() {
  var chart = am4core.create("chartdiv", am4charts.XYChart);

  // X軸
  var valueAxisX = chart.xAxes.push(new am4charts.ValueAxis());
  valueAxisX.title.text = 'number of trials';
  valueAxisX.renderer.minGridDistance = 50;
  // スケール固定
  valueAxisX.min = 0;
  // valueAxisX.max = trials - 1;

  var valueAxisY = chart.yAxes.push(new am4charts.ValueAxis());
  valueAxisY.title.text = 'π';
  // スケール固定
  valueAxisY.min = 3.1;
  valueAxisY.max = 3.2;


  var data = [{ trials: 0, calculated: 0, pi: Math.PI }];

  series_calc = createCalculatedSeries(chart);
  series_calc.data = data;
  series_pi = createPiSeries(chart);
  series_pi.data = data;

  chart.cursor = new am4charts.XYCursor();
  chart.cursor.xAxis = valueAxisX;

  chart.legend = new am4charts.Legend();
  // chart.scrollbarY = new am4core.Scrollbar();

  return;
}

function createCalculatedSeries(chart) {
  var series = chart.series.push(new am4charts.LineSeries());
  series.name = "calculated π";
  series.dataFields.valueY = "calculated";
  series.dataFields.valueX = "trials";
  series.tooltipText = "{valueY}";
  return series;
}

function createPiSeries(chart) {
  var series = chart.series.push(new am4charts.LineSeries());
  series.name = "theoretical π";
  series.dataFields.valueY = "pi";
  series.dataFields.valueX = "trials";
  series.tooltipText = "{valueY}";
  return series;
}

function addData(pi) {
  let data = { trials: trials, calculated: pi, pi: Math.PI };
  series_calc.addData(data, 0); // 第二引数はpush
  series_pi.addData(data, 0); // 第二引数はpush
}
```

グラフの部分。
グラフの作成とシミュレーション結果をグラフに追加していきます。
大体[眺めていられる遺伝的浮動(genetic draft)のシミュレーション](https://www.suzu6.net/posts/57-genetic-draft)と同じ。

`addData()`は`draw()`の中で呼び、フレームを合わせています。


```js
function restart(){
  trials = 0;
  t_inner = 0;
  series_calc = null;
  series_pi = null;
  chartInit();
  setup();
}
```
再計算するリセットの関数。

## 終わりに

少数２桁の精度でも意外と収束に時間がかかるんですね。

## 参考

- [Wiki](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%AB%E3%83%AD%E6%B3%95)
- [モンテカルロ法のお話 - 産業技術総合研究所](https://unit.aist.go.jp/diversity/ja/jst/teens/montecarlo.htm)
- [モンテカルロ法を用いた円周率の近似値算出 | みんなのメモ帳](https://yoshipc.net/mc-pi/)

眺めていられるモンテカルロ法で円周率の近似を求めるシミュレーション|JavaScript


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

そんな訳で、昔学んだ遺伝学から**遺伝的浮動のシミュレーション**を自分で作ったら、好きなだけぼーっとできるのではないかと思い立ちます。
是非、眺めてやって下さい。

ブラウザはChromeを推奨！

## 遺伝的浮動 (genetic draft)

このブログを見にくる方々はエンジニアが多いと思うので、簡単にですが説明します。

遺伝子が変異しても生物の生存に有利でも不利でもないものがあります。
集団の中でその変異型の遺伝子を持つ割合を**遺伝子頻度**と言います。
**遺伝的浮動(genetic draft)**とは、ある集団の持つ遺伝子の頻度が世代を経て偶発的に変動する様です。

シミュレーションでは、変異型の遺伝子が生存や生殖成功率に関して何の影響もないと仮定しています。
次の世代の遺伝子頻度は、親世代から無作為に選ばれた遺伝子を引継ぐとして算出しています。

詳しくは、[Introduction to population genetics simulation](http://www.biology.kyushu-u.ac.jp/~kteshima/Information/20170802_simulation_with_random_number.html)
を参照して下さい。
以下のシミュレーションもこちらを参考に作成しました。

## シミュレーション

とりあえず、眺めて見ましょう。


<div id="chartdiv" class="chart"></div>
<div id="chartdivfixation" class="chart-harf"></div>
<div id="chartdivlost" class="chart-harf"></div>


一番目のグラフが遺伝子頻度(frequency)をあわらします。
0世代目は50%から始めて、各世代(generations)の頻度の変化を計算しています。
同時に10個ずつ計算。

集団サイズNは300にしてあります。

下の２つは、その集団で**遺伝子が完全に広がるまでの世代数**（Time until fixation）と**遺伝子が集団から消失するまでの世代数**(Time until lost)をカウントしています。
試行回数を多く取ると二項分布になります。
ニョキニョキしているところをみながら気長に待つと、段々とそれっぽい分布があるような気がしてきます。

## ソースコード


集団サイズや初期の頻度を変えるとまた違った分布になります。

グラフは[amCharts 4](https://www.amcharts.com/)で書いています。

設定もいじれるように拡張中です。。。

### html

```html
<div id="chartdiv" class="chart"></div>
<div id="chartdivfixation" class="chart-harf"></div>
<div id="chartdivlost" class="chart-harf"></div>

<script src="https://www.amcharts.com/lib/4/core.js"></script>
<script src="https://www.amcharts.com/lib/4/charts.js"></script>
<script src="https://www.amcharts.com/lib/4/themes/material.js"></script>
<script src="https://www.amcharts.com/lib/4/themes/animated.js"></script>
<script src="/images/posts/57/genetic_draft.js"></script>


<style>
.chart {
  width: 100%;
  height: 400px;
}
.chart-harf {
  width: 100%;
  height: 200px;
}
</style>
```

### javascript

```js
{
  window.onload = function () {
    ini();
  }

  var size = 300;
  var derived = 150;

  var GEN_MAX = 500;
  var count_lost_chart = null;
  var count_fixation_chart = null;
  var frequecy_chart = null;
  var draft_num = 0;
  var parallel_num = 10;
  var interval_msec = 10;

  function ini(){
    // グラフ描画
    am4core.useTheme(am4themes_animated);
    frequecy_chart = createFrequencyChart();
    count_lost_chart = createCounter("lost");
    count_fixation_chart = createCounter("fixation");
  }

  function createFrequencyChart() {
    var chart = am4core.create("chartdiv", am4charts.XYChart);

    // X軸
    var valueAxisX = chart.xAxes.push(new am4charts.ValueAxis());
    valueAxisX.title.text = 'Generations';
    valueAxisX.renderer.minGridDistance = 50;
    // スケール固定
    valueAxisX.min = 0;
    valueAxisX.max = GEN_MAX - 1;

    var valueAxisY = chart.yAxes.push(new am4charts.ValueAxis());
    valueAxisY.title.text = 'frequecy';
    // スケール固定
    valueAxisY.min = 0;
    valueAxisY.max = 1;


    for (let n = 1; n <= parallel_num; n++) {
      let series = createSeries(chart);
      addData(series);
    }

    chart.cursor = new am4charts.XYCursor();
    chart.cursor.xAxis = valueAxisX;

    return chart;
  }

  function createCounter(id) {
    var chart = am4core.create(`chartdiv${id}`, am4charts.XYChart);
    chart.data = initCounterData(GEN_MAX);

    // X軸
    var categoryAxis = chart.xAxes.push(new am4charts.ValueAxis());
    // categoryAxis.title.text = 'Generations';
    categoryAxis.renderer.minGridDistance = 50;

    var valueAxisY = chart.yAxes.push(new am4charts.ValueAxis());
    valueAxisY.title.text = `Time until ${id}`;


    // Create series
    var series = chart.series.push(new am4charts.StepLineSeries());
    series.dataFields.valueY = "count";
    series.dataFields.valueX = "generation";
    series.tooltipText = "{valueY}";
    series.fillOpacity = 0.1;
    series.defaultState.transitionDuration = 10;
    series.hiddenState.transitionDuration = 10;

    chart.cursor = new am4charts.XYCursor();
    chart.cursor.xAxis = categoryAxis;

    
    return chart;
  }

  function initCounterData(gen_max) {
    var data = [];
    for (var i = 0; i < gen_max; i += 10) {
      data.push({ generation: i, count: 0 });
    }
    return data;
  }

  function createSeries(chart) {

    // Create series
    var series = chart.series.push(new am4charts.LineSeries());
    series.dataFields.valueY = "frequency";
    series.dataFields.valueX = "generation";
    series.tooltipText = "{valueY}";
    series.defaultState.transitionDuration = 10;
    series.hiddenState.transitionDuration = 400;

    return series;
  }

  function addData(series) {
    var gen = 0;
    var p = derived / size;
    var data = [{ generation: gen, frequency: p }];

    series.data = data;

    var calc = function () {
      p = calcNextGeneration(p, size);
      series.addData({ generation: gen++, frequency: p }, 0); // 第二引数はpush
      if (gen > GEN_MAX) {
        return true;
      }
      else if (p == 0) {
        // gene lost
        count_lost_chart.data[Math.floor(gen / 10)].count++;
        count_lost_chart.data = count_lost_chart.data;
        return true;
      }
      else if (p == 1) {
        // gene fixation
        count_fixation_chart.data[Math.floor(gen / 10)].count++;
        count_fixation_chart.data = count_fixation_chart.data;
        return true;
      }
      return false;
    }

    // add data
    var interval;
    function startInterval(calc) {
      interval = setInterval(function () {
        var res = calc();
        if (res) {
          clearInterval(interval);
          addData(series);
          console.log(draft_num);
        }
      }, interval_msec);
    }

    startInterval(calc);
  }

  function calcNextGeneration(p, size) {
    var derived = 0;
    for (let i = 0; i < size; i++) {
      if (Math.random() < p) {
        derived++;
      }
    }
    return derived / size;
  }

}
```

<script src="https://www.amcharts.com/lib/4/core.js"></script>
<script src="https://www.amcharts.com/lib/4/charts.js"></script>
<script src="https://www.amcharts.com/lib/4/themes/material.js"></script>
<script src="https://www.amcharts.com/lib/4/themes/animated.js"></script>
<script src="/images/posts/57/genetic_draft.js"></script>


<style>
.chart {
  width: 100%;
  height: 400px;
}
.chart-harf {
  width: 100%;
  height: 200px;
}
</style>


---

JavaScriptを初めて学ぶ方へのオススメ！
実際にプログラミングを書いて覚えられるので、オンラインでの学習と合わせて読み進めると理解が深まると思います。

<div class="cstmreba"><div class="booklink-box"><div class="booklink-image"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F13430282%2F" target="_blank" rel="nofollow" ><img src="https://thumbnail.image.rakuten.co.jp/@0_mall/book/cabinet/3584/9784797383584.jpg?_ex=200x200" style="border: none;" /></a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="booklink-info"><div class="booklink-name"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F13430282%2F" target="_blank" rel="nofollow" >確かな力が身につくJavaScript「超」入門</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"><div class="booklink-powered-date">posted with <a href="https://yomereba.com" rel="nofollow" target="_blank">ヨメレバ</a></div></div><div class="booklink-detail">狩野祐東 SBクリエイティブ 2015年10月31日    </div><div class="booklink-link2"><div class="shoplinkrakuten"><a href="//af.moshimo.com/af/c/click?a_id=1286797&p_id=56&pc_id=56&pl_id=637&s_v=b5Rz2P0601xu&url=http%3A%2F%2Fbooks.rakuten.co.jp%2Frb%2F13430282%2F" target="_blank" rel="nofollow" >楽天ブックス</a><img src="//i.moshimo.com/af/i/impression?a_id=1286797&p_id=56&pc_id=56&pl_id=637" width="1" height="1" style="border:none;"></div><div class="shoplinkamazon"><a href="https://www.amazon.co.jp/exec/obidos/asin/4797383585/suzu60c-22/" target="_blank" rel="nofollow" >Amazon</a></div><div class="shoplinkkindle"><a href="https://www.amazon.co.jp/gp/search?keywords=&__mk_ja_JP=%83J%83%5E%83J%83i&url=node%3D2275256051&tag=suzu60c-22" target="_blank" rel="nofollow" >Kindle</a></div>                              	  	  	  	  	</div></div><div class="booklink-footer"></div></div></div>