삽입정렬

삽입 정렬은 숫자를 적절한 위치에 삽입하는 방법이다. 

즉 필요할 때에만 위치를 바꾸면 된다. 

 

8번라인에서 j=i인 이유는 비교할 숫자를 선택하는 것이다

그리고 13번라인에서 j--를 해주는 이미 정렬되어 있는 왼쪽에 배열과 비교하기 때문이다. 

위의 array처럼 되어 있다면 10 >4인 경우 임으로 4와 10의 위치를 바꾼다. 그리고 for문으로 가서 

2는 10앞에 들어갈 지 4 앞에 들어갈지 비교한다. 이렇게 현재 자신의 왼쪽에 이미 정렬되어 있는 배열과 비교한다. 

만약 자신이 왼쪽 배열보다 크다면 반복문에서 벗어나기 때문에 멈춰서 필요할 때만 삽입되는 것을 알 수 있다. 

즉 기본적으로 정렬이 되어있다고 가정하면서 돌린다. 

 

이것도 마찬가지로 시간복잡도는 O(N^2) 이다 

 

※ 만약 거의 정렬되어 있다면..? 

 

2 3 4 5 6 7 8 9 10 1

이렇게 되어 있다면 3,4,5,6,7,8,9,10은 비교를 수행하지 않고 오직 1만 왼쪽에 배열된 위치를 탐색하기 때문에

상당히 빠르게 계산을 수행할 수 있다.