プログラミング素人が「選択ソート」を勉強したので自然言語で解説する

　ひととおりRubyの実装の初歩は学んだ僕ですが、コンピュータサイエンスの分野については完全にど素人です。
そもそも僕は高卒で、普通科高校の劣等生だったので専門的な知識は皆無です。
　そんな僕が最近勉強しているのは、アルゴリズムについて。
その中でちょっと苦戦した「選択ソート」について簡単に自然言語で解説します。

選択ソートでやりたいこと

　「ソート」という言葉自体は、非エンジニアでも使いますね。
具体的には、Excelで「昇順ソート」とか「降順ソート」とかです。
つまり「並び替え」です。
これまで僕の認識では「コンピュータなんだからいい感じに並び替えができるのだ」ぐらいの感覚でExcelでソートかけてました。

　今回扱うのは、「配列のソート」。
具体的には、[ 5, 7, 3, 10 ] という配列（数字の並び）を、小さい順に並べて [ 3, 5, 7, 10 ] にするプログラムを作りたいとします。

選択ソートはバトルである

　いくつかあるソートの方法のうち「選択ソート」とは、いわば「総当たり戦」で「一番大きい／小さいヤツ」を決める大会みたいなものです。
上記の[ 5, 7, 3, 10 ] という配列を例に取ると、行われているのは以下のようなことです。

• ルール「小さい方が勝ち」の大会。

• 必ず「暫定チャンピオン vs 挑戦者」という形で行われる。

• 大会開始時に「一番左にいるヤツ」が暫定チャンピオン役となる。

• 挑戦者が勝った（小さい）場合、その挑戦者は暫定チャンピオンになる。
  最後まで生き残ったらヤツが優勝。

• 試合運びは以下のような流れになる。

  • 第一試合：
    暫定チャンピオン「5」 vs 挑戦者「7」の対戦
    → 5の方が小さいので勝ち。

  • 第二試合：
    暫定チャンピオン「5」 vs 挑戦者「3」の対戦
    → 3の方が小さいので勝ち。
    　勝者は暫定チャンピオンとなり、その後の挑戦者を待ち受ける。

  • 第三試合：
    暫定チャンピオン「3」と挑戦者「10」の対戦。
    →3の勝ち。

  • 結果：3が優勝。

• 優勝者は、その大会が開始された時のチャンピオンである「5」の場所と交換される。
  よって、第一回大会が始まる前は[ 5, 7, 3, 10 ] という配列だったが、
  大会後は[ 3, 7, 5, 10 ] という結果が出て終了。

• この大会を、（配列に並んでいる値の数-1）回繰り返す。過酷である。
  つまり、今回の配列[ 5, 7, 3, 10 ]の参加者は4名なので、3回同じようなバトルが行われる。なぜマイナス1なのかは後述。

• なお第一回大会の優勝者である3は次回参加できない。絶対勝っちゃうから。今後の優勝者も同じ。一度優勝したら今後出禁。

これを繰り返すとどうなるか

第二回大会

配列[ 3, 7, 5, 10 ]のうち、3は初回チャンピオンのため不参加。残った7, 5, 10のうち、一番左にいる「7」が暫定チャンピオン役。初回敗退は見えているが我慢してください。

第一試合：　7 vs 5 → 5の勝ち
第二試合：　5 vs 10 → 5の勝ち
第二回大会の優勝者は、5

優勝者は「その大会で最初に暫定チャンピオンをやったヤツと入れ替わる」というルールだったので、5は7の席を貰うことになる。
出てくる配列は[3, 5, 7, 10]　となった。

第三回大会

やる意味ある？？？
というコメントは置いといてください。説明だけさせてください。

現状の配列は[3, 5, 7, 10]。
3と5は優勝経験があるので参加不可。参加者は7と10。
一番左にいる7が暫定チャンピオン。

第一試合：　7 vs 10 →　7の勝ち。優勝。
この場合、最初の暫定チャンピオンがそのまま優勝したので、この大会による場所の変動はありません。

第四回大会

さすがに参加者が[10]の一人では、やる意味がないので開催されません。
だから、（配列に並んでいる値の数-1）回の開催であるわけです。

たかがソートと侮るなかれ、裏では壮絶な戦いが(?)

そんなわけで、[ 5, 7, 3, 10 ] という配列を、小さい順に並べて [ 3, 5, 7, 10 ] にするプログラムを作りたいと思ったら、こういうドラマを想像することになります（個人差があります）。

個人的に、仮にary[i]をminとおいて、j = i+1 を定義してary[j]と比較して、もし小さければminに再代入して・・・というプロセスを理解するのにちょっと時間がかかったので、バトル漫画にして理解することにしました。果たしてわかりやすいのだろうか

ちなみにできたコードはこんな感じ。
ary[i]は「暫定チャンピオン」役のヤツで、暫定チャンピオンに与えられる称号が"min"みたいなイメージ。
上の例えで言う「挑戦者」はary[j] が該当しています。 

def select_sort(ary)
	(0...ary.length).each do |i|
		min = ary[i]
		min_position = i
		((i + 1)...ary.length).each do |j|
			if ary[j] < min
				min = ary[j]
				min_position = j
			end
		end
		ary[i], ary[min_position] = ary[min_position], ary[i]
	end
	return ary
end

ary = [245, 45, 32, 367, 122, 67, 14, 89]
p ary
p select_sort(ary)

擬人化してイメージするとわかりやすい（個人差があります）ので、今後もなんとかストーリー仕立てにしていろいろ理解していきたいと思っています。

ところで、トップの画像はGPT4に「手足の生えた3と5がボクシングしている画像作って」というプロンプトで作ってもらいました。きｍシュールですね。

おしまい。