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

149

5

장

정렬

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

●

비교 기반 정렬 알고리즘은 다음 두 가지 기본 연산을 요구한다.

-

less(i, j)

는

A[i] < A[j]

인지 판단한다.

-

swap(i, j)

는

A[i]

와

A[j]

의 내용을 교환한다.

●

정렬할 때 비교기를 제공하는 방법

1

●

코드의 구조에서 삽입 정렬 및 선택 정렬과 같이 비효율적인

O

(

N

2

) 정렬 알고리즘을 식별하는

방법

●

자기 자신을 호출하는 재귀 함수. 이 기본적인 컴퓨터 과학 개념은 문제 해결을 위한 분할 정복

전략의 기초를 구성한다.

●

병합 정렬과 퀵 정렬이 분할 정복을 사용해

O

(

N

log

N

)의 성능으로 요소가

N

개인 배열을 정렬

하는 방법. 힙 정렬도

O

(

N

log

N

)을 보장하는 방법

●

팀 정렬이 삽입 정렬과 병합 정렬의 기능을 결합해,

O

(

N

log

N

) 성능을 보장하는 파이썬의 기

본 정렬 알고리즘을 구현하는 방법

이 장에서는 배열의

N

개 요소를 오름차순으로 재배열하는 알고리즘을 소개한다. 값의 컬렉션

을 정렬된 순서로 구성하는 작업은 프로그램의 효율성을 향상하는 데 필수다. 또한 정렬은 여

1

예를 들면 정수나 문자열을 내림차순으로 정렬하거나, 기본 순서가 없는

2

차원 (

x

,

y

) 좌표 모음을 정렬하는 데 사용한다.

정렬

CHAPTER

5