PYTHON, ALGORITHM
[python]삽입정렬
((•_•))
2021. 2. 18. 23:44
삽입정렬은 특별한 경우, 즉 정렬되어있는 리스트가 입력값으로 전달되는 경우 O(n)이고, 일반적으로는 선택정렬과 같이 O(n^2)이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def ins_sort(a): #오름차순
n=len(a)
for i in range(1, n): #idx:1~n-1(끝)
key=a[i]
j=i-1
while j>=0 and a[j]>key:
a[j+1]=a[j]
j-=1
print(a, key)
a[j+1]=key
d=[2, 4, 5, 1, 3]
ins_sort(d)
print(d)
|
cs |
이해를 돕기위해 9번째줄에 print(a, key)로 출력을 했다.
그 결과값은 아래와 같다.
key가 1일때와 3일때만 while문을 실행하는 것을 알 수 있다.
print(a, key) 이것을 11번째 줄에 집어넣을 경우, 결과값은 아래와 같다.
key가 4와 5일 경우 리스트의 형태는 변하지 않는다. 하지만 key가 1, 3일 경우에는 상황이 달라진다.