[파이썬(python) 알고리즘] 정렬 - 삽입정렬 (Insert Sort)

삽입정렬

삽입정렬이란 정렬되어 있는 앞 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복하며 정렬하는 알고리즘이다.

 

삽입정렬 예시

 

1) 삽입정렬 과정

 초기 상태는 첫번째 원소를 정렬이 되어있다고 가정하고 시작함. 이후, 정렬된 부분 바로 뒷원소(a)와 정렬된 부분의 모든 원소를 비교하며 a의 제자리를 찾아 넣어줌. 예를 들어, 아래 그림에서의 2를 보면 1,3,5,8의 정렬된 부분 리스트와 비교를 시작하여 1보다 크고 3보다 작으므로 1과 3 사이에 삽입해주고, 탐색을 마친다.

삽입정렬 과정 도식화

2) 삽입정렬 알고리즘

이중 반복문 구조를 가진 알고리즘

1. 배열의 길이만큼 반복

2. key = 삽입할 원소

3. j는 배열의 오른쪽에서 왼쪽으로 이동한다.

4. 삽입할 원소를 정렬된 부분의 원소와 하나씩 비교하면서 한 칸씩 밀어냄.

5. 최종 마지막 위치에 key값을 복사해줌.

 

3) 삽입정렬 복잡도 분석

- 최선 (이미 정렬된 경우): O(n) → 비교가 n-1번 이루어짐.

- 최악 (역순 정렬): O(n^2)

  → 모든 단계에서 앞에 놓인 요소가 전부 이동해야함.

  → 비교하는 데에 n(n-1)/2 = O(n^2)

  → 이동하는 데에 n(n-1)/2 + 2(n-1) = O(n^2)

- 평균적으로 O(n^2)에 정렬이 가능함.

- 많은 이동이 필요하기 때문에 레코드가 클 경우가 비효율적.

- 대부분 정렬되어 있는 배열의 경우 효율적으로 정렬이 가능함. 

- 안정정렬.