👨‍💻

sleepソートのアルゴリズムがおもしろい

2023/10/14に公開

JavaScript

アルゴリズム

ソート

tech

自分が知ってたソートアルゴリズムの常識を覆すようなアルゴリズムを知って興奮してしまったので実際に動かしてみた記録です。

今日X（旧Twitter）でこういう投稿を見かけました！😃
どうやらsleep処理を用いて配列内の数値をソートしてくれるアルゴリズムのようです🧐

「数値分だけsleepした上でその数値を配列に詰める」という処理を非同期で実行すれば確かに順番に並びそうだなぁと興奮してしまいました笑
なので実際に手元で書き起こして試してみました！

const sleepSort = async (numbers: number[]): Promise<number[]> => {
  const result: number[] = [];

  const makeSleepPromise = (number: number) => {
    return new Promise((resolve) => {
      return setTimeout(() => {
        result.push(number);
        resolve(null);
      }, number);
    });
  };

  await Promise.all(numbers.map(makeSleepPromise));
  return result;
};

(async () => {
  const sortedNumbers = await sleepSort([6, 10, 5, 13, 2, 11, 1, 0, 3]);
  console.log(sortedNumbers);
})();

以下は実行結果。

[0, 1, 2, 3, 5, 6, 10, 11, 13]

確かに数値が小さい順に並んでいる😅
そしてアルゴリズムが面白すぎる😂

以下のTS公式のPlaygroundですぐに確認出来ます！

唯、この実装だと以下のような制約があります😢

大きい数値をソートする場合は時間がかかってしまう
負の数値をソートできない
数値以外の値（object等）をソート出来ない

大きい数値をソートする場合は時間がかかってしまう

に関しては仕方無いなと思いました。

指定した関数やコードを実行する前に待つタイマーの時間をミリ秒 (1/1000 秒) 単位で指定します。
また、値が数値でない場合、暗黙のうちに型強制が行われ、数値に変換されることにも注意してください。
https://developer.mozilla.org/ja/docs/Web/API/setTimeout

10分の1ミリ秒（0.1）等で指定するようであれば暗黙の型変換でint型になるようでして、
0.1をint型に変換する（parseInt(0.1)）すると0になるので、
このアルゴリズムのソートロジックが成立しなくなります。

負の数値をソートできない

に関しては、負の数値と正の数値を別々にソートすればいけると思います。
負の数値はsetTimeoutでは対応していないので、
絶対値を取ってソートした後にリバースする必要がありますが😅

type NumberType = 'plus' | 'minus';

const sleepSort = async (numbers: number[]): Promise<number[]> => {
  const resultPlusNumbers: number[] = [];
  const resultMinusNumbers: number[] = [];

  const makeSleepPromise = (number: number, type: NumberType) => {
    return new Promise((res) => {
      return setTimeout(() => {
        if (type === 'minus') {
          resultMinusNumbers.push(number);
        } else {
          resultPlusNumbers.push(number);
        }
        res(null);
      }, number);
    });
  };

  const plusNumbers = numbers.filter((number) => 0 <= number);
  const minusNumbers = numbers.filter((number) => number < 0).map((number) => Math.abs(number));

  await Promise.all([
    ...minusNumbers.map(number => makeSleepPromise(number, 'minus')),
    ...plusNumbers.map(number => makeSleepPromise(number, 'plus')),
  ]);
  return [
    ...resultMinusNumbers.map((number) => -number).reverse(),
    ...resultPlusNumbers,
  ];
};

(async () => {
  const sortedNumbers = await sleepSort([1, 0, 2, -12, 3, 4, -5, -11, 8]);
  console.log(sortedNumbers);
})();

数値以外の値（object等）をソート出来ない

に関しては、sleepSortWithKeyみたいな関数にして数値が入ってるkey名を貰えば実装出来るかと思うので特に試していないです。

言語仕様に関わってくるところもありますが、
このアルゴリズムは任意の大きい数値の入力に対してソートが遅くなるというところが致命的で
バブルソートやクイックソートに置き換わるものでは無いですが、
ただただアルゴリズムがおもしかったです笑

Discussion