[이코테 2021] 7. 삽입 정렬

🔊본 포스팅은 '(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬' 유튜브 강의를 수강하고 정리한 글입니다.

삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

삽입 정렬 동작 예시

[Step 0] 첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다.

[Step 1] 이어서 '9'가 어떤 위치로 들어갈지 판단한다.

'9'는 차례대로 왼쪽에 있는 데이터와 비교해서 왼쪽 데이터보다 더 작다면 위치를 바꿔 주고 그렇지 않다면 그냥 그자리에 머물러 있도록 한다.
'9'는 '7'보다 더 크기 때문에 현재 위치 그대로 내버려둔다.

[Step 2] 이어서 '0'이 어떤 위치로 들어갈지 판단한다.

'0'은 '9','7','5'와 비교했을 때 모두 작기 때문에 '5'의 왼쪽에 위치한다.

• 이러한 과정을 반복하면 다음과 같이 정렬이 완성된다.
  

삽입 정렬 소스코드

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

for i in range(1, len(array)):  # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
	for j in range(i, 0, -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)의 시간 복잡도를 가진다.