삽입 정렬(Insertion sort)은 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다. 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어 있을 때’ 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다.
첫 번째 데이터는 그 자체로 정렬이 되어 있다고 가정하고 두 번째 데이터를 첫 번째 데이터와 비교해서 첫 번째 데이터보다 크면 왼쪽에 삼입한다. 세 번째 데이터부터 마찬가지로 본인보다 작은 데이터를 찾아 오른쪽에 삽입한다.
왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입되면 되는 것이다.
[삽입 정렬을 코드로 직접 구현]
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i range(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)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
참고로 range의 매개 변수 3개(start, end, step)이다. 세 번쨰 매개 변수인 step에 -1이 들어가면 start 인덱스부터 시작해서 end + 1 인덱스까지 1씩 감소한다. 앞의 코드에서는 j 변수가 i부터 1까지 1씩 감소한다.
삽입 정렬의 시간 복잡도
삽입 정렬의 시간 복잡도도 선택 정렬과 마찬가지로 O(N2)이라고 표현할 수 있는데, 이는 반복문이 2번 중첩되어 사용되었기 때문이다. 하지만 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다. 최선의 경우 O(N)의 시간 복잡도를 가진다. 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬 등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.
ref
이것이 취업을 위한 코딩 테스트다 with 파이썬
나동빈 유튜브 강의