모두의 알고리즘 with 파이썬: 03 일반적인 삽입 정렬 알고리즘

3일반적인 삽입 정렬 알고리즘

이번에는 입력 리스트 안에서 직접 위치를 바꿔 정렬하는 삽입 정렬 프로그램을 살펴보겠습니다. 구체적인 동작 과정은 연습 문제 9-1 풀이에서 설명하겠습니다.

icon_cakewalk 프로그램 9-2

일반적인 삽입 정렬 알고리즘

◉ 예제 소스 p09-2-isort.py

# 삽입 정렬

# 입력: 리스트 a

# 출력: 없음(입력으로 주어진 a가 정렬됨)

def ins_sort(a):

n = len(a)

for i in range(1, n): # 1부터 n -1까지

key = a[i] # i번 위치에 있는 값을 key에 저장

# j를 i 바로 왼쪽 위치로 저장

j = i - 1

# 리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음

while j >= 0 and a[j] > key:

a[j + 1] = a[j] # 삽입할 공간이 생기도록 값을 오른쪽으로 한 칸 이동

j -= 1

a[j + 1] = key # 찾은 삽입 위치에 key를 저장

d = [2, 4, 5, 1, 3]

ins_sort(d)

print(d)a

icon_result 실행 결과

[1, 2, 3, 4, 5]

신간 소식 구독하기

뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.