삽입 정렬

• 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입
• 삽입정렬은 필요할 때만 위치를 바꿈 -> 데이터가 거의 정렬되어 있을 때 효율적
• 특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터들은 이미 정렬되어 있다고 가정함
• 정렬이 이루어진 원소는 항상 오름차순을 유지
• 삽입될 데이터보다 작은 데이터를 만나거나 앞에 더이상 데이터가 없으면, 그 위치에서 멈춤

 

[과정]

첫 데이터 '5'는 정렬되어있다고 판단하고, 두번째 데이터가 어디 들어갈지 찾는다.

두번째 데이터 '1'은 '5'의 왼쪽으로 들어가거나, 오른쪽으로 들어가는 두 경우만 존재한다.

오름차순으로 정렬한다고 했을때, '1'은 '5'보다 작고 '5'의 앞에 더이상 데이터가 없으므로, '1'은 '5'의 왼쪽에 삽입한다.

 

이어서 '4'가 어디 들어갈지 찾는다.

삽입할 수 있는 위치는 ['1'의 왼쪽, '5'의 왼쪽, '5'의 오른쪽]으로 총 3가지이다.

'4'는 '5'보다는 작지만 '1'보다는 크기 때문에 '1'과 '5'사이에 위치하게 된다.

 

'0'이 어디 들어갈지 찾는다.

'1', '4', '5'는 모두 '0'보다 작으므로 맨 앞으로 '0'을 보낸다.

 

'2'가 위치를 찾는다.

'5'부터 시작하여 찾을 위치를 보다가 '2'는 '1'보다 크므로 '1' 다음 위치에 놓는다.

 

마지막으로 '3'이 놓일 위치를 찾는다.

'5'부터 시작하여 찾을 위치를 보다가 '3'은 '2'보다 크므로 '2' 다음 위치에 놓는다.

 

[결과]

 

[소스 코드]

data = [5, 1, 4, 0, 2, 3]

for i in range(1, len(data)):
    for j in range(i, 0, -1):
        if data[j] < data[j - 1]:
            data[j], data[j - 1] = data[j - 1], data[j]
        else:
            break

print(data)

 

[시간복잡도]

반복문을 2번 중첩해서 돈다. -> O(N^2)

시간복잡도는 선택정렬과 같지만, 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. -> 최선의 경우 O(N)의 시간복잡도를 가진다.