삽입 정렬
문제) 리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 알고리즘을 만들어라.
#쉽게 설명한 삽입 정렬
#입력 : 리스트 a
#출력 : 정렬된 새 리스트
def find_ins_idx(r, v):
for i in range(0, len(r)):
if v < r[i]:
return i
return len(r)
def ins_sort(a):
result = []
while a:
value = a.pop(0)
ins_idx = find_ins_idx(result, value)
result.insert(ins_idx, value) #찾은 위치에 값 삽입(이후 값은 한 칸씩 밀려남)
return result
d = [2, 4, 5, 1, 3]
print(ins_sort(d))#삽입 정렬
#입력 : 리스트a
#출력 : 없음(입력으로 주어진 a가 정렬됨)
def ins_sort(a):
n = len(a)
for i in range(1, n):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)연습문제
8-1) 일반적인 삽입 정렬 알고리즘을 사용해서 리스트 [2, 4, 5, 1, 3]을 정렬하는 과정을 적어라.
| 2 4 5 1 3
2 | 4 5 1 3
2 4 | 5 1 3
2 4 5 | 1 3
1 2 4 | 5 3
1 2 4 5 | 3
1 2 3 4 | 5
1 2 3 4 5 |
8-2) Unit 8에서 설명한 정렬 알고리즘은 숫자를 작은 수에서 큰 수 순서로 나열하는 오름차순 정렬이었다. 이를 큰 수에서 작은 수 순서로 나열하는 내림차순 정렬로 바꾸려면 프로그램의 어느 부분을 바꿔야 하는가?
a[j] < key 에서 부등호 '>'를 '<'로 바꾼다.
def ins_sort(a):
n = len(a)
for i in range(1, n):
key = a[i]
j = i - 1
while j >= 0 and a[j] < key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)출처
모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10
.