3)位置合わせを挿入

ソートの挿入は、各数値を適切な位置に挿入する方法です.
問題は過去の時間と同じだ.
<昇順で次の数字を並べたプログラムを作成します.>
(1, 10, 8, 3, 5, 4, 7, 9, 2, 6)

int main() {
	int temp, j;
	int array[10] = { 1, 10, 8, 3, 5, 4, 7, 9, 2, 6 };
	for (int i = 0; i < 9; i++)
	{
		j = i;
		while (j >= 0 && array[j] > array[j + 1]) {
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}
	for (int i = 0; i < 10; i++)
	{
		cout << array[i];
	}
}

1-10-,8,3,5,4,7,9,2,6
jが8の場合、スペースには前の数1より大きく、10より小さく、その間に挿入される.
このように繰り返していく方法です.
他のソートが無条件に位置を変更している場合、挿入ソートは必要に応じてのみ位置を変更します.
したがって,実際の演算は前の学習よりもソートが最も少ない.
挿入ソートの時間的複雑さはO(N^2)であった.
しかし,ある程度並べ替えられていると仮定すると,この方法を用いる速度は非常に速い.