スターリンソート
アルゴリズム 1
長さが$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に送る、すなわち粛清するため、元の配列の要素がそのまま保持されないからだ。
しかし、コーディングをしていると、意外とこのようなアルゴリズムが必要だったり、このアルゴリズムで十分だったりすることがある。幸いにも、ネーミングセンスが素晴らしく、実装も非常にシンプルなので、わざわざ覚えようと努力する必要はない。