반응형
예를 들면, i인덱스의 값이 i-1값보다 작으면 i-1값과 자리를 바꾸고 i-2와 다시 비교하는 과정을 반복합니다.
이과정을 반복하다보면 전체적으로 정렬된 리스트를 얻게됩니다.
파이썬 코드로 간단히 구현해보았습니다.
|
1
2
3
4
5
6
7
|
def insertion_sort(L):
for i in range(1, len(L)):
for j in range(i, 0, -1):
if L[j-1] > L[j]:
L[j-1], L[j] = L[j], L[j-1]
else:
break
|
cs |
4번째 줄에서 비교를 하고 5번째 줄에서 교환을 합니다. 만약 j값이 j-1값보다 크다면 break문을 통해 다음 비교를 실행합니다.
다음은 삽입 정렬의 시간복잡도에 대해서 알아보겠습니다.
인덱스 1일때 인덱스 0과 한번 비교하고 인덱스 2일때 인덱스1,인덱스0 총 2번 비교합니다.
인덱스 n-1일때 n-1번 비교를 합니다. 따라서 위의 식으로 나타낼 수 있습니다.
최선의 경우는 이미 정렬되어 있는 경우 총n번만 비교해보면 됩니다.
최악의 경우는 끝까지 다 비교해서 정렬을 하는 경우입니다. 오름차순으로 정렬해야하는데 내림차순으로 정렬되어있는경우입니다.
다음은 쉘정렬에 대해서 공부하겠습니다!
반응형
'자료구조' 카테고리의 다른 글
| [파이썬 자료구조] 합병정렬 (0) | 2020.06.10 |
|---|---|
| [파이썬 자료구조] 쉘정렬(Shell sort) (0) | 2020.06.10 |
| [파이썬 자료구조] Sorting: 선택정렬 (0) | 2020.06.10 |
| [파이썬 자료구조] 회문 검사 (0) | 2020.05.05 |
| [파이썬 자료구조] 괄호 매칭 (0) | 2020.05.05 |