ソートアルゴリズム

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

---

```cs:SelectSort.cs

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;
                }
            }
        }
```
```cs:実行結果
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

↓参考にするとより分かりやすいURL
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&cad=rja&uact=8&ved=2ahUKEwi99or54uf6AhXDm1YBHYIGBnUQFnoECAsQAQ&url=https%3A%2F%2Fwww.codereading.com%2Falgo_and_ds%2Falgo%2Fselection_sort.html&usg=AOvVaw2SLiOmGK95IYFUJ08BHLAl