1.今日のプログラミング
前回は、ソートアルゴリズムの中で一番簡単なバブルソートをやりました。
なので今回は、前回よりも少し難しいセレクトソート（選択ソート）についてやってこうと思います。
※以降 選択ソートのことをセレクトソートと呼ぶ。
2.セレクトソート
セレクトソートは、未整列の要素の中から最小値を探し出して、ソート済みの要素と後ろの要素を交換して、
並び替えていくソートアルゴリズムです。
バブルソートとの違いが分かる優秀な人もいるかもしれないですが、一応説明しておきます。（自分の備忘録も兼ねて）
例えばバブルソートは、array[ j ] > array[ j + 1 ]だった時、ソートが完了するまで、残りの要素に対してスワイプし続けます。
つまり、下記の要素があったとき最初に70（array[ j ]）と、60(array[ j + 1 ])を比べます。
(全体の要素数の配列はarray[ i ]とする。)
------array[ i（0） ]---------
70、60、40
array[ j ] > array[ j + 1 ]より、70 > 60なので入れ替える。
60、70、40
次に、
60、70、40
70 > 40なので入れ替える。
60、40、70
------array[ i（1） ]---------
60、40、70
60 > 40なので入れ替える
40、60、70
次に、
40、60、70
60 < 70なので入れ替えない。
40、60、70
これでソート完了です。
これがバブルソートでした。今は要素数が少ないので楽ですが、1万ものデータをこれで処理をしようとすると大変ですよね。。。
しかし、セレクトソートだともっと早くソートを完了させることができます。
未整列ソート部分の中で最も小さい要素を特定して、未整列ソート部の最も小さいインデックスと交換するのです。
つまり下記の要素があったとき、最初に70（ minIndex = 0 ）、60( j = 1 )をくらべていきます。
(全体の要素数の配列はarray[ i ]とする。)
------array[ i（0）]---------
70、60、40
minIndex = 0 、 j = 1 より、70 > 60。ｊ（60）の数値をminIndex（70）に渡します。minIndex = 1（60）
次に、
70、60、40
minIndex = 1 、 j = 2 より、60 > 40。ｊ（40）の数値をminIndex（60）に渡します。minIndex = 2（40）
ｊが最後まで走査し終わったら並び替えます。
今一番の minIndex は40ですね。
つまり40が要素の最小ってことがわかりました。
------array[ i（1）]---------
40はソート完了なので動かしません。
したがって、70と60だけを見ます。
40、70，60
minIndex = 1 、 j = 2 より、70 > 60。ｊ（60）の数値をminIndex（70）に渡します。minIndex = 2（60）
j が最後まで走査し終わったので並び替えると、
40、60、70となります。
長くなりましたが、実装していきましょう。
言語・・・C#
IDE・・・Visual Studio2022
static void Main(string[] args)
{
int[] selectsort = {7,6,9,3,5,4,2,8,1 };
SortAlgorithm(selectsort);
for(var i = 0; i < array.Length; i++)
{
Console.WriteLine(array[i]);
}
while (true) ;
}
public static void SortAlgorithm(int[] array)
{
int minIndex;//こいつが要素の最小、最も小さい要素
for (var i = 0; i < array.Length - 1; i++)
{
minIndex = i; //array[i]は、array[minIndex]と交換させる
var minValue = array[minIndex];
for (var j = i; j < array.Length - 1; j++)
{
if (minValue > array[j + 1])//ここで交換処理
{
minValue = array[j + 1];
minIndex = j + 1;
}
}
//値渡し
if (i != minIndex)
{
var tmp = array[i];
array[i] = array[minIndex];
array[minIndex] = tmp;
}
}
}
1
2
3
4
5
6
7
8
9
このコードを実行すると小さい順に並びました。もし昇順にしたいのなら二重forのifの中の不等号を逆にしてみてください。
一見バブルソートとおんなじそうだし、バブルソートでいいんじゃね？？
って思う方もいると思いますが、処理のスピードが若干違うんです。
結論から言うと、セレクトソートのほうが若干早いです。
↓ 処理のスピードを見たい方はこちらのURLより
https://www.youtube.com/watch?v=kPRA0W1kECg&t=9s
セレクトソートは0：00～、バブルソートは4：01～です。
ソートアルゴリズムは奥が深いですねぇ....
まとめ
要素の比較回数は同じだけど交換回数が少ないので、バブルソートを理解できたのならばぜひ、
セレクトソートを使ってみましょう。
それと、理解するとアルゴリズム系はたのしいね。
・バブルソートのブログはこちらからhttps://qiita.com/Ryosuke004682/items/ef871e2e521471f65ea5