2013年度 秋期 情報セキュリティスペシャリスト 午前I 問3

選択肢アの3回、イの6回、エの15回は、いずれもこのアルゴリズムの実行結果としてあり得る回数ですが、与えられた初期値とアルゴリズム（挿入ソートと仮定）に基づいた厳密なシミュレーションが必要です。

アの3回は、要素がほとんど整列されている場合や、挿入される要素が常に整列済みの部分の末尾に挿入される場合に考えられます。しかし、初期配列には大小のばらつきが大きいため、3回では少ないと考えられます。

イの6回も、初期配列の特性によってはあり得ますが、挿入ソートの交換回数は一般的にn(n-1)/2に近づく傾向があります。6回では、比較的回数が少なく、配列の非整列度を考慮すると、まだ交換の余地が大きい可能性があります。

エの15回は、最大交換回数であり、要素が完全に逆順に並んでいる場合に到達しうる回数です。今回の初期配列は逆順ではありませんが、挿入ソートの性質上、交換回数はしばしばn(n-1)/2に近くなります。

しかし、この問題では、与えられた初期配列でアルゴリズムを具体的に実行し、交換回数を数える必要があります。初期配列 [21, 5, 53, 71, 3, 17] に対して挿入ソートを適用すると、数回の外側ループと内側ループの実行を経て、最終的にa[j-1]とa[j]の値の入替えは8回行われます。これは、各要素が整列済みの部分に挿入される際に、その位置に応じて複数回の交換が発生することを示しています。例えば、最初の5が21の前に挿入される際に1回、3が先頭に挿入される際には複数回の交換が発生するなど、要素の移動距離に比例して交換回数が増加します。