참고: 이 글은 루비(Ruby)로 다양한 정렬 알고리즘을 구현해 보는 시리즈의 네 번째 편입니다. 1편에서는 버블 정렬을, 2편에서는 선택 정렬을, 3편에서는 병합 정렬을 다루었습니다.
데이터를 정렬하는 여러 방법론을 계속 탐색해 오던 중, 이번에는 삽입 정렬(Insertion Sort)을 살펴보겠습니다. 삽입 정렬에는 좋아할 만한 이유가 세 가지나 있습니다! 첫째, 삽입 정렬은 안정 정렬(stable sort)입니다. 즉, 키 값이 같은 요소들의 상대적인 순서가 유지됩니다. 둘째, 제자리(in-place) 알고리즘이기 때문에 정렬된 결과를 담기 위해 새로운 배열을 추가로 생성하지 않습니다. 마지막으로, 곧 확인하게 되겠지만 구현 난이도가 상당히 낮다는 점도 큰 매력입니다.
삽입 정렬, 왜 배워야 할까?
같은 이야기를 반복하는 듯 느껴질 수 있지만, 앞선 모든 포스트에서 강조했듯이 데이터를 정렬하는 다양한 메커니즘과 각 방법의 트레이드오프를 이해하는 것은 매우 중요합니다. 예를 들어, 삽입 정렬은 대규모 데이터셋에는 적합하지 않지만(아래에서 자세히 다룹니다), 작은 데이터셋이나 이미 거의 정렬된 데이터에는 충분히 효율적일 수 있습니다. 그 이유는 구현 과정을 함께 살펴보면 자연스럽게 이해하게 될 것입니다.
물론 실무에서는 주로 프로그래밍 언어가 제공하는 내장 정렬 메서드를 사용합니다. 하지만 삽입 정렬은 코딩 인터뷰에서 페어 프로그래밍 과제나 시간 복잡도 관련 질문으로 등장할 수 있는 주제이기도 합니다. 이 글을 끝까지 읽고 나면 삽입 정렬을 직접 구현할 수 있을 뿐만 아니라, 시간 복잡도까지 어렵지 않게 설명할 수 있게 될 것입니다.
시각적으로 이해하기
코딩에 들어가기 전에 아래 영상을 확인해 보시길 강력히 추천합니다. 삽입 정렬을 '춤'으로 설명하는 영상인데, 저는 개인적으로 몇 번을 봐도 질리지 않습니다! :)
코드 단계별 분석
이제 코드를 살펴보겠습니다.
def insertion_sort(array)
for i in 1...(array.length) # Step 1
j = i # Step 2
while j > 0 # Step 3
if array[j-1] > array[j] # Step 4
temp = array[j]
array[j] = array[j-1]
array[j-1] = temp
else
break
end
j = j - 1 # Step 5
end
end
return array
end
Step 1
for 루프를 사용해 변수 i를 1로 초기화하고, 배열의 길이와 같아질 때까지 값을 하나씩 증가시킵니다.
Step 2
또 다른 변수 j를 만들고 i의 값으로 초기화합니다.
Step 3
다음으로 중첩된 while 루프가 등장하며, j가 0보다 큰 동안 계속 실행됩니다. j가 1부터 시작하므로 최소 한 번은 실행된다는 것을 알 수 있습니다.
Step 4
if... else 블록은 처음에는 다소 복잡해 보일 수 있지만, 차근차근 살펴보면 전혀 어렵지 않습니다(이해가 안 되면 위의 춤 영상을 다시 참고하세요!).
if 조건에서는 array[j-1]이 array[j]보다 큰지 검사합니다. 현재 j가 1이므로, 사실상 array[0]과 array[1], 즉 배열의 첫 두 요소를 비교하는 셈입니다.
앞의 요소(array[0])가 뒤의 요소(array[1])보다 크다면 당연히 자리를 바꿔야 하며, 이것이 if 블록 안에서 수행되는 스왑(swap) 로직입니다. 반대로 array[0]의 값이 더 작다면 이미 정렬된 상태이므로 아무 작업도 필요 없고, else 블록의 break를 통해 루프를 빠져나옵니다.
Step 5
이후 j를 1 감소시킵니다. 그러면 다시 for 루프로 돌아가고, 이번에는 i가 2가 됩니다. 첫 번째 반복에서는 array[1]과 array[2]를 비교하고, j가 이번에는 1이 아니라 2부터 시작했기 때문에 while 루프를 한 번 더 돌게 된다는 점을 상상해 볼 수 있습니다.
실제 데이터로 따라가기
다음 예시 배열로 코드를 직접 추적해 보겠습니다: [5,7,2,10,9,12]
첫 번째 반복: 5와 7을 비교합니다. 5 < 7이므로 즉시 조건문을 벗어나 다음 단계로 넘어갑니다.
두 번째 반복: 7과 2를 비교합니다. 이번에는 자리를 바꿔야 하므로 배열은 [5, 2, 7, 10, 9, 12]가 됩니다. 이어서 2를 5와 다시 교환하여 최종적으로 [2, 5, 7, 10, 9, 12]가 됩니다.
세 번째 반복: 10과 7을 비교합니다. 이미 올바른 순서라서 추가 작업이 필요 없습니다!
네 번째 반복: 10과 9를 비교하여 자리를 바꿉니다. 그다음 7이 9보다 작으므로 더 이상의 교환은 일어나지 않습니다. 현재 배열은 [2, 5, 7, 9, 10, 12]입니다.
마지막 반복: 12가 10보다 크다는 것이 확인되면 끝! 정렬이 완료되었습니다.
성능 분석
앞서 살펴본 정렬 알고리즘 중 버블 정렬처럼 실무에서 거의 사용되지 않는 것들도 있었지만, 삽입 정렬은 나름 합리적인 선택지가 될 수 있습니다. 배열이 이미 정렬되어 있다고 상상해 보세요. 삽입 정렬은 매우 빠르고 효율적으로 실행됩니다. 반대로 역순으로 정렬된 배열을 처리해야 한다면 어떻게 될까요? 삽입 정렬에게는 악몽과 같은 상황입니다.
배열이 이미 정렬되어 있다면, 삽입 정렬은 단순히 n번 순회만 하면 되기 때문에 O(n)의 성능을 보입니다. 직접 확인하고 싶다면 메서드 상단에 puts i를 추가하고, 미리 정렬된 배열을 인자로 넘겨 프로그램을 실행해 보세요.
반면 배열이 역순으로 정렬되어 있다면, 삽입 정렬은 O(n^2)의 성능을 보입니다. 머릿속으로 그려볼 수 있을 겁니다. 연속적인 스왑이 발생해야 하므로 모든 요소마다 if 조건을 통과하게 되기 때문입니다. 역시 카운터 변수를 만들어 출력하면서 역순 배열을 넣어 직접 실험해 보시기 바랍니다.
최악의 경우가 O(n^2)이라는 점은 버블 정렬과 선택 정렬과 동일하지만, 일반적으로는 삽입 정렬이 더 선호됩니다. 앞서 확인했듯이 삽입 정렬의 최선의 경우는 O(n)인 반면, 선택 정렬의 최선의 경우는 O(n^2)이기 때문입니다. 또한 삽입 정렬은 버블 정렬보다 스왑 횟수가 적어, 이 대결에서도 승리합니다.
마치며
이 글이 도움이 되었기를 바라며, 삽입 정렬의 장단점과 알고리즘이 작동하는 원리를 확실히 이해하셨기를 바랍니다. 더 깊이 알아보고 싶다면 위키피디아의 삽입 정렬 문서를 참고해 보시길 추천합니다.