スターリンソートをJSで実装してみた

スターリンソートなる、「整列されていない要素を"粛清"することでO(N)でソートを実現する」というネタが盛り上がっているようなので、便乗して書きました。

実装

まず、空のソート結果を格納する配列を用意します。そして、リストを先頭から見ていきます。ソート結果配列の末尾がリストの要素より小さければ、ソート結果にリストの要素を追加します。

const stalinSort = arr =>
  arr.slice(0).reduce((acc, a) => (acc.length === 0 || acc[acc.length - 1] <= a ? [...acc, a] : acc), []);

スターリンソートの開始位置を変えてみる

このスターリンソートは、[100, 1, 2, 3, 4, 5]のように最大値が先頭に来てしまうと残りの要素がすべて粛清されてしまうという問題点があります(他にもあるやろ！)。そこで、開始位置を変えることで、得られる配列の長さを最大化してみようと思います。

これは「最長部分増加列」を求める問題と同一になります。ちなみに、最長部分増加列を求めるにはO(NlogN)かかるのでスターリンソートのメリットがなくなります。本末転倒ですね。

const bound = comp => (arr, key) => {
    let s = 0, t = arr.length;
    while (t - s > 1) {
        const mid = s + Math.floor((t - s) / 2);
        if (comp(arr[mid], key))
            s = mid;
        else
            t = mid;
    }
    return comp(arr[s], key) ? t : s;
};
const lower_bound = bound((a, b) => a < b);
const upper_bound = bound((a, b) => a <= b);

const longestStalinSort = arr => {
    const dp = [];
    for (const item of arr)
        dp[lower_bound(dp, item)] = item;
    return dp;
};
console.log(longestStalinSort([100,1,2,100,3,4,5]));
console.log(longestStalinSort([1,3,5,2,4,6]));