📂アルゴリズム

スターリンソート

アルゴリズム ¹

長さが$n$の配列が与えられたとしよう。配列を前から後ろまで読んで、後ろの要素が前の要素より大きい場合に削除を繰り返すと、‘順番に’並べ替えられた配列を得ることができる。その時間複雑性は$O(n)$で、疑似コードは次の通りである。

FUNCTION stalinSort(A : list OF sortable items)
    n := length(A)
    bigger := 0
    B SET empty list

    FOR i := 0 TO n NOT inclusive DO
        IF A[i] >= bigger THEN
          bigger := A[i]
          B.push(A[i])
        END IF
    END FOR

    RETURN B
END FUNCTION

説明

スターリンソートは、ソビエトの独裁者ヨシフ・スターリン^{Ио́сиф Ста́лин}の名前から取ったアルゴリズムで、実際のところ、ジョークに近い。なぜなら、スターリンが行ったように、気に入らない要素をグラグ^gulagに送る、すなわち粛清するため、元の配列の要素がそのまま保持されないからだ。

しかし、コーディングをしていると、意外とこのようなアルゴリズムが必要だったり、このアルゴリズムで十分だったりすることがある。幸いにも、ネーミングセンスが素晴らしく、実装も非常にシンプルなので、わざわざ覚えようと努力する必要はない。