알고리즘의 예술, 삽입 정렬
알고리즘의 꽃이라는 정렬 알고리즘 중 삽입 정렬 구현
현재 학습 중인 코딩 책을 처음 개관할 때, '4장 재귀'를 건너뛰고 '5장의 정렬'과 '6장의 검색'부터 실습하고 4장을 학습하는 것으로 계획했었다. 왜냐하면, 재귀보다는 정렬과 검색 알고리즘 구현이 실무에서도 많이 들어봤고, 쉬울 거라고 판단했었기 때문이었다.
하지만 저자의 의도와 진도를 빼면 뺄수록 느껴지는 책의 내공으로, 차례대로 학습하지 않았으면 더 오래 시간이 걸릴 뻔했다. 어쨌든 보기와 달리 '삽입 정렬' 알고리즘 하나 제대로 구현하는데도 주말을 전부 헌납해야 했다. 그리고 4장에서 배운 재귀의 개념은 이 정렬 알고리즘을 구현하는데도 멲함수처럼 계속 쓰였다.
삽입 정렬 알고리즘은 선택 정렬 알고리즘보다 구현하기가 까다로웠다. 왜냐하면 인터넷에서 검색되는 다른 삽입 정렬 알고리즘은 파이썬으로도 array() 함수를 사용하여 더 쉽게 구현할 수 있었으나, 이 책의 저자는 재귀 함수와 꼬리 재귀 함수, while-루프와 for-루프 버전까지 처음에 발상한 리스트 귀납 구조에서 비롯된다는 것을 강조했다.
모든 게 재귀였다. 그 가운데 삽입 정렬의 구현은 실무에서 그나마 사용된다는 병합 정렬이나, 퀵 정렬보다는 쉽더라도, 꼬리 재귀 함수로 구현하고 이것의 실행을 추적하면서 실제 함수의 파라미터 값을 일일이 쫓는데 하루가 금방 지나갔다.
사실, 삽입 정렬의 재귀함수 구현은 처음에 단 한 번의 시도로 깔끔하게 구현했었다. 그래서 이후 꼬리 재귀 함수와 while-루프 버전까지 쉬우리라 예단했는데, 막힌 지점은 가장 작은 수를 왼쪽으로 보내는 insert() 함수가 아니라, 기존의 리스트에서 insert() 함수를 통해 반환된 가장 왼쪽의 작은 수를 차례로 정렬시키는 insertion_sort() 함수에서 꼬리 재귀 함수로 만드는 파트였다(아래).
삽입 정렬_꼬리 재귀 함수 구현 이해 완료 (github.com)
하지만, 함수의 로직을 일일이 하나씩 쫓아가면 결국 이 함수의 기능과 삽입 정렬의 개념을 아래와 같이 단순화시킬 수 있었다.
그리고 아래와 같이 insertion_sort 함수를 'for 루프 버전'으로 바꾸면 이 알고리즘이 얼마나 많은 시행착오를 통해서 이렇게 간결하게 설계할 수 있었는지를 실감할 수 있다. 간단하게 설명하면 xs 리스트인 [2,5,4,3] 중 맨 앞의 x의 값 2부터 시작하여 5, 4, 3을 xs 리스트 값들 중 어느 사이에 삽입하는 것이 순서대로 숫자를 나열하는 것인가를 구현한 알고리즘이다. insert() 함수 자체가 재귀 함수이다.
def insertion_sort(xs):
ss = []
for x in xs:
ss = insert(x, ss)
return ss
def insert(x, ss):
left = []
while ss != []:
if x <= ss[0]:
left.append(x)
return left + ss
else:
left.append(ss[0])
ss = ss[1:]
left.append(x)
return left
# Test code
print(insertion_sort([2,5,4,3]))
위의 함수 중 insert(x, ss) 함수를 도식화하면 아래와 같다.
프로그래밍의 정석(도경구, 2021)