버블정렬, 선택정렬에 이어 오늘은 삽입정렬을 정리해보자.
1. '삽입정렬' 매커니즘
여기 [4, 2, 7, 1, 3] 이란 배열이 있다.
(말로 풀어써봤는데, 읽기가 힘들어서 배열이 변화하는 모습으로 설명해봤다ㅎㅎㅎㅎ)
첫 번째 반복문 : "인덱스 0과 1에 주목"
[4, 2, 7, 1, 3] ->
[4, 4, 7, 1, 3] ->
[2, 4, 7, 1, 3]
두 번째 반복문 : "인덱스 0, 1, 2에 주목"
[2, 4, 7, 1, 3] -> (변동없음)
세 번째 반복문 : "인덱스 0, 1, 2, 3에 주목"
[2, 4, 7, 1, 3] ->
[2, 4, 7, 7, 3] ->
[2, 4, 4, 7, 3] ->
[2, 2, 4, 7, 3] ->
[1, 2, 4, 7, 3]
네 번째 반복문 : "인덱스 0, 1, 2, 3, 4에 주목"
[1, 2, 4, 7, 3] ->
[1, 2, 4, 7, 7] ->
[1, 2, 4, 4, 7] ->
[1, 2, 2, 4, 7] ->
[1, 2, 3, 4, 7]
배열 변화로 표현해도 처음에 확 와닿지는 않다ㅎㅎㅎㅎㅎ
음.... 일단 '임시변수'를 활용하는 것이 핵심이다.
인덱스 값을 -1씩 줄여가며 고정된 임시변수와 대소비교 한다.
앞 인덱스의 값이 더 크다면, 복사(시프트)를 통해 임시변수가 들어갈 자리를 만든다.
그래서,
[1, 2, 4, 4, 7] 처럼 중복되는 숫자가 정렬 도중에 보이는 것이다.
숫자 '3'이 배열에 없어서 사라진 것이 아니라, 임시변수에 저장되어 있다.
따라서,
숫자 3이 놓일 자리가 마련되면, 임시변수를 그 자리에 입력하면 끝이다.
2. 삽입정렬 코드
def insert_sort(list):
length = len(list)
for index in range(1, length): # 1, 2, 3, 4
# 임시변수
# 아래 while문에서 '비교'와 '복사(시프트)'가 진행되는 동안
# 임시변수값은 변경되지 않는다.
comp = list[index]
# 임시변수와 비교하게될 배열 인덱스
# - 1씩 감소하며 비교될 예정
cur_index = index
#임시변수(comp)보다 앞 인덱스의 값이 크다면 loop문 진행
while cur_index > 0 and list[cur_index - 1] > comp:
# 값을 '복사'해서 자리를 계속 만들어 준다.
list[cur_index] = list[cur_index - 1]
# 앞 인덱스들 데이터와의 대소비교를 하기 위해 -1 진행
cur_index -= 1
# (while loop 탈출 후) 적절한 위치에 임시변수 값 입력 list[cur_index] = comp
return list
list = [4, 2, 1, 7, 3]
sorted_list = insert_sort(list)
print(sorted_list)결과
3. 삽입정렬 효율
Worst case를 먼저 보자.
[4, 3, 2, 1] 처럼 내림차순으로 정렬된 배열이 최악의 경우다.
1) 비교 : 시그마(N-1)
- 데이터가 4개면, (3+2+1)으로 총 6번
2) 복사(시프트) : 시그마(N-1)
- 비교할 때마다 시프트 되기 때문
따라서,
'비교'와 '복사'만 해도 (N-1) * (N-1)
시간복잡도는 이미
O(n^2) 이 되어 버렸다.
하지만,
여기에 새로운 관점이 도입된다.
'최악의 상황'에서는 (버블, 선택, 삽입)정렬 모두 시간복잡도가 같지만!
'현실에서는 최악의 상황보다 '평균적인 상황'이 주류라는 것이다.
내림차순으로 정렬된 배열을 오름차순으로 정렬해야 하는 상황은 흔치 않다.
'적당히' 흩어져있는 배열을 정렬하는 경우가 대부분이다.
시나리오에 따라 삽입정렬의 효율이 바뀐다는 것이다.
삽입정렬
- 최악의 경우 : 비교는 시그마(N-1)회, 복사는 시그마(N-1)
- 최선의 경우 : 비교는 (N-1)회, 복사는 0회
- 평균값은 (N^2) / 2
이런 결과가 나오는건, '삽입'정렬이
반복문을 다 수행하지 않는 속성 때문이다.
앞에서 버블정렬과 선택정렬의 경우
모든 반복문을 다 순회해야 했다.
하지만, 삽입정렬을 보면
while cur_index > 0 and list[cur_index - 1] 이 조건을 만족하지 않으면,
굳이 while loop를 진행할 필요가 없게 되는 것이다.
배열 [1, 2, 3, 4] 를 통해 설명하자면,
숫자 '3'은 그 앞의 값인 2보다 크다.
"인덱스 0과 인덱스 1의 값을 더 볼 필요가 없다"
"이미 이전 단계의 반복문에서 검증된 정렬순서이기 때문에 그렇다"
따라서,
'추가 작업을 수행할 필요가 없게 되는 것이다.'
- One step at a time - 