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

181

5

장

정렬

이 장에서 배운 내용은 다음과 같다.

●

성능이

O

(

N

2

)인 일부 기본 정렬 알고리즘은 대규모 데이터 세트를 정렬하는 데 부적합하다.

●

재귀 개념은 문제를 더 작은 하위 문제로 나누어 해결하는 핵심 전략이다.

●

병합 정렬과 힙 정렬은 서로 다른 방식으로

O

(

N

log

N

) 성능을 달성한다.

●

퀵 정렬은 병합 정렬에 필요한 추가 저장 공간 없이도

O

(

N

log

N

) 성능을 달성한다.

●

팀 정렬은 파이썬에서 사용하는 기본 정렬 알고리즘으로, 다른 프로그래밍 언어에서도 점차 도입하고

있다.

5.12

연습 문제

1.

A

에서 값

t

가 나타나는 횟수를 반환하는 재귀 함수

count

(

A

,

t

)

를 작성하자.

find

_

max

(

A

)

와 비슷한 재귀적 구조로 구현해야 한다.

2.

0

에서

N

-

1

까지 고유한 정수

N

개의 순열을 포함하는 배열이 주어졌을 때 값을 오름차순으

로 정렬하는 데 필요한 최소 교환 횟수를 구하자. 그리고 이러한 배열을 입력으로 받아 정

숫값을 반환하는

num

_

swaps

(

A

)

함수를 작성하자. 배열을 실제로 정렬할 필요는 없고 정렬

에 필요한 교환 횟수만 구하면 된다.

고유한 값

N

개를 가지는 배열로 동작하는 문제를

3

장의 심볼 테이블을 사용해 확장하고,

[그림

5

-

1

]에

5

회의 교환이 필요함을 확인해보자.

3.

값이

N

개인 정렬되지 않은 배열에서 가장 큰 값을 찾는 재귀 함수인

find

_

max

(

A

)

에서 필

요한 총 비교 횟수는 얼마인가? 이 횟수는

1

장에서 본

largest

(

A

)

를 사용해 비교한 횟수

와 비교해 더 작은지 (혹은 ...