[알고리즘] 삽입 정렬
1. 삽입 정렬 (insertion sort) 란?
- 삽입 정렬은 두 번째 인덱스부터 시작
- 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
- 이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동
두 번째 인덱스(cur) 부터 시작해서, 앞에 있는 값들과 cur 값을 비교한다.
앞에 있는 값이 cur 값보다 크다고 해도, 바로 swap 하는게 아니라!
계속해서 비교하다가,
맨 처음 인덱스이거나 혹은 cur 값보다 작은 값을 만난 위치에 cur 값을 삽입한다.
이 사이트에서 시뮬레이션을 확인하자!
2. 어떻게 코드를 만들까?
데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
예: data_list = [9, 3, 2, 5]
- 첫 번째 턴
- key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: [3, 9, 2, 5] - 두 번째 턴
- key값은 2, 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: [2, 3, 9, 5] - 세 번째 턴
- key값은 5, 9보다 5이 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝: [2, 3, 5, 9]
3. 알고리즘 구현
def insertionSort(data):
for i in range(len(data)-1): # i는 턴
for j in range(i+1, 0, -1): # j는 비교 # j가 최소 1이어야 아래 코드에서 j-1번째 인덱스까지 판단 가능!
if data[j] < data[j-1]: # 내가 내 앞 데이터보다 작다면 swap
data[j], data[j-1] = data[j-1], data[j]
else:
break # 내가 swap 될 필요 없다면, 더 앞 데이터와 비교할 필요 없이 해당 턴을 멈추기
return data
참고
🌟
for j in range(i+1, 0, -1)에서 range를 살펴보자!
i+1: 바로 윗 줄에서 i가 0부터 시작하기 때문에 비교 대상은 1번째 인덱스부터가 된다0: j가 최소 1 이어야 아랫 줄에서 j-1번째 인덱스까지 판단할 수 있다-1: 앞으로 한칸씩 이동하며 비교한다
코드 이미지
테스트
4. 알고리즘 분석
- 반복문이 두 개 $O(n^2)$
- 최악의 경우, $\frac{n(n−1)}{2}$ - 완전 정렬이 되어 있는 상태라면 최선은 $O(n)$
-else문에서break에 걸려 다음 턴을 진행하지 않기 때문
💛 개인 공부 기록용 블로그입니다. 👻