[Algorithm] 정렬 알고리즘 (삽입 정렬)

 

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

삽입 정렬 과정

Step 0 : 정렬할 데이터를 준비한다.

Step 1 : 첫 번째 데이터 '5'가 정렬되어 있다고 판단, 두 번째 데이터인 '1'이  '5'의 왼쪽이나 오른쪽으로 들어갈지 결정한다.

결과적으로 '5'의 왼쪽으로 '1'이 들어가게 된다.

Step 2 :  이어서 '4' 가 어디로 들어갈지 판단한다.

'4'는 '5'의 왼쪽인 두번째 위치로 들어갈 것이다.

Step 3 : 이어서 '3'이 어디로 들어갈지 판단한다.

'3'은 '5'의 왼쪽으로 이동, '4'의 왼쪽으로 이동을 통해서 다음과 같이 위치할 것이다.

Step 4 : 마지막으로 '2'가 어디로 들어갈지 판단한다.

'2'는 3번의 이동을 통해서 다음과 같이 '3'의 왼쪽에 위치하게 될 것이다.

아래의 케이스는 자신보다 작은 데이터를 만날 때 그 위치에서 멈추는 경우도 포함된 예시이다.

python으로 구현한 삽입 정렬

삽입 정렬의 시간 복잡도

선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다. 따라서 

• 삽입 정렬은 리스트의 데이터가 정렬된 상태가 좋을수록 더 빠르게 동작한다. 
• 최선의 경우 O(N)의 시간 복잡도를 가질 수도 있다.
• 이미 정렬되어 있는 경우에 삽입 정렬을 수행하게되면 N-1번만 수행하게 되므로 O(N)의 시간 복잡도를 가지게 되는 것이다.