概要

基本情報技術試験の問題対策として「選択ソート」を説明をしました。
(初投稿で文章が読みにくい部分が有るかと思います。ご了承下さい。)

対象とする読者

　・アルゴリズムの基礎から学びたい人。
　・これから基本情報技術試験を受けようと考えている人。

選択ソートとは？

例

想像してみてください、あなたはりんご農園で働いていて、りんごを小さい番号順に棚に並べる必要があります。りんごは最初、バラバラな順番で置かれています。ここでのりんごの大きさを表す配列は [4, 2, 5, 1, 3]です。 選択ソートを使用する事により、あなたの作業が自動化されます。

要するに

「選択ソートは配列の中身を昇順/降順で並び替えるアルゴリズムの1つです。選択ソートは配列の中で最小の要素を見つけ、それを配列の最初の要素と交換することから始まります。」

選択ソートの穴埋め問題

この問題は、基本情報技術試験を想定した形式で出題される選択ソートに関する問題です。問題文中に登場する「りんご配列」という表現は、配列の要素を視覚化するために用いられています。また、この問題では、一般的なプログラミング言語の変数名として日本語が使用されています。

問題の前提:
配列のサイズ (N): 5
りんご配列: [4, 2, 5, 1, 3]

①　for(回：1, 回　≦　N　-　1, ＋1)
②　　　小　←　回
③　　　　　？
④　　　　　　if(りんご［小］　　＞　　　りんご［数］)
⑤　　　　　　　　　小　←　数
⑥　　　　　　endif
⑦　　　endfor
⑧　　　if(回　　≠　　小)
⑨　　　　　　ワーク　←　りんご［回］
⑩　　　　　？
⑪　　　　　　りんご［小］　←　ワーク
⑫　　　endif
⑬　endfor

説明

・「回」とは、あなたが行う並び替えの回数を表します。最初の並び替えを「1回」と数え、次に「2回」、そして「3 回」と続けていきます。この数え方はりんごの数分続きます。例えば、最初の「1回」では、りんご配列の最初のりんごから始めて、最小のりんごを見つけてその位置に移動させます。次の「2回」では、2番目のりんごから始めて、また最小のりんごを見つけてその位置に移動させます。これをりんごの数分繰り返します。

・「小」とは、現在のりんごの中で最も小さいものを見つけるために使用する位置（インデックス）です。例えば、最初の反復では、あなたは最初のりんご（サイズ 4）を「小」として指定します。しかし、隣のりんご（サイズ 2）がより小さいことに気づくと、「小」はそのりんご（サイズ 2）の位置に更新されます。

・「数」とは、現在注目しているりんごの次から最後のりんごまでをチェックするために使用する位置（インデックス）です。つまり、最初のりんご（サイズ 4）から始めて、次のりんご（サイズ 2）、その次のりんご（サイズ 5）と順に比較していきます。「数」はこの比較のために次々と更新されます。

・「ワーク」は、一時的にりんごのサイズ（値）を保存するための変数です。例えば、あなたがサイズ 4 のりんご（最初の位置）とサイズ 1 のりんご（4番目の位置）を交換するとき、「ワーク」はサイズ 4 のりんごの値を一時的に保持します。これにより、サイズ 1 のりんごを最初の位置に移動させた後、元のサイズ 4 のりんごを4番目の位置に移動させることができます。これにより、値の上書きを防ぎながら、りんごを適切な位置に移動させることができます。

空欄の解答

③ for(数：回 ＋ 1, 数 ≦ N, ＋ 1):
これはあなたが現在のりんご（位置 回）から棚の最後まで見ていく操作です。
あなたは各りんごをチェックし、それが現在のりんごより小さければ、その位置を覚えておきます。例えば、最初のりんご（4）の後に 2、5、1、3 がありますが、その中で最も小さいのは 1 です。

⑩ りんご[回] ← りんご[小]:
これは見つけた最小のりんご（例では 1）を現在の位置に移動する操作です。　つまり、4 があった場所に 1 を置きます。これにより、最小のりんごが正しい位置に移動されます。選択ソートを使うことで、あなたはりんごを一つずつ最小のものから順に選び、適切な位置に移動させることができます。

プロセスの終わりには、りんごは小さい番号順にきれいに並べられています。この例では、最終的な配列は [1, 2, 3, 4, 5] となり、全てのりんごが番号順に整列されます。