【選択ソート】入力データを昇順・降順・ランダムにした時の比較と交換の時間計算量とは

　選択ソートの平均計算時間や最悪計算時間は調べてもすぐに出てきますが、入力データが昇順・降順の時は？　比較の時間計算量や交換の時間計算量は？　いろいろと調べましたが、簡潔に説明してくれるサイトを見つけれなかったので記事にしてまとめてみました。誰かの役に立てば幸いです。

選択ソートとは？

選択ソートは、ソートのアルゴリズムの一つです。アルゴリズムは、配列された要素から、最大値やまたは最
小値を探索し配列最後の要素と入れ替えを行います。非常に直感的で単純なアルゴリズムですね。

選択ソートのメリット

　空間計算量が限られているせいで他の高速な手法が使えない場合や、ソートする配列が充分小さく、選択ソートが高速に動作することが保証されている場合に利用できる

選択ソートのデメリット

　内部ソートで安定なソートではない。

　最悪計算時間が O(n²)と遅い。

比較の時間計算量(昇順・降順・ランダムの時)

　n個の入力データがどの並びをしていても、アルゴリズムは全てのデータを比較するので比較の時間計算量はO(n²)となります。

交換の時間計算量(昇順・降順・ランダムの時)

　選択ソートにおいて入力データの個数がnとすると、交換の回数は常に(n-1)回になります。つまり、交換の時間計算量はO(n)になります。