選択ソートとはまだ整列が終わってないデータから最小値*4のデータを取り出し、最小値と確定データの右隣*5と入れ替えることで整列させていく方法を選択ソートと呼びます。下の4つのデータを昇順に選択ソートしてみましょう。未確定データ(全部)から最小値を探し、左端のデータと入れ替えます。すると、左端のデータ「1」の場所が確定します。確定していない残りの3つのデータから最小値を探し、確定データの右隣(2番目)のデータと入れ替えます。すると、左から2番目のデータ「2」の場所が確定します。残り2つのデータから最小値を探し、確定データの右隣(3番目)のデータと入れ替えます。昇順に選択ソートするプログラムは、下のように書くことができます。}}参考までに降順ソートの場合は、下のようなプログラムとなります。選択ソートの比較・交換回数n個のデータを選択ソートするときにif文で比較する回数とデータの交換回数を考えましょう。選択ソートでは、最小値(or最大値)を探すために自分以外の未確定の要素を比較して最小値を探します。そのため、1番目の要素を確定させるときにn-1回、2番目の要素を確定させるときにn-2回、......、n-1番目の要素を確定させるときに1回比較を行います*6。\]となりますまた、交換は最小値を見つけたときにのみ行うので、n-1回の交換で済みます。交換回数がバブルソートよりも基本的に少ないため選択ソートはバブルソートより早いです。挿入ソートとはデータを整列済と未整列の2つに分類し、未整列データの先頭の要素を正しい場所に挿入していくことで整列済にしていく方法を挿入ソートと呼びます。下の4つのデータを昇順に選択ソートしてみましょう。1つ目を整列済とします。次に未整列のデータの先頭(2番目のデータ)を適切な位置に移動させます。おや、偶然にも移動させなくても適切な位置でしたね。いうことで2番目までのデータが整列できましたね。整列済にしていきましょう。つぎは3番目のデータを適切な位置に移動させます。最後に4番目のデータを適切な位置に移動させればソート完了です。昇順に挿入ソートするプログラムは、下のように書くことができます。変えると降順ソートを行うことができます。挿入ソートの比較・交換回数n個のデータを選択ソートするときにif文で比較する回数とデータの最大交換回数を考えましょう。1番目のデータは比較、交換をしなくても整列済にできますね。2番目以降のデータは、値によっては1回の比較(交換なし)で済みますが、最もデータを比較・交換する場合、左端になるまでデータを交換していく必要があります。