[Algorithm] 삽입 정렬

삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다, 선택정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다. 다음과 같은 예제를 생각해보자.

 

 

 

 

특정한 데이터가 삽입될 위치를 선정할 때 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추면 된다.

이 과정을 N - 1번 반복하게 되면 다음과 같이 모든 데이터가 정렬될 것이다!

 

이를 파이썬 코드로 구현해보자.

 

#삽입 정렬

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

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

 

삽입 정렬의 시간 복잡도는 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(Nlog N)을 기대할 수 있다. 그러나 최악의 경우 O(N^2)의 시간 복잡도를 가진다.