応用情報技術者 試験情報＆徹底解説

選択法という整列のアルゴリズムについて教えてください。 
データが５個の場合、４回、３回、２回、１回と比較が行われ、
データの比較回数が１０回で、ｎ(ｎ＋１)÷２で表現されるのですが、どうしてこの数式になるのかが分かりません。等差数列とか、決まりきった公式のようなものなんでしょうか？

追加で質問です、選択法の比較回数は「ｎ(ｎ＋１)÷２」ですとあるのですが、最終的にはＯ(n２乗)になるというのも、どうしてそうなるのかが、分かりません・・・・

選択ソートでは、最初はデータの位置を確定するために（n-1)回の比較が必要です。
次は、(n-2)回の比較、その次は(n-3)回の比較が必要となります。
これを繰り返すことになるので、(n-1)+(n-2)+(n-3)+...1  つまり、1からn-1までの総和を求めています。
n-1
Σ i = 1/2(n^2-n)＝n(n+1)÷2
I=1

結果、計算量はO(n^2)になります。
簡単に言えば、入力によらずn^2に比例した計算量になります。

>結果、計算量はO(n^2)になります。
>簡単に言えば、入力によらずn^2に比例した計算量になります。

ご回答ありがとうございます。
上記の内容にｎ＝５で考えると、5^2＝25回の判定を行うことになりますか？
選択法だと、4＋3＋2+１=10回ですよね？
ここの部分について教えてもらえませんでしょうか？

質問していて、なんとなく感じたのですが、
Ｏの計算量はソートによってデータが移動する回数のことを指してるということでしょうか？
よくわかってなくて、本当にすみません。
教えてください。

等差数列は、連続する整数の和を求めるための数学的手法です。
n=5であるとき、教科書では10回なのに代入すると15回になるのは、あくまで等差数列的に求められることを示したかったとか、その程度ではないでしょうか。
ちなみに私の持っている教材にはn(n-1)/2とあり、質問者様の予想と同じ式になっています。これらはO的な発想では同じことです。
オーダ(なんとオーダーOrderのこと)では、1回も100回も同じことです。1万回でも1億回でも、それが整数値で無限でなければコンピュータにとって些細な事だからです。極端な例では些細ではなくなりますが、そういう話で実際的に使われることはないので問題ありません。
プログラミング的に言ってしまえば、ループ変数を2個使うから2次式で求められて、それ以外の項はオーダ的に無視されるよね。
つまり、まず1を2-5まで比較する必要があります。これは4回ですが、40回でも4万回でも=n回です。
次に、1は確定なので、2を3-5まで比較する必要があります。これは3回ですが=n回です。
n回比較する作業を、何回すれば良いでしょうか。
n-1回なので、それはn回に等しいです。
n回の比較をn回繰り返すから、n^2。これがオーダになります。
ちなみにn^2+nの場合、n^2以外の項は無視されます。これはn^2にとってnが些細過ぎる数だからです。

n(n＋1)／2とn(n－1)／2が入り乱れているようです。

1からnまでの数の合計は、n(n＋1)／2  nに5を代入すると15
1からn－1までの数の合計は、n(n－1)／2  nに5を代入すると10

n個の要素の選択ソートの比較回数は、(n－1)＋(n－2)＋・・・＋2＋1＝n(n－1)／2

下記の式でn(n+1)÷2と書いていましたが、n(n-1)÷2ですね。
n-1
Σ i = 1/2(n^2-n)＝n(n-1)÷2
I=1

n=5で考えると、5*(5-1)*1/2=10です。

O(n)とは計算量のオーダーのことで、アルゴリズムへの入力サイズをnとして計算量がnに応じてどのように変化するか
ということです。
データが移動する回数というより、処理数(計算のステップ数）ですね。

plさん、助け人さん、yuさんへ

いろんなモヤモヤが解消しました。
また、別のテーマで質問する機会があると思います。また、よろしくお願いします。