きっかけ

スターリンソート(Stalin Sort) というジョークアルゴリズムがあります。配列を先頭から走査し、直前の要素より小さい値が出てきたらその場で削除する、というO(n)の「ソート(?)」です。

これを見て、「もっと酷くできるのでは」と思い立ち、ポルポトソート(Polpot Sort) を作りました。

アルゴリズム

配列からランダムに1要素を選び、「基準値」として固定する(以後、実行中は一切更新しない)。
配列を走査し、基準値より大きい要素はその場で除外する。基準値以下の要素は生存する。
フェーズ1を生き延びた要素それぞれに対し、値とは無関係に一定確率(デフォルト20%)でさらに除外する(内部粛清フェーズ)。

出力は入力配列の部分列で、要素数は入力以下になります。ソートアルゴリズムとして機能を全く果たしていませんが、それがこのプロジェクトの狙いです。

計算量

ケース	計算量
最悪	O(n)
平均	O(n)
最良	O(n)

配列を1回ずつ走査するだけなので、常にO(n)です。ただし「最悪」なのは計算量ではなく出力の正しさの方で、ソート済みである保証も、出力の要素数の保証もありません。

実装(Python)

import random


class PolpotSort:
    def __init__(self, purge_probability=0.2, seed=None):
        self.purge_probability = purge_probability
        self.seed = seed

    def sort(self, arr):
        if self.seed is not None:
            random.seed(self.seed)

        if not arr:
            return []

        n = len(arr)
        baseline_idx = random.randrange(n)
        baseline_val = arr[baseline_idx]

        survivors = [x for x in arr if x <= baseline_val]
        purged = [x for x in survivors if random.random() > self.purge_probability]

        return purged if purged else [baseline_val]

sorter = PolpotSort(purge_probability=0.2, seed=42)
print(sorter.sort([5, 3, 8, 1, 9, 2, 7, 4, 6, 10]))

実装(JavaScript)

class PolpotSort {
  constructor({ purgeProbability = 0.2, seed = null } = {}) {
    this.purgeProbability = purgeProbability;
    this.seed = seed;
    this._rng = seed !== null ? mulberry32(seed) : Math.random;
  }

  sort(arr) {
    if (!arr || arr.length === 0) return [];

    const n = arr.length;
    const baselineIdx = Math.floor(this._rng() * n);
    const baselineVal = arr[baselineIdx];

    const survivors = arr.filter((x) => x <= baselineVal);
    const purged = survivors.filter(() => this._rng() > this.purgeProbability);

    return purged.length > 0 ? purged : [baselineVal];
  }
}

可視化

粛清の過程を棒グラフの動画として書き出すスクリプトも同梱しています。

グレー: 未処理
緑: 生存
黄: 基準値
粛清された要素はその場で消える

Python版(Pillow + imageio)とJavaScript版(npm依存なし、ffmpegに直接パイプ)の両方を用意しています。

関連するジョークアルゴリズム

スターリンソート — 昇順を乱す要素を片っ端から削除する
ボゴソート — ソートされるまでひたすらシャッフルを繰り返す
サノスソート — 1回の走査ごとに要素のちょうど半分をランダムに削除する

リポジトリ

Python/JavaScript両対応、MITライセンスです。他の言語での実装のPRも歓迎します。