[解答例1] [解答例2]

[解答例]

[解答例]

[解答例]
　挿入ソートにおいては挿入するデータよりも前に位置するデータは仮ではあるがソート済みであり、比較した結果で挿入の必要がなければ、ソート済みデータに対しては以降の比較と移動処理が不要となります。そのため、ある程度整列したデータ列に対しては比較・移動処理回数を少なくすることができ、結果として高速に動作します。逆に、降順に整列したデータ列を昇順にソートしようとした場合は、未ソート部分には必ずソート済みデータの中の一番小さな値よりも小さなデータがあるため、すべてのソート済みデータとの比較、i番目のデータではi回の比較・移動処理が必要となるため、時間計算量は1+2+...+(N-1) = N(N-1)/2回となります。

[解答例]

 二分探索木の探索における時間計算量オーダーは木の高さに相当するのでO(logn)となりますが、関数print_decsend()はn個のノードを巡回してそのデータ値を表示している、すなわちn回の処理を行っているので、時間計算量オーダーはO(n)となります。再帰呼び出しを利用してはいますが、n回の繰り返し処理と時間計算量は変わりません。
[解答例]
 （注）問題のソースコードでは省略されていた、ノード追加のために確保した記憶領域の解放処理を、以下の解答例では追加しています。