삽입 정렬 알고리즘

삽입 정렬

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

선택 정렬에 비해 구현 난이도가 높지만 일반적으로 더 효율적으로 동작

 

9를 7과 비교합니다. 7보다 더 크기 때문에 오른쪽에 위치에 놓습니다.

0을 9와 비교 9보다 작기 때문에 왼쪽으로 놓고 7과 비교해 작으니 왼쪽 5하고 비교하여 작기 때문에 왼쪽에 놓습니다.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
  for j in range(i, 0 , -1):
    # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
    if array[j] < array[j - 1]:
      # 한 칸씩 왼쪽으로 이동
      array[j],array[j - 1] = array[j - 1], array[j]
    else: 
      break
        # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
print(array) 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도 O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용

삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작

       최선의 경우 O(N)의 시간 복잡도를 가집니다.

       이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행한다면? O(N)