0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

非IT系の世界史好きに「スターリンソート」を広めるための記事

0
Posted at

はじめに(エンジニアの皆様へ)

こちらはネットで繋がっている非エンジニアの世界史好きの方々に向けて書いた記事です。
もともと自分のエンジニアとしての知識が浅いのはもちろんのこと、個人的にターゲットとしている方のうち大多数が中高生なこともあり、非エンジニアの方でもできる限り意図が伝わるように、あえて本来の概要とはかなり歪めた表現を入れている場合があります。
あらかじめご了承ください。

非エンジニアの皆さんへ

上の「エンジニアの皆様へ」を読めば概ね分かる通り、こちらの記事は「正確な解説」を目的とはしていません。
とても精度の悪いAIが生成した記事としてお楽しみいただければと思います。

そもそもソートとは

ソートとは、適当に並べられた複数個の数字のデータを小さい順に並べる処理のことです。
学校で例えるなら、クラスや学年の男女で「背の順」や「出席番号順」で並ぶ、あの一連の動作です。

例えば、あなたがいるクラスの全員で背の順に並ぶとき、具体的にどのようにして背の順の列を決めていきますか?
おそらく多くの人が「一番小さい人・大きい人から順番に並んでいく」か、「一定の身長でグループを作ってその中で背の順に並ぶ」と考えると思います。
これも立派なソートであり、プログラムも確立されているのですが、エンジニアの世界では大抵数多のデータを取り扱うため、「更にもっと速く並ばせる」が重要視されているのです。

最高に速いソート「スターリンソート」とは

さて、世の中には「バブルソート」や「クイックソート」など、賢いエンジニアの方々が考えた正しい並べ替えの方法がいくつもあります。

しかし、2019年に誕生した「スターリンソート(Stalin Sort)」は一味違います。

もし、クラスで背の順に並ぶときにスターリンソートを適用するとどうなるでしょうか?

image.png

  1. 一番前にいる生徒を基準(135cm)とします。

image.png

  1. 次の生徒(137cm)を見ます。135cmより大きいのでOK、そのまま並びます。

image.png

  1. 次の生徒(128cm)を見ます。前の人より小さいですね?
    普通なら入れ替えたり間に入ったりします。

ですが、スターリンソートでは違います。

「粛清(シベリア送り)」 です。

image.png

128cmの生徒は配列(列)から即座に消去されます。
だって、言われたとおりに背の順に並んでいなかったもんね?

  1. 次の生徒(143cm)を見ます。137cmより大きいので残れます。

image.png

  1. 次の生徒(139cm)を見ます。前の人より小さいので、粛清!!

image.png

これを最後まで繰り返すと……?

なんと、「生き残った人たちだけで見れば、最初から完璧に背の順で並んでいる」という状態が完成します!!

image.png

普通のソートでは、「データが多ければ多いほど絶対に並び替える時間がかかる」という致命的な弱点があります。
しかし、このソートは「どんなにデータが多くても絶対に1周すれば完了する」という素晴らしく高速なソートなのです! データは消えるけど

おまけ

直近で ポルポトソート なるもっとひどいジョークアルゴリズムを作った方もいます。
(実は自分はこの記事からスターリンソートを知りました)
このスターリンソートよりももっとブラックジョークを再現(?)したソートになっていますので、よければ閲覧してみてください。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?