Insert Sort

 삽입정렬이란?

앞에서부터 시작하여 범위를 늘려가며 자기 자신의 자리를 찾는 정렬 방식이다.

 

ex) 3 2 1 -> 2 3 1 -> 1 2 3

 

1. 시간복잡도

 최악의 경우(정렬되어있지않은 경우) 1번, 2번, 3번, ..... , N-1번까지 정렬이 일어날 수 있다. 

즉, N*(N-1)/2 이므로 O(N^2)

 

2. stable

 범위를 늘려가면서 순서대로 자기 위치를 찾기 때문에 같은 숫자의 순서를 유지한다.

 

3. 코드

 

 

 ps. 삽입 정렬은 왼쪽 부분이 정렬되어있다고 가정하기 때문에 자기가 왼쪽에 있는것보다 크다면 거기서 멈추면 된다. 따라서 멈출 포인트를 알고 있기 때문에 선택, 버블 정렬보다 효율적이다.