[알고리즘] 정렬 알고리즘 (2)

팀 정렬 (Tim sort)

팀 정렬은 삽입 정렬(insertion sort)과 합병 정렬(merge sort)을 조합한 정렬 알고리즘이다. 이 알고리즘도 시간 복잡도는 O(N log N)인데, 다른 O(N log N)을 가지는 정렬 알고리즘들에 비해 가장 빠르기에 파이썬, 자바 등의 여러 프로그래밍 언어에서 표준 정렬 알고리즘으로 사용한다고 한다.

삽입 정렬은 그 시간복잡도가 O(N^2)으로 효율이 좋지 않은 알고리즘인데, 이를 합병 정렬과 결합하여 사용한 이유는 무엇일까?

참조 지역성 원리 (Locality of reference)

우리는 알고리즘의 성능을 파악하기 위해, 입력값의 크기 N에 따른 알고리즘 내에서 쓰이는 핵심 연산의 횟수를 계산하였다. 이를 함수로 f(N)이라 표현하겠다. 그러면 이를 토대로 시간복잡도 O(f(N))을 구했다. 그런데 실제 해당 알고리즘의 동작 시간은 T(N) = c * f(N)이다. 여기서 c는 컴퓨터의 CPU가 실제로 핵심 연산을 한 번 실행시키는데 걸리는 시간이다. 그런데 이 c에 영향을 끼치는 요소로 해당 알고리즘이 참조 지역성의 원리를 잘 만족시키느냐가 있다.

참조 지역성 원리는 프로그램이 일정 기간동안 전체 메모리들 중 특정 범위의 위치에 존재하는 메모리들에만 접근하는 경향을 의미한다. 즉, 제일 최근에 참조한 메모리와 그와 인접한 메모리가 다음에도 또 참조되는 경향을 말한다. 이를 이용하여 CPU에서는 제일 최근에 참조한 메모리와 그와 인접한 메모리를 캐시 메모리에 저장한다. 이로 인해 해당 메모리가 다음에 또 참조될 때 캐시 메모리에 있는 해당 메모리를 참조하게끔 하면 되기에 속도가 더 빨라진다. 비유를 들자면 캐시 메모리는 서점에서의 일종의 베스트 셀러 책들만 모아놓은 곳이라고 볼 수도 있겠다. 많은 사람들이 찾는 책들을 모아 “베스트 셀러” 항목에 몰아 넣으면 다음에 다른 손님들이 올 때에도 굳이 서점 전체를 찾지 않고서도 “베스트 셀러” 항목에 가기만 하면 원하는 책을 찾을 수 있으니 시간적으로 효율적이다. 하지만 만약 어떤 사람이 다른 사람들은 전혀 찾지 않는 책을 찾고자 한다면 “베스트 셀러” 항목에 해당 책이 없기에 그 사람은 최악의 경우 서점 전체를 둘러보아야 한다. 마찬가지로, 캐시 메모리에 저장되지 않은 데이터를 참조하려면 메인 메모리에서 해당 데이터를 일일이 찾아야 해서 시간이 더 걸린다.

참조 지역성 원리에 의하면, 어떤 배열이 존재하고 만약 인덱스 i번째 데이터를 참조했다면, CPU는 “다음에는 바로 다음 인덱스인 i+1번째 데이터를 참조하겠지?”라고 예측하여 해당 데이터를 캐시 메모리에 담는다. 그리고 실제로 해당 인덱스의 데이터를 참조하면 캐시 메모리에서 해당 데이터를 반환하면 된다. 그런데 만약 전혀 엉뚱한 인덱스를 참조하게 된다면, CPU는 메인 메모리에서 해당 위치의 메모리를 일일이 찾아야 해서 시간이 더 오래걸린다. 이러한 이유로, 메모리를 연속으로 읽는 작업은 그 작업 속도가 더 빠른 반면, 메모리를 계속 무작위 위치에서 읽어오면 해당 작업 속도는 느리다.

이러한 참조 지역성 원리에 비추어 앞서 살펴본 정렬 알고리즘들을 되돌아보면, 삽입 정렬은 시간복잡도 자체는 O(N^2)으로 비효율적이나, 바로 앞뒤에 위치한 데이터들만을 비교하고 이동시키기에 참조 지역성 원리 측면에서는 연산 한 번 할 때의 시간 (c) 자체는 그렇게 걸리지 않아 꽤 빠르다고 할 수 있다(c의 값이 작다). 반면, 힙 정렬의 경우, 힙 자료구조를 기반으로 정렬하는데, 부모 노드와 자식 노드를 배열에서 참조할 때 항상 기존 인덱스의 두 배에 위치한 인덱스를 참조하거나 그 반대로 두 배 작은 인덱스하고만 비교하기에 (즉, 이전 참조 위치와 다음 참조 위치간 간격이 너무 크기에) 참조 지역성 원리 측면에서 보면 연산 한 번 할 때의 시간 c는 매우 느리다고 볼 수 있다(c가 크다). 합병 정렬의 경우, 서로 인접하게 위치한 배열들에 대해서 비교 및 이동 연산을 실행하기에 참조 지역성의 원리를 잘 만족한다. 퀵 정렬도 마찬가지로 pivot 주변에서의 데이터 이동이 빈번하기에 해당 원리를 잘 만족한다.

이러한 점 때문에 삽입 정렬과 합병 정렬을 결합하여 Tim sort가 탄생하였다. 전체 배열을 2의 제곱수(\(2^x\))의 크기를 가지는 부분 배열로 나눈 후, 부분 배열마다 삽입 정렬을 실행하고 다시 병합시키면 더 빠르다는 아이디어에서 출발한 것이다.

부분 배열의 크기가 1이 될 때까지 분할하고 이를 다시 합병했던 합병 정렬과 달리 Tim sort에서는 부분 배열의 크기가 2의 제곱수가 될 때까지만 분할하기에 합병 정렬에 비해 분할 및 합병 작업이 좀 더 생략된다. 정확히는, 부분 배열의 크기가 \(2^x\)개가 될만큼만 자르면 x번 만큼의 합병 작업이 생략된다. 따라서 이 경우의 연산 횟수 f(N) = N(log(N)-x)가 되어 더 줄어든다. 이렇게 정렬 작업을 할 때 걸리는 시간을 최소로 줄이고자 한다면 x의 크기를 최대로 늘리면 된다. 즉, 이 말은 분할된 부분 배열의 크기를 할 수 있는 대로 최대화시켜야 한다는 뜻이다.

팀 정렬의 원리: 최적화하기

분할되는 부분 배열의 크기 x는 최대로!

전체 배열을 2^x (2의 제곱수) 개의 크기를 갖는 부분 배열들로 나눈다. 이를 위해서 먼저 처음 배열 왼쪽에 있는 2^x개의 요소들을 하나의 부분 배열로 묶는다. 그리고 그 부분 배열에 대해서 삽입 정렬을 실행시킨다. 그 후에는 부분 배열 바로 오른쪽에 있는 숫자가 정렬된 부분 배열의 최대값보다 더 크면 해당 숫자도 부분 배열에 바로 포함시킨다. 이 때는 이미 오름차순으로 정렬된 것이나 다름 없기에 따로 삽입 정렬을 추가적으로 실행하지 않는다. 이러한 과정을 반복하여 부분 배열의 크기를 최대한으로 늘린다.

다음의 숫자 배열들이 있다고 가정하겠다.

[10, 13, 9, 15, 18, 21, 13, 8, 5, 11, 3]

이 전체 배열을 크기가 2^2=4개인 부분 배열로 나누겠다. 먼저 맨 왼쪽에서부터 4개의 숫자들을 하나의 부분 배열로 묶는다. 그 후 해당 배열에 삽입 정렬을 통해 정렬시킨다. 이 때, 첫 두 숫자인 10과 13은 오름차순이므로 해당 부분 배열도 오름차순으로 정렬시킨다.

[(10, 13, 9, 15), 18, 21, 13, 8, 5, 11, 3]
[(9, 10, 13, 15), 18, 21, 13, 8, 5, 11, 3]

그 다음 원소를 보니, 이미 정렬된 부분 배열의 가장 오른쪽에 있고 가장 큰 수인 15보다 그 다음 원소인 18이 더 크다. 그리고 그 다음으로 21이라는 더 큰 수가 있다. 이 두 수인 18, 21을 부분 배열에 합쳐놓으면 따로 정렬 연산을 실행시키지 않더라도 이미 정렬된 부분 배열이 완성된다.

[(9, 10, 13, 15, 18, 21), 13, 8, 5, 11, 3]

그 다음 수인 13은 해당 부분 배열의 최대값인 21보다 작으므로 13은 부분 배열에 포함시킬 수 없다. 따라서 해당 부분 배열의 크기 확장은 여기서 멈추게 된다. 이제 그 다음 4개의 숫자들을 묶어 부분 배열로 만들고 삽입 정렬 작업을 실행시킨다. 이 때, 첫 두 요소인 13, 8은 내림차순이기에 해당 부분 배열은 내림차순으로 정렬시킨다.

[(9, 10, 13, 15, 18, 21), (13, 8, 5, 11), 3]
[(9, 10, 13, 15, 18, 21), (13, 11, 8, 5), 3]

두 번째 부분 배열의 가장 오른쪽에 있는 최소값인 5와 그 다음 요소인 3을 비교했을 때 3이 더 작은 수이므로 그대로 두 번째 부분 배열에 포함시키면 자연스레 크기를 더 늘리면서도 정렬 작업을 실행시키지 않아도 이미 정렬되어 있는 부분 배열을 만들 수 있다.

[(9, 10, 13, 15, 18, 21), (13, 11, 8, 5, 3)]

이후 내림차순의 부분 배열은 순서만 뒤집어 오름차순으로 만들면 된다.

이렇게, 처음 2^x개의 크기를 갖는 부분 배열을 minrun이라 하고, 위 예처럼 minrun에서 최대한 크기를 늘린 부분 배열을 run이라 부른다.

팀 정렬은 실제 현실 세계에서의 데이터들은 완전히 무작위로 배열되어 있지 않고 어느 정도는 오름차순 또는 내림차순으로 정렬되어 있을 것이라고 가정하기에 위와 같이 부분 배열의 크기를 늘리는 방법을 사용하는 것이다. 이러면 어느 정도는 정렬 연산을 생략해도 되기에 조금 더 효율적인 방법이라 할 수 있겠다.

보통, 팀 정렬에서 minrun의 크기는 2^5 ~ 2^6 개로 설정한다고 한다. 또는 전체 입력값의 크기 N이 2^5보다 작으면 N을 minrun의 크기로 설정한다. 사실 이 경우는 run이 1개 뿐이므로, 사실상 삽입 정렬만 실행하는 것과 다를바가 없긴 하다. minrun의 크기를 2^5=32개로 할지 2^6 = 64개로 할 지는 run의 개수가 2의 제곱수가 되도록 하는 minrun의 크기로 결정한다고 한다.

삽입 정렬은 이진 삽입 정렬(Binary insertion sort)로!

앞선 정렬 알고리즘 문서에서, 삽입 정렬은 이미 정렬된 부분 배열에 다음 숫자를 삽입할 때, 정렬된 부분 배열의 맨 뒤 숫자부터 차례대로 비교한 뒤 알맞은 위치에 삽입하는 과정을 거쳤다. 이러면 한 요소를 삽입하기 위해 O(n)의 시간복잡도를 가지고 비교를 거쳐야 한다. 이러한 순차탐색법 대신 이진 탐색법 (binary array search)을 이용하면 O(log n)이므로 더 빨리 정렬시킬 수 있다. 이 방법은 참조 지역성은 비교적 떨어지지만 시간복잡도에서의 우위를 이용하여 정렬 시간을 더 축약시킬 수 있다.

run들을 효율적으로 병합시키는 방법

합병 정렬에서는 안정성 유지를 이유로 가장 인접한 부분 배열들끼리 먼저 병합하였다. 그리고 병합될 두 부분 배열의 크기가 똑같을수록 최소한의 추가 메모리를 사용하여 효율성을 얻을 수 있다. (예를 들어, 두 부분 배열의 크기가 각각 5, 5인 경우와 2, 20인 경우 각각 필요한 추가 메모리는 10과 22일 것이다. 즉, 아무렇게나 두 부분 배열을 선택해서 합병하면 효율이 떨어진다는 뜻인 것 같다)

Tim sort에서는 앞서 보았듯, run마다의 길이가 제각기이다. 그래서 최소한의 추가 메모리 사용을 위해 최대한 비슷한 크기의 부분 배열들끼리 병합하도록 해야 한다.

그림 1. 서로 다른 크기를 가지는 run들이 스택에 쌓인 모습. 길게 묘사한 run이 그 크기가 가장 크다는 것을 의미한다. [2] 참조.

Tim sort에서는 하나의 run이 생성될 때마다 바로 스택에 담는다고 한다. (참고로 이 스택은 여러 run들을 하나로 병합할 용도의 스택이다) 이 때, 스택에 push되는 run들은 위 그림 1에서 묘사된 두 조건을 만족시켜야 한다.

1. 상대적으로 맨 아래에 있는 스택(C)의 크기는 바로 위에 오는 두 스택(A, B)의 길이의 합보다 더 커야 한다.
2. 상대적으로 아래에 있는 스택(B)은 그 위에 있는 스택 (A)보다 길이가 더 길어야 한다.

만약 위 조건을 만족시키지 않는다면, 두 조건을 만족시키게끔 두 run을 병합시킨다.

그림 2. 조건에 맞게끔 두 run을 병합하는 과정. [2] 참조.

그림 2를 예로 들면, 새로 들어온 A는 바로 아래에 있는 B보다 더 크다. (조건 2 위배) 따라서 B는 인접한 A, C 중 더 작은 C와 병합을 하여 두 조건을 만족시키도록 한다. 이러한 과정은 스택에 새로운 run들이 들어올 때마다 반복될 것이다.

이러한 조건을 만족시키도록 스택 내 run들을 병합시키면 두 가지 장점이 있다고 한다.

1. 총 입력값의 크기 N에 비해 스택에 들어있는 run의 개수를 작게 유지할 수 있다. 즉, run들을 병합시키기 위해 필요한 추가 스택의 용량이 상대적으로 그렇게 많이 필요하지 않다는 뜻이다.
2. 비슷한 크기의 run들끼리 병합할 수 있다. 이러면 최소한의 추가 메모리만을 이용하여 병합할 수 있기에 좀 더 효율적이라고 한다.

본격적인 run 합병

합병 정렬에서는 크기가 똑같은 두 부분 배열들끼리 병합하였으며, 병합과정에서 두 부분 배열의 크기만큼의 추가 메모리가 필요하였다. Tim sort에서의 병합 과정은 이와는 조금 다르다.

앞서 살펴보았듯, 보통 run들의 길이는 제각각일 것이다. 이 중 더 작은 길이의 run을 복사한다.

합병 전 원래 배열: [(3, 5, 8, 11, 13), (9, 10, 13, 15, 18, 21)]
run A: (3, 5, 8, 11, 13)
run B: (9, 10, 13, 15, 18, 21)

size(run A) > sizse(run B) => run B를 복사.

그 다음은 두 run을 하나로 병합시킨다. 합병 정렬에서 두 부분 배열을 하나로 합칠 때와 마찬가지로 두 run을 각각 스택으로 구성했을 때 스택에서 가장 앞에 있는 두 숫자들 중 가장 작은 수를 배열에 넣는 방식으로 합병시키는 것이다. 이 때, 합병 결과는 원래 배열에 추가한다.

stage 1)
원래 배열: [3, 5, 8, 11, 13, 9, 10, 13, 15, 18, 21]
run A: (3, 5, 8, 11, 13)
run B: (9, 10, 13, 15, 18, 21)
9 < 3 -> 3 삽입
원래 배열: [(3), 5, 8, 11, 13, 9, 10, 13, 15, 18, 21]
# 소괄호 안에 쓰인 숫자들은 두 run 중 한 곳에서
# 추출되고 삽입되어 이미 합병을 마친 숫자임을 표시
run A: (5, 8, 11, 13)
run B: (9, 10, 13, 15, 18, 21)

stage 2)
5 < 9 -> 5 삽입
원래 배열: [(3, 5), 8, 11, 13, 9, 10, 13, 15, 18, 21]
run A: (8, 11, 13)
run B: (9, 10, 13, 15, 18, 21)

stage 3)
8 < 9 -> 8 삽입
원래 배열: [(3, 5, 8), 11, 13, 9, 10, 13, 15, 18, 21]
run A: (11, 13)
run B: (9, 10, 13, 15, 18, 21)

# 이하 생략
최종 결과: (3, 5, 8, 9, 10, 11 ,13, 13, 15, 18, 21]

두 run 중 더 작은 run들을 복사하고 원래 배열에 왼쪽부터 차례대로 합병시키므로 아직 병합되지 않은 더 큰 run의 원소 일부가 다른 수로 덮어쓰일 일은 없다.

한 편, 두 run 중 더 작은 run의 크기를 복사하여 메모리를 추가로 사용하므로 최악의 경우 N/2의 추가 메모리를 사용한다. 공간복잡도로 표현하면 합병 정렬과 똑같이 O(N)이긴 하지만 이 방법이 합병 정렬보다 최대 절반의 메모리를 아낄 수 있다.

Galloping

방금 살펴본 두 run들의 합병 과정에서, run A의 앞에 있는 3개의 요소들이 run B의 맨 앞에 있는 요소 9보다 더 작았기에 run A에 있는 3개의 요소들이 연속으로 빠져나와 합병될 배열에 저장되었다. 이러한 상황에서, 두 run에 있는 요소들을 하나씩 대조하는 것보다는 한 run에서 여러 칸을 건너뛰며 비교하는 것이 더 효율적이지 않을까?

run A: [30, x, x, x, ..., x]
run B: [1, 2, 3, 5, 7, 9, 14, 28, 41, 60, 82]

위 예를 보면, 맨 처음 run A의 첫 번째 요소인 30과 run B의 첫 번째 요소인 1과 비교한다. 그 후 더 작은 숫자인 1이 합병된다. 그 후, run B에서는 그 다음 위치에 존재하는 숫자 2와 비교한다. 이렇게 한 번에 한 칸씩 대조하는 방식을 one pair at a time mode (”한 번에 한 쌍씩” 모드)라 한다. 위 예를 보면 알 수 있듯, 적어도 run B의 맨 앞의 3개의 요소들이 연속으로 병합될 것으로 보인다. 이 후로는 galloping mode(질주 모드)로 전환된다. galloping mode에서는 한 번에 한 칸씩만 비교하는 것이 아니라 1, 2, 4, 8, … , 2^k 칸씩 뛰어 넘으며 대소 비교를 진행한다.

run A: [30, x, x, x, ..., x]
run B: [(1, 2, 3), 5, 7, 9, 14, 28, 41, 60, 82]
run B index:       V  V      V               V

위 예에서는 galloping mode로 전환된 직후 시작되는 숫자 5부터 1칸, 2칸, 4칸, 8칸씩 건너뛰어 run A의 30과 대소 비교를 한다. 8칸을 건너뛴 곳에 82가 있고 이는 30보다 크다. 이 경우, [28, 41, 60, 82] 범위에서 이진 탐색법을 사용하여 이 중 30보다 작은 범위만을 포착한다. 그 후 30 이하 모든 숫자들을 한꺼번에 병합시키는 것이다. 이렇게 하면 계속 한 칸씩 뒤로 가면서 대소 비교를 하는 것보다 훨씬 더 효율적인 방식이다.

앞서 설명을 위해 galloping mode로 전환될 조건으로 “한 run에서만 3번 연속 병합시”라고 설정하였는데 그 횟수는 적절히 선택하면 된다. galloping mode로 전환되기 위해 필요한 한 run에서의 연속 병합 횟수를 임의로 설정한 후 병합을 실행시켰을 때 galloping mode로 전환되는 횟수가 빈번했다면 효율성을 위해 연속 병합 횟수를 감소시키고, 반대로 galloping mode로 전환되는 횟수가 별로 없다면 이는 그만큼 한 run의 가장 바깥에 있는 요소보다 작은 요소들이 반대편 run에 연속으로 존재하는 그 길이가 짧다는 뜻이므로, 연속 병합 횟수 조건을 증가시키면 더 효율적인 병합을 진행시킬 수 있다.

---

Reference

[1] George T. Heineman, “Learning Algorithms: A Programmer’s Guide to Writing Better Code”, (O’Reilly, 2021)

[2]

Tim sort에 대해 알아보자

[3]

[운영체제] 참조의 지역성(Locality of Reference)이란? 캐시의 지역성이란? 행렬 곱셈 최적화 방법

This content is licensed under CC BY-NC 4.0