자바로 배우는 핵심 자료구조와 알고리즘: 기술 면접에 필요한 실용주의 자료구조와 알고리즘

172

자바로 배우는 핵심 자료구조와 알고리즘

따라서 내부 반복문의 총 실행 횟수는

1

,

2

, … ,

n

-

1

수열의 합인

n

(

n

-

1

)/

2

가 되고, 이 식의

최대 차수는

n

2

이 됩니다.

최악일 때 삽입 정렬은 이차지만, 다음과 같은 특징이 있습니다.

1

. 요소가 이미 정렬되어 있거나 거의 정렬되어 있으면 삽입 정렬은 선형입니다. 특히 각 요

소가 있어야 하는 자리 기준

k

이하의 위치에 있다면 내부 반복문은

k

번 이하로 동작하게

되고 전체 실행시간은

O

(

kn

)이 됩니다.

2

. 구현이 단순하므로 오버헤드

overhead

가 작습니다. 즉, 실행시간은

an

2

이지만 최대 차수의

계수인

a

는 아마도 작을 것입니다.

따라서 배열이 거의 정렬되어 있거나 별로 크지 않다면 삽입 정렬은 좋은 선택이 됩니다. 하지

만 큰 배열에서는 더 좋은 방법들이 있습니다. 사실은 훨씬 더 좋은 방법입니다.

17.2

실습

14

병합 정렬은 실행시간이 이차보다 좋은 알고리즘의 하나입니다. 여기에서도 알고리즘 자체를

설명하기보다

http

://

thinkdast

.

com

/

mergesort

문서를 읽어보기 바랍니다. 어떤 내용인지

알게 되면 돌아와서 실제로 구현해 보면서 이해한 내용을 확인해 보기 바랍니다.

이 책의 코드 저장소에는 실습을 위한 다음 소스 파일이 있습니다.

●

ListSorter ...