전체가 한눈에 보일 때
삽입 정렬 알고리즘 recall
운전 중에 신호에 막혀서 가다 서다를 반복하다 빨간불에 대기하고 있다가 든 생각이다. 인간의 사고방식도 일정 구간마다 대기하고 있는 신호등 체계와 같이 직렬식이라고 가정한다면,
인간이 할 수 있는 생각의 한계를 넓히는 방법은 구간마다의 신호등 색깔이 초록색으로 동시 다발적으로 바뀌게 하는 것과 비슷하지 않을까?
대기하고 있는 신호등이 초록색으로 바뀌었을 때, 지나가고 곧바로 마주치는 신호등의 색깔이 초록색으로 바뀌어서 바로 지나가고, 또 지나치는 신호등의 색깔이 때마침 초록색으로 바뀌어 바로 지나가는 이 과정과 같이 동시다발적인 논리적 신호(전부 on)가 길면 길수록 내가 생각할 수 있는 범위가 지금과는 달리 더 넓지 않을까 말이다.
파이썬의 정렬 알고리즘의 퀵 정렬까지 마무리하고, 다시 처음부터 정렬 알고리즘을 스스로 환기시키는 마당에 삽입 정렬의 묘미는 새로웠다. 무작정 화이트보드에 생각나는 대로 알고리즘을 자연어(psuedo)로 기술하여 코드로 다시 구현하면서 각기의 함수를 한 번에 보니 백 트래킹(함수 실행 추적, 디버깅)의 중요성을 깨달을 수 있었다.
사실 퀵 정렬 함수보다 이 삽입 함수에서 재귀 함수 구현이 필자에겐 상당한 부하를 안겨다 줬었는데, 무지한 자에게는 역시 '반복과 이해'의 선순환밖에 답이 없다는 것을 알았다.
이 삽입 정렬(Insertion Sort) 함수는 아래와 같은 함수 실행 추적을 가진다는 것을 스스로 긁적일 수 있다면, 사실 코드 구현에 치중해서 알고리즘 자체를 이해하기보다는, 왜 이 알고리즘을 '삽입 정렬'이라고 부르고 삽입라는 별개의 함수(Insert)를 두어 중첩 재귀(nested recursion) 구조와 같이 만들었는지를 알 수 있다.
리스트 [3,5,4,2]에 대한 백트래킹 과정이다. 이것만 정확하게 본인이 직접 써 내려갈 수 있으면 이 함수의 이해는 끝난다.
insertionSort([3, 5, 4, 2])
-> insert([3], insertionSort([5,4,2]))
-> insert([3], insert([5], insertionSort([4,2])))
-> insert([3], insert([5], insert([4], (insertionSort([2]))))
-> insert([3], insert([5], insert([4], (insert([2], [ ]))))
-> insert([3], insert([5], insert([4], [2])))
-> insert([3], insert([5], [2] + insert([4], [ ])))
-> insert([3], insert([5], [2] + [4])))
-> insert([3], insert([5], [2, 4])))
-> insert([3], [2] + insert([5], [4]))
-> insert([3], [2] + insert([4], insert([5], [ ])))
-> insert([3], [2] + insert([4, 5]))
-> insert([3], [2, 4, 5])
-> [2] + insert([3], [4, 5])
-> [2] + [3] + [4, 5]
-> [2] + [3, 4, 5]
-> [2, 3, 4, 5]
