삽입 정렬(Insertion Sort)

삽입정렬

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입한다.

1단계

69와 10을 비교한 후 정렬한다.

2단계

30의 자리를 찾기 위해 먼저 69와 크기를 비교한다. 30 < 69 이므로 10과 30을 비교한 후 정렬한다.

3단계

2의 자리를 찾기 위해 먼저 69와 크기를 비교한다. 2 < 69 이므로 그 다음으로 30, 10과 계속해서 비교해나간다.

비교한 후 정렬한다.

4단계

마찬가지로 69부터 시작해서 차례로 16과 비교한 후 정렬한다.

시간복잡도

Worst, Average

Best

실행코드 / 결과