ワイ「スリープソート？　寝ている間に小人さんがソートしてくれるんでっか？」

社長「[やめ太郎](https://qiita.com/Yametaro)くん」

ワイ「なんでっか社長」

社長「**画期的なソートアルゴリズム**をJavaScriptで書いたから見てくれや」

ワイ「ソートアルゴリズムちゅうのは配列を数字が小さい順に並べ替えてくれるやつでんな」

ワイ「（どうせ**バブルソート**とかやろ）」

社長「これや」

```js
function sleep(duration) {
  return new Promise(resolve => setTimeout(resolve, duration));
}
function sleepSort(arr) {
  const result = [];
  return Promise.all(
    arr.map(elm => sleep(elm * 100).then(() => result.push(elm)))
  ).then(() => result);
}

sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]).then(console.log);
// 1秒後に [1, 1, 1, 2, 3, 3, 4, 4, 6, 10] と表示される
```

ワイ「**[スリープソート](https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88#%E3%82%B9%E3%83%AA%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88)やないかい！**」

※この記事は全編[やめ太郎](https://qiita.com/Yametaro)さんリスペクトでお送りします。（[3週間ぶり2回目](https://qiita.com/uhyo/items/da4a764f313a3b795d59)）

## スリープソートを読み解く

ワイ「思わず突っ込んでもうたけど何やっとんのか全然分からんで」

ワイ「**スリープソート**っちゅうんは**寝ている間に小人がソートしてくれる**っちゅうことでっか？」

社長「んなわけあるかい！」

社長「これはタイマーを使うことで複雑なロジックを書かんでもソートができる画期的なアルゴリズムや」

ワイ「それだけ聞いてもどんなソートなのか全然分かりまへんわ」

社長「仕方あらねんなあ、ワイ自ら解説したるで（ワイって一人称ワイで合っとるんか？　みんな一人称同じやんけ）」

社長「まず結果の配列を用意する。これはまあええやろ」

```js
const result = [];
```

社長「そして与えられた配列の各要素に対して`sleep(elm * 100).then(() => result.push(elm))`を実行するんや」

社長「ここでいくらか時間がかかるからそれを待つんや」

社長「`Promise.all`っちゅうのは全部の要素が終わるまでしっかり待つっちゅうことやな」

社長「そして全部終わったら`result`を返す」

ワイ「社長アホになったんでっか？　`sleepSort`に`return result;`なんて書いとらんやん」

社長「お前本当にJavaScript書いとんのか？　**非同期処理なんだからPromiseに包んで値を返すのは当たり前**やん」

社長「最後の`.then(() => result)`で処理が全部終わったら`result`っちゅう結果をPromiseに包んで返すことを表しとるんや」

ワイ「（そもそもソートを非同期処理にする方がどうかしとるんちゃうか）」

[ハリー先輩](https://qiita.com/Yametaro/items/831d23536ae1310447e6)「（こいつソートを並列化したこと無いんか）」

ワイ「じゃあ`sleep(elm * 100).then(() => result.push(elm))`はどういう意味でっか」

社長「`sleep`ってのは与えられたミリ秒数だけ経ったら解決されるPromiseを返す関数や」

社長「そしてそのPromiseが解決されたら`result`に`elm`を追加する」

社長「つまり`elm * 100`ミリ秒後に`result`に`elm`を追加するっちゅうことや」

ワイ「`elm`ってのは配列の要素やから」

ワイ「`elm`が1なら100ミリ秒後、2なら200ミリ秒後に`result`に`1`とか`2`が追加されるわけでんな」

社長「せや」

社長「小さい数ほど先に`result`に追加されるから全部追加し終えたらソートが完了しとるっちゅうわけや」

ワイ「この`sleep`っちゅうのは`arr.map`で各要素に対して実行されとるけど」

ワイ「配列の各要素に対して順番に実行されるんでっか」

社長「ちゃうで」

社長「`Promise`で表されるのは**非同期処理**や」

ハリー先輩「**非同期処理**っちゅうのは終わるまでボケっと待っとらんでもええってことやで」

社長「つまり一つ一つが終わるのを待たんでも全部同時に`sleep(elm * 100)`が走るんや」

ハリー先輩「つまり`elm * 100`秒後に`result`に`elm`を追加するっちゅう処理が全要素同時に始まるっちゅうことや」

社長「どや、画期的やろ」

ワイ「これ**負の数はどうするんでっか**」

社長「**適当にゲタ履かせときゃええやろ**」

ワイ「**1000000とか渡されたら1日以上待つんでっか**」

社長「あー忙し、仕事しよ」

ワイ「**社長！**」

## スリープソートを高速化してみた

[ハスケル子](https://qiita.com/Yametaro/items/11dcd3ec26027ff30214)「やめ太郎さん」

ワイ「何や（この筆者ハスケル子好きやな……）」

ハスケル子「スリープソートを高速化してみたんですけど」

ワイ「ほう、見せてみい」

```js
async function sleep(duration) {
  for (let i = 0; i < duration; i++) {
    await null;
  }
}
function sleepSort(arr) {
  const result = [];
  return Promise.all(
    arr.map(elm => sleep(elm).then(() => result.push(elm)))
  ).then(() => result);
}

sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]).then(console.log);
// すぐに [1, 1, 1, 2, 3, 3, 4, 4, 6, 10] と表示される
```

ハスケル子「これです」

ワイ「`sleep`関数が変わっただけやな」

ワイ「おお、一瞬でソートが終わったで」

ワイ「でも`sleep`関数の意味が分からんわ」

ハスケル子「これは**`async`関数**です」

ワイ「返り値が自動的に`Promise`になるやつやな」

ハスケル子「`await null;`がポイントで」

ハスケル子「これは**一瞬待つ**って意味です」

ワイ「ほお」

ハスケル子「つまり`elm`が`1`なら一瞬待って」

ハスケル子「`elm`が`2`なら二瞬、`elm`が`3`なら三瞬待ちます」

ワイ「**は？**」

ハスケル子「つまり`elm * 100`ミリ秒待つ代わりに`elm`瞬待つようにして高速化したんです」

ワイ「説明聞いてもやっぱり意味が分からんわ」

## イベントループ

ハスケル子「最近のJavaScript処理系は**イベントループ**という仕組みを持っています」

ハスケル子「JavaScriptは非同期といっても全部シングルスレッドで動くので」

ハスケル子「非同期処理のコールバックが呼ばれる場合は今実行している処理が終わってからそっちに移るんです」

ワイ「溜まっとる一個一個の処理をループで順番に処理していくからイベントループってわけやな」

ハスケル子「`await null`はループ一周分待つってことなんです」

ワイ「はあ」

ワイ「でもそれがスリープソートと何の関係があるんや」

ハスケル子「まだ理解できないんですか……　じゃあちょっとさっきのコードを書きなおしてみましょう」

```js
function sleep(duration) {
  let i = 0;
  const loop = () => {
    if (i < duration) {
      i++;
      return Promise.resolve(null).then(loop);
    } else {
      return null;
    }
  };
  return loop();
}
function sleepSort(arr) {
  const result = [];
  return Promise.all(
    arr.map(elm => sleep(elm).then(() => result.push(elm)))
  ).then(() => result);
}

sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]).then(console.log);
// すぐに [1, 1, 1, 2, 3, 3, 4, 4, 6, 10] と表示される
```

ワイ「`sleep`の中がますます意味不明になったで」

ハスケル子「さっきのコードを`async`と`await`を使わずに生のPromiseを使うように書きなおしただけです」

ワイ「async/awaitが分かとっらん読者もおるかもしれんけど本題とは関係ないから省略するで」

ハスケル子「こういうふうに`Promise.resolve`で作られたPromiseは一瞬で解決されます」

ハスケル子「つまり、それに`then`でつなげた関数はイベントループの**次のループ**で呼び出されるんです」

ワイ「はあ」

ハスケル子「じゃあイベントループを自分で再現してみましょう」

```js
const events = [];
// ソートの結果
const result = [];
// 最初に実行する処理を登録
events.push(() => sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]));
// ここからイベントループの処理
while (events.length > 0) {
  // eventsの先頭から1つ取り出して呼び出す
  const nextEvent = events.shift();
  nextEvent();
}
// イベントループが終わったらresultを表示
console.log(result);

function sleep(elm, callback) {
  let i = 0;
  const loop = () => {
    // イベントループ1回の処理
    if (i < elm) {
      i++;
      events.push(loop);
    } else {
      // ループが終了したのでコールバックを呼ぶ
      callback();
    }
  };
  return loop();
}
function sleepSort(arr) {
  for (const elm of arr) {
    // 各elmに対する処理を実行
    sleep(elm, () => result.push(elm));
  }
}

```

ワイ「一気にコードが長くなって読むのがつらいで」

ワイ「でも**イベントループ**っちゅうのがどこかは分かるで」

ワイ「`while (events.length > 0)`のところやな」

ハスケル子「そうです、イベントループは`events`に登録された関数を順番に呼び出すだけです」

ハスケル子「`sleepSort`関数は`arr`の各要素に対する処理を別々にイベントループに登録します」

ワイ「`sleep(elm).then(()=> result.push(elm))`が`sleep(elm, ()=> result.push(elm))`になっとるで」

ハスケル子「`then`を実装するのが面倒なので`sleep`にコールバックを渡す形にしたんです」

ワイ「`sleep`関数の中は`Promise.resolve(null).then(loop)`が`events.push(loop)`に変わっとるで」

ハスケル子「`Promise.resolve(null)`は一瞬で解決されるので、それに`then`した`loop`は次のイベントループで呼び出されるんです」

ハスケル子「だから自前のイベントループを使うためにこう直しました」

ワイ「なるほどな」

## スリープソートを最適化してみる

ワイ「何となく分かったから自分でちょっとコードをいじってみるで」

ワイ「まずイベントループは`sleepSort`関数の中に押し込んでもええやろ」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  const events = [];
  for (const elm of arr) {
    // 各elmに対する処理を実行
    sleep(elm, () => result.push(elm));
  }
  while (events.length > 0) {
    // eventsの先頭から1つ取り出して呼び出す
    const nextEvent = events.shift();
    nextEvent();
  }
  return result;
  function sleep(elm, callback) {
    let i = 0;
    const loop = () => {
      // イベントループ1回の処理
      if (i < elm) {
        i++;
        events.push(loop);
      } else {
        // ループが終了したのでコールバックを呼ぶ
        callback();
      }
    };
    loop();
  }
}
```

ワイ「`events`配列の中に関数を突っ込むのはようわからんわ」

ワイ「スリープソート専用にして`i`と`elm`を覚えといてくれるオブジェクトにするで」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  const events = [];
  for (const elm of arr) {
    // 各elmに対する処理を実行
    sleep(elm);
  }
  while (events.length > 0) {
    // eventsの先頭から1つ取り出して呼び出す
    const { i, elm } = events.shift();
    if (i < elm) {
      events.push({
        i: i + 1,
        elm
      });
    } else {
      result.push(elm);
    }
  }
  return result;
  function sleep(elm) {
    events.push({
      i: 0,
      elm
    });
  }
}
```

ハスケル子「なんか`sleep`の中身がすっきりしてイベントループの中にベタ書きになりましたね」

ワイ「もう`sleep`とか要らんから消すわ」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  const events = [];
  for (const elm of arr) {
    // 各elmに対する処理を実行
    events.push({
      i: 0,
      elm
    });
  }
  while (events.length > 0) {
    // eventsの先頭から1つ取り出して呼び出す
    const { i, elm } = events.shift();
    if (i < elm) {
      events.push({
        i: i + 1,
        elm
      });
    } else {
      result.push(elm);
    }
  }
  return result;
}
```

ハスケル子「あの」

ハスケル子「この`i`ってオブジェクトの中に入れる必要無くないですか？」

ワイ「せやろか」

ハスケル子「`i`は最初みんな`0`で」

ハスケル子「みんな一緒に`i`が増えていって`elm`に達したやつが`result.push(elm)`されるんですよね」

ハスケル子「なので`i`は別々に持つんじゃなくて共通にしましょう」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  let events = [];
  for (const elm of arr) {
    // 各elmに対する処理を実行
    events.push({
      elm
    });
  }
  for (let i = 0; events.length > 0; i++) {
    const nextEvents = [];
    while (events.length > 0) {
      const { elm } = events.shift();
      if (i < elm) {
        nextEvents.push({
          elm
        });
      } else {
        result.push(elm);
      }
    }
    events = nextEvents;
  }
  return result;
}
```

ワイ「なんか随分変わりよったなあ」

ハスケル子「次のイベントループに登録するものは`events`に直にpushするんじゃなくて`nextEvents`を作ってそっちにpushするようにしました」

ワイ「なんで？」

ハスケル子「今の`i`の処理が終わったら`i`を増やしてから次のイベントループに行きたいので今の`i`に対する処理と混ざらないようにするためです」

ワイ「さよか（難しくなってきたで、若者の考えることはよう分からんわ）」

ワイ「でもこれ`events`の中身のオブジェクトが`elm`しか値を持たんから数値を直に入れてもええやろ」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  let events = [];
  for (const elm of arr) {
    events.push(elm);
  }
  for (let i = 0; events.length > 0; i++) {
    const nextEvents = [];
    while (events.length > 0) {
      const elm = events.shift();
      if (i < elm) {
        nextEvents.push(elm);
      } else {
        result.push(elm);
      }
    }
    events = nextEvents;
  }
  return result;
}
```

ハスケル子「でも」

ワイ「今度は何や」

ハスケル子「これもう`i`要らなくないですか？」

ワイ「なんでや」

ハスケル子「`i`がどんどん増えていって`elm`に到達したやつから`result`にpushされるんですよね」

ワイ「せやな（これそういう意味なんか、やっと分かったで）」

ハスケル子「ということは一番小さい`elm`が最初に`result`にpushされますよね」

ワイ「せやな」

ハスケル子「じゃあ一番小さい`elm`を直接探せばいいんじゃないですか？」

ハスケル子「`i`は要らない子ですね」

ワイ「（**`i`を要らない子にしたのはお前やろ！**）」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  let events = [];
  for (const elm of arr) {
    events.push(elm);
  }
  while (events.length > 0) {
    // 一番小さいelmを探す
    let minElm = Infinity;
    for (const elm of events) {
      if (elm < minElm) {
        minElm = elm;
      }
    }
    // eventsの中から一番小さいelmをresultに入れて他はnextEventsに入れる
    const nextEvents = [];
    for (const elm of events) {
      if (minElm === elm) {
        result.push(elm);
      } else {
        nextEvents.push(elm);
      }
    }
    events = nextEvents;
  }
  return result;
}
```

ワイ「やっとることは分かったけど」

ワイ「なんか`nextEvents`を毎回作っとるのが気に入らんで」

ハスケル子「じゃあ作らないようにしましょう」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  const events = [];
  for (const elm of arr) {
    events.push(elm);
  }
  while (events.length > 0) {
    // 一番小さいelmを探す
    let minElm = Infinity;
    for (const elm of events) {
      if (elm < minElm) {
        minElm = elm;
      }
    }
    // eventsの中から一番小さいelmを抜き出してresultに入れる
    for (let k = 0; k < events.length; k++) {
      const elm = events[k];
      if (minElm === elm) {
        result.push(elm);
        // eventsからk番目を抜く
        events.splice(k, 1);
        // 次の要素がk番目に来るので調整のためにkを減らす
        k--;
      }
    }
  }
  return result;
}
```

ハスケル子「`nextEvents`を作る代わりに`events`から`splice`を使って抜き出していくようにしました」

ワイ「なるほどな」

ハリー先輩「動くな、**計算量警察**や」

ワイ「は？」

ハリー先輩「`splice`は$O(N)$かかる計算や」

ハリー先輩「さっきまで$O(N^2)$だったアルゴリズムが$O(N^3)$になったんとちゃうか？」

ハスケル子「くっ……」

ワイ「（なんの話しとるのかさっぱり分からんで）」

ワイ「（[前回の話](https://qiita.com/uhyo/items/da4a764f313a3b795d59)では**英語の仕様書を一瞥しただけで理解できる天才**だったのにどうしてこうなったんや）」

（1時間後）

ハスケル子「！！！」

ハスケル子「待ってください、`splice(k, 1)`は配列の`k`番目以降を全部前にずらすのが$O(N)$の理由です」

ハスケル子「ということは`for (let k = 0; k < events.length; k++)`というforループと合わせればこれは全体として配列全体を1回舐めているだけ、よって$O(N)$です」

ワイ「（ちくわ大明神）」

ハリー先輩「だとしたら`splice(k, 1)`の後に`break;`が必要なんとちゃうか？」

ハスケル子「あっ……」

ハスケル子「でも`splice`を呼ぶと一番外側のループの回数がひとつ減るから……」

（1時間後）

ハスケル子「でも`minElm`を持つ`elm`が複数あったときにもう一度最小値を探しなおすのは無駄ですよね」

ワイ「（話についていけなくて飽きてきたで）」

ハリー先輩「じゃあこういうときに使えるテクニックを教えたるで」

ハリー先輩「要素を全部動かすんやなくて要素の入れ替えを使うんや」

ワイ「お、やっと2人が次のコードを書き始めたで」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  for (const elm of arr) {
    result.push(elm);
  }
  // まだソートされていない部分の開始位置
  let start = 0;
  while (start < result.length) {
    // 一番小さいelmを探す
    let minElm = Infinity;
    for (let k = start; k < result.length; k++) {
      const elm = result[k];
      if (elm < minElm) {
        minElm = elm;
      }
    }
    // resultの中から一番小さいelmを探す
    for (let k = start; k < result.length; k++) {
      const elm = result[k];
      if (minElm === elm) {
        // elmをstart番目に入れて代わりに今start番目にあるやつをk番目に移動
        result[k] = result[start];
        result[start] = elm;
        // start番目はソート済み
        start++;
      }
    }
  }
  return result;
}
```

ワイ「なんか元のコードの面影はあるけどまた大分変わってもうたで」

ワイ「`events`も`nextEvents`も消えて`result`だけになってもうたわ」

ハリー先輩「このコードでは`result`は2つの意味を持つで」

ハリー先輩「前半、つまり`start`番目より前はソート済みでそれより後は未ソートや」

ワイ「最初`start`が0ってことはまだなんもソートされてないっちゅうことでんな」

ハスケル子「配列から最小値を見つける部分は同じですが」

ハスケル子「`start`番目より前は既に処理済みなので`start`番目以降から探すようになってます」

ハリー先輩「そして最小値`elm`を見つけたらそれを処理済み部分に付け足すんや」

ハリー先輩「つまり`start`番目に移動させてやって`start`を1増やしてやる」

ハスケル子「もともと`start`番目にあった`result[start]`はまだソートされていないですが」

ハスケル子「ちょうど`elm`があった位置である`k`番目が空いてるのでそこに入れておきます」

ハリー先輩「ここがポイントやな」

ハスケル子「要素の入れ替えによりソートを進めることで`splice`による**配列をずらす操作**を無くしているんです」

ハリー先輩「これなら誰が見ても計算量は$O(N^2)$や」

## まとめ

ワイ「ところで」

ハリー先輩「ん？」

ワイ「**これだとソートの安定性が失われるんとちゃいますか？**」

ハスケル子「えっ……確かにそうですが」

ハリー先輩「誰やお前、さっきまでアホ面して半分寝とったあいつはどこに行ったんや」

ワイ「お前人様のキャラに向かって言っていいことと悪いことがあるで」

ワイ「てかなあ」

ハリー先輩「おう」

ワイ「これただの**[選択ソート](https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88)**やんけ！」

**スリープソートを最適化したら選択ソートになった話**　〜完〜

<br>

<br>

### おまけ

ハスケル子「というか」

ワイ「なんや」

ハスケル子「**計算量警察以降の話って無駄じゃないですか？**」

ワイ「**せやな**」

ワイ「正直、`i`が消えた段階（↓）で既に**選択ソート**になっとると思うんやけど」

```js
const result = sleepSort([1, 3, 6, 2, 1, 4, 10, 1, 4, 3]);
console.log(result);

function sleepSort(arr) {
  const result = [];
  let events = [];
  for (const elm of arr) {
    events.push(elm);
  }
  while (events.length > 0) {
    // 一番小さいelmを探す
    let minElm = Infinity;
    for (const elm of events) {
      if (elm < minElm) {
        minElm = elm;
      }
    }
    // eventsの中から一番小さいelmをresultに入れて他はnextEventsに入れる
    const nextEvents = [];
    for (const elm of events) {
      if (minElm === elm) {
        result.push(elm);
      } else {
        nextEvents.push(elm);
      }
    }
    events = nextEvents;
  }
  return result;
}
```

ワイ「**選択ソート**でググっても要素の入れ替えを使って並び替えるのが選択ソートやっちゅう説明しか出てこんかったから無理やりそこまで持ってったんや」

ハスケル子「まあメモリ使用量が違いますからね」

ワイ「てか要素の入れ替えを使うとかプログラム書き換えすぎやろ、それでスリープソートが選択ソートになってもなんも面白ないで」

ワイ「見た目変わってるけど考え方は変わってないでってアピールするのが大変だったわ」

ハスケル子「**アピール失敗してますよそれ**」

ハスケル子「最後だけ説明が長くてコードが全然出てこないし」

ワイ「まあ**ソートアルゴリズムの本質**を分かっとる奴はあの段階でピンと来とったやろ」

ワイ「そうでない奴らから何言われたって痛くないで」

ハスケル子「（何で最後の最後に喧嘩売るんですかこの人は）」

〜完〜