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

169

5

장

정렬

5.7

퀵 정렬

병합 정렬 외에 분할 정복을 따르는 정렬 알고리즘으로

퀵 정렬

Quicksort

7

이 있다. 퀵 정렬은 지금

까지 설계된 알고리즘 중 가장 효율적이고 많이 연구되었다.

A

에서

피벗

pivot

값

p

로 사용할 요

소를 선택해 재귀적으로 정렬한 다음

p

를 정렬된 최종 배열 내 적절한 위치에 삽입한다. 이를

수행하기 위해

A

[

lo

..

hi

]

의 내용을

p

값을 기준으로 재배열한다 (

p

보다 작으면 왼쪽 하위

배열로,

p

보다 크면 오른쪽 하위 배열로). [그림

5

-

11

]을 보면 분할된 배열은 이러한 기준으

로 배열되어 있다.

그림

5-11

A

[

0

]

을 피벗으로 사용해

partition

(

A

,

0

,

7

,

0

)

을 호출한 결과

전체 배열의 정렬 결과를 알지 못한 채,

p

가 최종 정렬된 배열에서 어디에 위치할지 어떻

게 알까? 분할

partitioning

은

A

의 모든 요소를 정렬하지 않고

p

를 기반으로 일부만 재정렬한다.

partition

()

의 구현은

1

장 연습 문제를 참조하자. [그림

5

-

11

]에서

partition

()

이 완료된

후, 정렬할 왼쪽 하위 배열은 값이

2

개인 반면 오른쪽 하위 배열은

5

개다. 각 하위 배열은 퀵

정렬을 통해 재귀적으로 정렬된다 (코드

5

-

8

).

7

퀵 정렬은

1959

년에 토니 호어

Tony

Hoare

가 고안한 것으로, ...