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

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

実装

リストを先頭から見ながら暫定の最大値を持っておきます。その最大値よりも小さい値があったら、それは整列されていない要素なので結果に加えないこととします。

const stalinSort = arr => {
    if (arr.length == 0)
        return [];
    let max = arr[0]; // 暫定の最大値
    const res = [arr[0]];
    for (const item of arr) {
        if (max < item) {
            max = item;
            res.push(item);
        }
    }
    return res;
};

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

このスターリンソートは、[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]));