똑똑한 코드 작성을 위한 실전 알고리즘

178

똑똑한 코드 작성을 위한 실전 알고리즘

5.10

팀 정렬

팀 정렬은 삽입 정렬과 병합 정렬에서 사용하는

merge

()

헬퍼 함수를 결합한 알고리즘으로,

실제 데이터 정렬에서 다른 알고리즘의 성능을 능가한다. 특히 부분적으로 정렬된 긴 일련의

데이터를 활용해 성능을 극대화한다.

[코드

5

-

10

]를 보면 팀 정렬은 먼저

compute

_

min

_

run

()

에서 계산된

size

를 사용해

N

/

size

개의 하위 배열을 부분적으로 정렬한다.

size

는 일반적으로

32

와

64

사이 정수다. 이 숫자는

N

과 무관한 상수로 다뤄진다. 이 단계는 부분적으로 정렬된 일련의 데이터가 있는지 확인해, 정

렬된 하위 배열 두 개를 하나로 합치는 병합 정렬에서 가져온 헬퍼 함수인

merge

()

의 성능을

향상한다.

코드

5-10

기본 팀 정렬 구현

def tim_sort(A):

N = len(A)

➊

if N < 64:

insertion_sort(A,0,N-1)

return

size = compute_min_run(N)

➋

for lo in range(0, N, size):

➌

insertion_sort(A, lo, min(lo+size-1, N-1))

aux = [None]*N

➍

while size < N:

for lo in range(0, N, 2*size):

mid = min(lo ...