計算時間
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 07:06 UTC 版)
バブルソートと比較すると、「交換回数」は等しくなる。しかし、「比較回数」は、バブルソートでは必ずn(n-1) / 2回必要だったが、挿入ソートはこれ以下で済むため、挿入ソートの方が高速である。また、ほとんど整列済みのデータに対しては高速という特徴を持っている。 なお交換回数に関しても、前記実装例のように一連の交換の途中の特定処理を省略することができるので交換一回が高速になる。また、特にデータが連結リストで格納されている場合には、バブルソートと比較して大幅な高速化が図れる。これは配列における「挿入」が一連の交換（の途中の特定処理を省略した処理）によって実現されるのに対し、連結リストでは文字通りの「挿入」が可能であるので、交換回数が大幅に減少するからである。
※この「計算時間」の解説は、「挿入ソート」の解説の一部です。
「計算時間」を含む「挿入ソート」の記事については、「挿入ソート」の概要を参照ください。
計算時間
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/21 01:56 UTC 版)
以下、ソートする配列の要素数を n とする。 要素の比較に関して、各ループで n − 1 回、n − 2 回、……と行われ、処理全体としては ∑ k = 1 n − 1 k = n ( n − 1 ) 2 {\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}} 回行われる。 要素の交換に関して、各ループで最大1回行われ、処理全体では多くとも n − 1 回となる。 バブルソートと比較すると、要素の比較回数は同じだが交換回数が少ないため、選択ソートの方が高速である。
※この「計算時間」の解説は、「選択ソート」の解説の一部です。
「計算時間」を含む「選択ソート」の記事については、「選択ソート」の概要を参照ください。
- 計算時間のページへのリンク
