[문제] 삽입 정렬 구현하기

문제

반복문을 활용해 삽입 정렬 알고리즘을 구현하세요.

insertion_sort() 함수는 data를 파라미터로 받아 삽입 정렬 알고리즘을 실행해 리스트를 오름차순으로 정렬합니다.

이 함수는 리스트를 정렬할 뿐 어떤 값을 리턴하지는 않습니다.

삽입 정렬은 직관적이지만 실제로 구현하는 것은 생각보다 어려울 수 있습니다.

삽입 정렬 레슨을 여러 번 다시 보고 알고리즘을 어떻게 구현해야 할지 생각해 보세요.

 

실습 해설

 

삽입 정렬은 정렬된 범위를 점점 더 넓혀가면서 키라는 값을 적당한 위치에 삽입하는 걸 반복하는 알고리즘입니다.

예를 들면 1번 인덱스를 키로 하고 0번 인덱스에서 0번 인덱스까지의 범위(요소가 0번 인덱스 하나뿐인 범위)에서 적당한 위치를 찾아 키 값을 집어 넣습니다.

2번 인덱스를 키로 하고 0번 인덱스에서 1번 인덱스까지를 범위로 해서 적당한 위치에 키를 집어 넣고요, 3번 인덱스를 키로 하고 0번 인덱스에서 2번 인덱스까지를 범위로 해서 적당한 위치에 키를 집어 넣죠.

 

바깥쪽 반복문 작성하기

이렇게 '범위를 계속 넓혀가면서', 그 '범위 안에서 요소들을 차례대로 비교'하고 키가 들어갈 위치를 찾는 걸 반복하는데요, 그래서 i와 j, 두 개의 반복 변수가 있는 중첩된 반복문 구조가 필요합니다.

바깥쪽 반복문은 변수 i로 리스트가 어디까지 정렬되어 있는지 범위를 저장합니다.

예를 들어서 i가 5라면 인덱스 0에서 4까지가 정렬되어 있고 data[5]를 정렬할 차례라는 의미인데요, 이 data[i]에 해당하는 값을 '키'라고 부르죠.

for i in range(len(data)):
    key = data[i]

여기서 i가 0 대신 1부터 시작하도록 변경할 수 있는데요. 왜냐하면 i가 0이면 인덱스 0보다 앞에 있는 요소들이 전부 정렬되었다는 의미인데, 이 범위에는 요소가 하나도 없죠?

그래서 생략하고 인덱스 1부터 반복하면 불필요한 단계를 줄일 수 있답니다.

for i in range(1, len(data)):
    key = data[i]

이제 변수 j를 사용해서 안쪽 반복문을 구현해 봅시다.

 

안쪽 반복문에서 변수 j 정의하기

i 값마다 j는 i-1에서 시작해서 오른쪽에서 왼쪽으로 이동합니다.

다음과 같이 for문을 쓰면 j가 i-1에서 0까지 이동하도록 할 수 있습니다.

for i in range(1, len(data)):
    key = data[i]
    for j in range(i - 1, -1, -1):

for문 대신에 while문을 사용할 수도 있습니다.

for i in range(1, len(data)):
    key = data[i]
    j = i - 1
    while j >= 0:
        j -= 1

둘 다 올바른 구현 방법입니다. 하지만 반복문에서 탈출하는 조건이 여러 개라면 for문보다는 while문을 사용하는 것이 더 편한데요.

삽입 정렬을 계속 구현하다 보면 왜 for문 보다 while문을 사용하는 게 나은지 알게 되실 겁니다.

 

안쪽 반복문 구현하기

안쪽 반복문에선 뭘 해야 할까요? 궁극적으로 해야 하는 일은 key의 올바른 위치를 찾는 건데요, 반복문을 다 도는 동안 올바른 위치를 찾아서 key에 해당하는 값을 집어 넣으면 됩니다.

key가 들어갈 위치를 찾을 때까지 j를 감소시켜야 하죠.

그럼 어떤 조건들일 때 j를 감소시켜야 할까요?

 

첫째로, key가 data[j]보다 작아야 합니다.

key가 data[j]보다 크거나 같으면 해당하는 위치에서 key를 삽입하면 되기 때문에 반복문을 끝내면 됩니다.

 

둘째로, j는 항상 0보다 크거나 같아야 합니다.

j가 0보다 작으면 더 이상 확인할 요소가 없기 때문에 반복문을 끝내면 됩니다.

while문의 조건을 다시 작성해 볼게요.

while j >= 0 and key < data[j]:
    j -= 1

이제 이 두 조건이 모두 충족되면 반복문이 실행되는데요, key가 mdata[j]보다 작기 때문에 j에 있는 요소는 오른쪽으로 한 칸 이동해 줄게요.

data[j + 1]를 data[j] 값으로 할당해 줍시다.

while j >= 0 and key < data[j]:
    data[j + 1] = data[j]
    j -= 1

이렇게 되면 두 개의 인덱스 j와 j+1에 일시적으로 중복된 정보가 저장되는데요, 그럼 한 요소에 대한 정보는 없어지게 되는 걸까요?

바깥쪽 반복문이 시작될 때 이미 키에 해당하는 값은 변수 key에 저장했기 때문에 괜찮습니다.

key에 저장된 값의 올바른 위치를 찾을 때까지 while문을 실행하고, while문이 종료될 때 key 값의 삽입이 완료될 겁니다.

 

올바른 위치에 key 삽입하기

while문이 종료된다는 건  j가 -1이거나 key가 data[j]보다 크거나 같다는 의미인데요.

첫 번째 경우는 리스트의 가장 왼쪽에 도달했을 때입니다(j가 -1인 경우). 이때는 key를 인덱스 0인 j + 1에 삽입해 주면 됩니다.

두 번째 경우는 key가 인덱스 j에 있는 값보다 크거나 같으므로 key를 인덱스 j + 1에 삽입해 줍니다.

따라서 두 경우 모두 key를 인덱스 j + 1에 삽입해 주면 됩니다.

while j >= 0 and key < data[j]:
    data[j + 1] = data[j]
    j -= 1
data[j + 1] = key

모범답안

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and key < data[j]:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key

# 테스트 코드
list_1 = [9, 4, 2, 3, 1, 8, 1]
list_2 = [1, 2, 5, 2, 10, 16, 2]
list_3 = [10, 8, 6, 4, 2, 1]

insertion_sort(list_1)
insertion_sort(list_2)
insertion_sort(list_3)

print(list_1)
print(list_2)
print(list_3)

공감과 댓글은 저에게 큰 힘이 됩니다.

 

Starting Google Play App Distribution! "Tester Share" for Recruiting 20 Testers for a Closed Test.

Tester Share [테스터쉐어] - Google Play 앱