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

154

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

그림

5-3

삼각수 공식 시각화:

1

부터

7

까지의 합은

28

이다.

5.3

성능이

O

(

N

2

)인 정렬 알고리즘의 구조

선택 정렬을 분석해보면 비교 횟수의 최고차항이

N

2

이며, 이는 성능이

O

(

N

2

)이라는 의미다.

N

개 값을 정렬할 때

N

-

1

회의 개별 단계가 어떻게 수행되는지 살펴보며 그 이유를 알아보자.

첫 단계에서

N

-

1

회 비교를 통해 가장 작은 값을 찾고 단 하나의 값만 알맞은 위치로 이동한다.

이후

N

-

2

개의 단계 각각은 마지막 단계에서 더 이상 작업이 없을 때까지 하나씩 (아주 천천

히) 감소한다. 비교 횟수를 줄일 수 있을까?

삽입 정렬

Insertion

Sort

은 선택 정렬 (마찬가지로

N

-

1

개의 개별 단계를 사용해 배열을 왼쪽에서 오

른쪽으로 정렬)과는 다른 알고리즘이다.

A

[

0

]

가 알맞은 위치에 있다고 가정하고 시작한다(배

열에서 가장 작은 값일 수 있다 ). 삽입 정렬의 첫 번째 단계에서

A

[

1

]

이

A

[

0

]

보다 작은 값이면

오름차순 정렬이 필요하므로 두 값을 교환한다. 두 번째 단계에서는

A

[

2

]

의 값을 처음

3

개 값

만 고려해 알맞은 위치로 삽입하려고 시도한다. 여기에는 세 가지 가능성이 존재한다.

A

[

2

]

가

알맞은 위치이거나,

A

[

0

]

와

A

[

1

]

사이에 삽입해야 하거나,

A

[

0

]

앞에 삽입해야 ...