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

151

5

장

정렬

교환 횟수도 중요하지만 두 값 간의 비교 횟수도 계산해야 한다. 먼저,

1

장에서 본 것과 같이

7

회 비교만으로

2

가 배열

A

에서 가장 작은 값임을 알 수 있다. 가장 작은 값은

A

[

3

]

에 있으니

A

[

0

]

과 교환한다. 가장 작은 값을 배열의 맨 앞으로 이동하는 것이다. [그림

5

-

1

]에는 교환되

는 값들을 음영 처리하고, 최종 위치에 놓인 값은 굵은 테두리로 표시했다. 굵은 테두리 안의

값은 더는 교환되지 않으며 외부의 값들은 아직 정렬되지 않았다.

가장 큰 값

24

를 찾기 위해 남은 값들을 조사하고 (

6

회 비교 )

A

[

5

]

와

A

[

7

]

을 교환해 가장 큰

값을 배열의 맨 마지막으로 이동시켰다. 남은 값 중에 가장 작은 값

5

를 찾았고 (

5

회 비교 )

A

[

1

]

과

A

[

6

]

을 교환해

5

를 알맞은 위치로 이동시켰다.

21

이 알맞은 위치에 있음을 검증하기

위해

4

회 비교했으며, 이 시점에 교환은 일어나지 않았다.

3

회 비교 후 남은 값 중에

15

가 제일 작았고, 두 번째

15

를 선택해

A

[

4

]

와

A

[

2

]

를 교환했다.

2

회 비교로

15

는 인덱스 위치

3

임을 검증했으므로, 추가

1

회 비교로

A

[

4

]

와

A

[

5

]

를 교환해

19

를 알맞은 위치로 이동시켰다. [그림

5

-

1

]에 그려진 마지막 단계에서 값

20

왼쪽에 있는 값은

모두

20

보다 작거나 같고,