Dev/Python

파이썬 알고리즘 - 삽입정렬

healthyryu 2017. 8. 20. 22:46

파이썬 알고리즘 - 삽입정렬

< 그림 위키피디아 - https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC >


내가 푼 방식

-> 모범 답안에 비해서 시간 복잡도가 높게 나왔다.

def insertion_sort(my_list):
for i in range(1, len(my_list)):
for i2 in range(0, i):
if my_list[i] < my_list[i2]:
small = i2
break
else:
small = i

if small != i:
a = my_list[i]

for j in range(i, small, -1):
my_list[j] = my_list[j-1]
my_list[j-1] = my_list[j-2]

my_list[small] = a


some_list = [11, 3, 6, 4, 12, 1, 2]
insertion_sort(some_list)
print(some_list)


모범답안

# 삽입 정렬
def insertion_sort(my_list):
for i in range(len(my_list)):
key = my_list[i]

# i - 1부터 시작해서 왼쪽으로 하나씩 확인
# 왼쪽 끝까지(0번 인덱스) 다 봤거나
# key가 들어갈 자리를 찾으면 끝냄
j = i - 1
while j >= 0 and my_list[j] > key:
my_list[j + 1] = my_list[j]
j = j - 1

# key가 들어갈 자리에 삽입
# 왼쪽 끝까지 가서 j가 -1이면 0번 인덱스에 key를 삽입
my_list[j + 1] = key

some_list = [11, 3, 6, 4, 12, 1, 2]
insertion_sort(some_list)
print(some_list)


반응형