広告 プログラム

選択ソート(基本選択法)とは | 分かりやすく図解で解説

はじめに

基本情報技術者試験や応用情報技術者試験でよく出題される整列アルゴリズムの問題。

基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があり、より高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」があります。

スポンサーリンク

本記事では、最小値(もしくは最大値)と先頭の値を交換していく「選択ソート(基本選択法)」について図解で分かりやすく解説しています。

選択ソート(基本選択法)とは

選択ソートとは対象となるデータの中から最小値(もしくは最大値)を探し先頭の値と交換、この作業を繰り返すことで全体を整列させていく手法です。

簡単な流れ

  • 未整列データの中から最小値を探す
  • 最小値と先頭の値を入れ替え(※最小値が先頭の場合はそのまま)最小値を整列済みデータとする
  • 処理1~2を繰り返し、すべてのデータが整列済みになったら終了

暗記ポイント

選択ソートは、未整列データ内の最小値と先頭の値を交換。この作業を繰り返し整列していく整列アルゴリズム。

それでは、図を利用して選択ソートの流れを説明していきます。

1回目 未整列データ内の最小値と先頭の値を交換する

未整列データの中から最小値を探し、先頭の値と位置を入れ替えます。(最小値「1」と先頭のデータ「4」を入れ替え、最小値「1」を整列済みデータとする)

選択ソート手順1

2回目 再び未整列データ内の最小値と先頭の値を交換する

整列済みデータ以外の未整列データの中から最小値を探し、未整列データの先頭の値と位置を入れ替えます。(最小値「2」と先頭のデータ「4」を入れ替え、最小値「2」を整列済みデータとする)

選択ソート手順2

3回目 再び未整列データ内の最小値を探し、整列を完了させる

整列済みデータ以外の未整列データの中から最小値を探します。最小値「3」は未整列データの先頭なので、位置の入れ替えはおこなわずそのままとします。(最小値「3」を整列済みデータとする)

最後に残った「4」を整列済みにして選択ソートは完了です。

選択ソート手順3

 

helpful