TIL - 단순 삽입 정렬

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다. 단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다.

예를 들어 3인 원소를 선택해 앞쪽에 삽입할 때 왼쪽에 이웃하는 원소가 선택한 원소(3)보다 크면, 그 값을 오른쪽에 이웃하는 원소(3)에 대입하고 앞으로 이동하면서 이 작업을 반복한다.
그러다가 선택한 값(3)보다 작은 원소를 만나면 그 보다 앞쪽은 스캔할 필요가 없고 그 위치에 선택한 값(3)을 삽입한다.

Python 실습

n = len(a)
for i in range(1, n):
  j = i
  tmp = a[i]
  while j > 0 and a[j - 1] > tmp:
    a[j] = a[j - 1]
    j -= 1
  a[j] = tmp

이 알고리즘은 서로 떨어져 있는 원소를 교환하지 않으므로 안정적이라고 할 수 있다. 비교와 교환 횟수는 모두 n^2 / 2번이다.