정렬 알고리즘을 유도해보자
컴퓨터 프로그래밍을 하면 절대로 빠뜨릴 수 없는 것이 정렬 알고리즘이다. 그 중에서 잘 알려진 3개를 간단히 살펴보자.
Selection Sort
따로 알고리즘을 배우지 않은 사람에게 정렬 알고리즘을 만들어보라 하면 가장 먼저 떠올릴 법한 방식이 선택정렬(Selection Sort)이다. 전체 리스트 중에서 가장 작은 값을 찾아서 첫 번째 자리에 넣고, 남은 리스트 중에서 가장 작은 값을 찾아서 두 번째 자리에 넣는 방식이다. 구체적인 예로 보자.
입력값: [3, 2, 5, 1, 4]
1단계: 3과 2를 비교하니 2가 더 작다. 2와 5를 비교하니 2가 더 작다. 2와 1을 비교하니 1이 더 작다. 1과 4를 비교하니 1이 더 작다. 최솟값은 1이므로, 3과 1의 자리를 바꾼다.
중간 결과: [1, 2, 5, 3, 4]
2단계: 첫째 자리는 확정되었으니 이제는 두 번째 값을 찾자. 2와 5를 비교하니 2가 더 작다. 2와 3을 비교하니 2가 더 작다. 2와 4를 비교하니 2가 더 작다. 최솟값 2가 이미 두 번째 자리에 있으므로 자리바꿈이 필요없다.
중간 결과: [1, 2, 5, 3, 4]
이 과정을 4번째 자리까지 반복하면 정렬이 끝난다. 매우 직관적이고 단순하지만, 비효율적인 면도 보인다. 어떻게 개선할 수 있을까?
Insertion Sort
선택정렬에서 불필요하게 반복되는 연산을 찾아보자. 일단 눈에 띄는 것은 최솟값을 찾기 위해 무조건 리스트를 끝까지 확인한다는 점이다. 예제에서 입력값 [3, 2, 5, 1, 4] 중 마지막 값 2개는 이미 정렬되어 있으므로 사실상 1까지만 비교해보면 된다. 2단계에서도 [1, 2, 5, 3, 4] 중 마지막 2개가 정렬되어 있으므로 마지막 4까지 비교할 필요가 없다. 이 정보를 이용해서 계산의 낭비를 줄일 수 있다.
입력값 [a, b, c, d, e]에서 [b, c, d, e]가 이미 정렬되어 있다고 “가정”해보자. 그러면 정렬 작업은 매우 간단해진다. b, c, d, e를 앞에서부터 순서대로 a와 비교하다가 처음으로 a보다 큰 값을 만나면 그 앞에 a를 끼워넣으면 된다. [3, 1, 2, 4, 5]를 생각하면 쉽다. 문제는 [b, c, d, e]는 실제로는 정렬되어 있지 않다는 점인데, 이럴 때는 재귀적으로 생각하자.
- 입력값: [3, 2, 5, 1, 4]
- [2, 5, 1, 4]를 정렬한 뒤, 적당한 위치에 3을 끼워넣는다. 그러려면 먼저 [2, 5, 1, 4]를 정렬해야 한다.
- [5, 1, 4]를 정렬한 뒤, 적당한 위치에 2를 끼워넣는다. 그러려면 먼저 [5, 1, 4]를 정렬해야 한다.
- [1, 4]를 정렬한 뒤, 적당한 위치에 5를 끼워넣는다. 그러려면 먼저 [1, 4]를 정렬해야 한다.
- [1, 4]를 정렬한다. 값이 2개밖에 없을 때는 1) 그대로 두거나 2) 두 값을 바꿔치거나 둘 중의 하나다.
재귀이므로 실제 적용 순서는 4단계부터 1단계로 거꾸로가 된다. 입력값 [3, 2, 5, 1, 4]에서 먼저 제일 뒤의 [1, 4]를 정렬하고, 거기에 5를 끼워넣고, 다음에 2를 끼워넣고, 마지막에 3을 집어넣는다. 이 과정에서 실제로 일어나는 비교 연산은 순서대로 (1 < 4), (5 > 1), (5 > 4), (2 > 1), (2 < 4), (3 > 1), (3 > 2), (3 < 4)이다.
앞뒤 순서가 바뀐 것만 빼면, 이게 바로 삽입정렬(Insertion Sort)이다.
Merge Sort
여기에는 낭비가 없을까? 실제로 수행한 비교 연산을 보면, (2 > 1), (2 < 4), (3 > 1), (3 > 2), (3 < 4)가 있는데, 군더더기가 눈에 띈다. (3 > 2)와 (2 > 1)를 이미 알고 있다면, (3 > 1)은 굳이 비교할 필요가 없다.
왜 (3 > 1) 비교가 필요했는지를 살펴보면, [2, 5, 1, 4]를 정렬해서 [1, 2, 4, 5]가 나온 상황에서 3을 어디에 넣을지 찾기 위해서다. 그 직전 단계에서 [1, 4, 5]에 2를 넣기 위해서 (2 > 1) 비교를 이미 해보았지만, 그 정보를 사용할 수가 없었기 때문에 다시 처음부터 하나씩 비교해야 했던 것이다. 2와 3을 독립적으로 추가하지 않고, (2 < 3)이라는 정보를 활용한다면 이 낭비를 제거할 수 있다.
예를 들어보자. 입력값 [3, 2, 5, 1, 4]를 [3, 2]와 [5, 1, 4]의 두 리스트로 나누어서 정렬하여 [2, 3]과 [1, 4, 5]을 얻었다면, 이 둘을 효율적으로 합칠 수 있을까? 이미 정렬되어 있다는 사실을 십분 활용하자. 앞에서부터 비교하면서 더 작은 쪽 리스트의 값을 최종 리스트에 추가하면 된다.
- 왼쪽 리스트는 [2, 3], 오른쪽 리스트는 [1, 4, 5]로 시작한다. 최종 리스트는 비어있다.
- 2와 1을 비교하니, 1이 더 작으므로 1을 최종 리스트에 추가한다.
- 2와 4를 비교하니, 2가 더 작으므로 2를 최종 리스트에 추가한다.
- 3과 4를 비교하니, 3이 더 작으므로 3을 최종 리스트에 추가한다.
- 왼쪽 리스트가 소진되었으므로 남은 오른쪽 리스트를 그대로 최종 리스트에 추가한다.
앞선 방식과의 차이를 알 수 있을 것이다. 삽입정렬에서는 [1, 4, 5]에 3과 2를 독립적으로 추가해야 했기 때문에 5번의 비교가 필요했다. (2 > 1), (2 < 4), (3 > 1), (3 > 2), (3 < 4) 하지만, 새로운 방식에서는 [2, 3]으로 이미 정렬해놓았기 때문에 (3 > 1)이라는 불필요한 비교를 제거할 수 있었다. 총 4번의 비교만으로 원하는 정보를 모두 얻었다. (2 < 3), (2 < 1), (2 > 4), (3 < 4) 겨우 하나 차이라고 할 수도 있겠지만, 재귀적으로 적용되기 때문에 정렬할 리스트가 길어질수록 차이가 커진다. 이 알고리즘을 병합정렬(Merge Sort)이라고 부르는데, 절차를 정리하면 다음과 같다.
- 정렬할 리스트를 절반씩 나누어 두 개의 서브 리스트를 만든다.
- 두 서브리스트를 정렬한다. (재귀적으로)
- 정렬된 서브리스트를 하나로 합친다.