퀵 정렬(quick sort)

<퀵 정렬(quick sort)>

분할 정렬 방법이며, 정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다.
왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.

 

기준 값 : 피봇(pivot)이란?
일반적으로 전체의 원소 중에서 가운데에 위치한 하나의 원소를 골라서 선택 

 

퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성한다.
1. 분할(divide)
정렬할 자료들을 기준값을 중심으로 2개의 부분 집합으로 분할하기
2. 정복(conquer)
부분 집합의 원소들 중에서 기준값보다 작은 원소들은 왼쪽 부분 집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬하기.
부분 집합의 크기가 1 이하로 충분히 작지 않으면 순환호출을 이용하여 다시 분할.

 

[퀵 정렬 수행 방법]
- 부분 집합으로 분할하기 위해서 L과 R을 사용
① 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇 보다 크거나 같은 원소를 찾아 L로 표시
② 오른쪽 끝에서 왼쪽으로 움직이면서 피봇 보다 작은 원소를 찾아 R로 표시
③ L이 가리키는 원소와 R이 가리키는 원소를 서로 교환한다.
- L와 R이 만나게 되면 피봇과 R의 원소를 서로 교환하고, 교환한 위치를 피봇의 위치로 확정한다.
- 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분 집합과 오른쪽 부분 집합에 대해서 퀵 정렬을 순환적으로 반복 수행하는데 모든 부분 집합의 크기가 1 이하가 되면 퀵 정렬을 종료한다.

 

[퀵 정렬 수행 과정]
정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 퀵 정렬 방법으로 정렬하는 과정을 살펴보자. 

 

원소의 개수가 8개이므로 네 번째 자리에 있는 원소 2를 첫 번째 피봇으로 선택하고 퀵 정렬 시작.

① 원소 2를 피봇으로 선택하고 퀵 정렬 시작.

L이 오른쪽으로 이동하면서 피봇 보다 크거나 같은 원소를 찾고, R은 왼쪽으로 이동하면서 피봇 보다 작은 원소를 찾는다.
L은 원소 69를 찾았지만, R은 피봇 보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 된다.
L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 2의 위치를 확정한다.

② 피봇 2의 왼쪽 부분 집합은 공집합이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행.
오른쪽 부분 집합의 원소가 7개 이므로 가운데 있는 원소 16을 피봇으로 선택.

L이 찾은 30과 R이 찾은 8을 서로 교환한다.

현재 위치에서 L과 R의 작업을 반복한다.
L은 원소 69를 찾았지만, R은 피봇 보다 작은 원소를 찾지 못한 채로 원소 69에서 L과 만나게 된다. L과 R이 만났으므로, 원소 69를 피봇과 교환하여 피봇 원소 16의 위치를 확정한다.

③ 이런식으로 반복수행한다.

 

④ 피봇 30의 확정된 위치에서의 왼쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않고, 오른쪽 부분 집합에 대해서 퀵 정렬 수행.
오른쪽 부분 집합의 원소 2개 중에서 원소 31을 피봇으로 선택한다.

L은 오른쪽으로 이동하면서 원소 31을 찾고, R은 왼쪽으로 이동하면서 피봇 보다 작은 원소를 찾다가 못 찾은 채로 원소 31에서 L과 만난다.
L과 R이 만났으므로 피봇과 교환하는데 R의 원소가 피봇이므로 결국 제자리가 확정된다.

피봇 31의 오른쪽 부분 집합의 원소가 한 개 이므로 퀵 정렬을 수행하지 않는다. 이것으로써 전체 퀵 정렬이 모두 완성되었다.

 

퀵 정렬을 분석해보자.

[메모리 사용공간]
n개의 원소에 대하여 n개의 메모리 사용 

 

[연산 시간]
1. 최선의 경우
- 피봇에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우
2. 최악의 경우
- 피봇에 의해 원소들을 분할하였을 때 1개와 n-1개로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우

평균 시간 복잡도 : O(n log2n)

같은 시간 복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 더 빨리 실행되어 실행 시간 성능이 좋은 정렬 방법임.

 

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)