【JavaScript】スリープソートの紹介と実装

 世の中には様々な並び替えアルゴリズム(以降ソートアルゴリズム)が存在します。高級言語を使っていると言語組み込みのソート機能が手製ソートより遥かに高速なことが多いため普段は意識しませんが、アルゴリズムの勉強などをすると様々なソートアルゴリズムが見つかります。ソートアルゴリズムの中には時にはジョークアルゴリズムとでもいうべき実用的でないアルゴリズムもあります。比較的近年話題になったものではスターリンソートなどがあります。

【PHP】のスターリンソートがけっこうそれっぽい – 株式会社シーポイントラボ | 浜松のシステム・RTK-GNSS開発

 これらは実際にはソートでなかったりわざわざ使う必要が無かったりします。そんなソートの一つにスリープソートがあります。

 スリープソートは渡された値を並列して処理し、値の時間だけスリープしてスリープが終わった順に並び替えをする処理です。言葉では分かりにくいですが、実装を見るとわかりやすいです。JavaScriptでの実装例が次です。

/** ソート対象 */
const preSort = [3,5,6,1,3,4,2,12];
/** ソート結果格納変数 */
let sorted = [];

// 要素時間待った後にソート結果格納用の配列にpush
// 各要素が同時に待ちだすので1は1秒後にpush、3は3秒後にpush、…となります
preSort.forEach(v => setTimeout(()=> sorted.push(v), v * 1000));

// 結果の確認に毎秒ソート結果の中身を観測する処理を使用
const intervalId = setInterval(() => {
    // 毎秒ソート結果を console.log して
    console.log(sorted);
    // すべてのソートが終わったら終了
    if(preSort.length === sorted.length){
        clearInterval(intervalId);
    }
},1000);

 実際に動かしたデモが次です。

 例やデモでは1秒単位でしたが0.1秒単位、0.01秒単位の待ち時間でも同様に作れます。問題点として並び替え対象の要素が多くなるほど待ち時間の単位を短くすると並び替えに失敗しやすいです。これは並び替え対象の最後にスリープ処理をかけにいった時には既に最初のスリープ処理から単位時間以上の時間が経過しやすいためです。

>株式会社シーポイントラボ

株式会社シーポイントラボ

TEL:053-543-9889
営業時間:9:00~18:00(月〜金)
住所:〒432-8003
   静岡県浜松市中央区和地山3-1-7
   浜松イノベーションキューブ 315
※ご来社の際はインターホンで「316」をお呼びください

CTR IMG