CHAPTER 6. 정렬 - 퀵 정렬

3. 퀵 정렬

기준을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

 

정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘이다. 책 에서는 다루지 않지만 퀵 정렬만큼 빠른 알고리즘으로 병합 정렬이 있다. 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다.

 

 

특징

• 큰 숫자와 작은 숫자를 교환할때, 교환하기 위한 기준을 피벗(Pivot)이라고 한다.
• 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야한다.
• 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분한다.

여기서는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 설명한다.

 

동작 예시 - 호어 분할 방식

• 규칙: 리스트에서 첫 번째 데이터를 피벗으로 정한다.

위의 규칙에 따라 피벗을 설정한 뒤, 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 피벗에 대해 정렬이 수행된다.

 

초기 데이터: 5 7 9 0 3 1 6 2 4 8

퀵 정렬은 전체 과정을 3개 파트로 나눠보는 것이 편하므로 Ⅰ,Ⅱ,Ⅲ 파트로 설정한다.

 

Ⅰ 파트 - 분할

[step 1] 리스트의 첫 번재 데이터를 피벗으로 설정하므로 피벗은 '5'다. 이후에 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

 

5 7 9 0 3 1 6 2 4 8

5 4 9 0 3 1 6 2 7 8

 

[step 2] 다시 피벗보다 큰 데이터와 작은 데이터를 찾고 두 값의 위치를 서로 변경한다. 현재 '9'와 '2'가 선택되었으므로 이 두 데이터의 위치를 서로 변경한다.

5 4 9 0 3 1 6 2 7 8

5 4 2 0 3 1 6 9 7 8

 

[step 3] 다시 피벗보다 큰 데이터와 작은 데이터를 찾으면 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린다는 것을 알 수 있다. 이렇게 두 값이 엇갈린 경우 '작은 데이터'와 '피벗'의 위치를 서로 변경한다. 즉, 작은 데이터인 '1'과 피벗인 '5'의 위치를 서로 변경하여 분할을 수행한다.

5 4 2 0 3 1 6 9 7 8

 

[step 4] 분할 완료 이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보면, 피벗인 '5'의 왼쪽에 있는 데이터는 모두 피벗보다 작고 오른쪽에 있는 데이터는 모두 피벗보다 크다. 이러한 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

1 4 2 0 3 5 6 9 7 8

 

이 상태에서 왼쪽 리스트와 오른쪽 리스트 개별적으로 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대해 모두 정렬이 이루어질 것이다.

 

Ⅱ 파트 - 왼쪽 리스트 정렬

왼쪽 리스트에서는 다음과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

1 4 2 0 3

1 0 2 4 3

0 1 2 4 3

0 1 2 3 4

 

Ⅲ 파트 - 오른쪽 리스트 정렬

오른쪽 리스트에서는 다음과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

6 9 7 8

6 7 9 8

6 7 8 9

 

퀵 정렬은 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에, 피벗을 기준으로 왼쪽리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. 이는 재귀 함수와 동작 원리가 같다. 실제로 퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다. 재귀 함수와 동작 원리가 같다면, 종료 조건이 있어야한다는 것을 알 수 있다. 퀵 정렬의 종료 조건은 바로 현재 리스트의 데이터 개수가 1개인 경우이다. 리스트의 원소가 1개라면, 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능하다.

 

시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 최선의 경우에 피벗 값의 위치가 변경되어 분할될 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다면 도식화 했을 때, 데이터 개수 = N  높이 = logN 이라고 할 수 있다. (일반적으로 컴퓨터 과학에서 log는 밑이 2인 log를 의미한다.) 즉, N = 1,000일 때 log₂N ≈ 10 으로 상대적으로 매우 작은 수임을 이해할 수 있다.

이는 데이터 개수가 많을수록 차이가 극명하게 드러나기때문에 데이터 개수가 많을수록 퀵 정렬은 선택 정렬, 삽입 정렬에 비해 압도적으로 빠르게 동작할 거라고 추측할 수 있다.

 

* 아래의 표는 평균 시간 복잡도를 기준으로 각 정렬 알고리즘이 데이터의 개수에 따라 얼마나 많은 연산을 요구하는지를 나타낸 것이다. 엄밀한 연산 횟수 비교는 아니다.

데이터 개수(N)	N²(선택 정렬, 삽입 정렬)	Nlog₂N(퀵 정렬)
N = 1,000	≈ 1,000,000	≈ 10,000
N = 1,000,000	≈ 1,000,000,000,000	≈ 20,000,000

 

하지만 퀵 정렬은 최악의 경우 시간 복잡도가 O(N²)이다. 데이터가 무작위로 입력될 때 퀵 정렬은 빠르게 동작할 확률이 높지만 위의 예시처럼 가장 왼쪽 데이터를 피벗으로 정할 때는 이미 데이터가 정렬되어 있다면 매우 느리게 동작한다.( 정렬되어 있을 때 매우 빠르게 동작하는 퀵 정렬과는 반대이다.)

 

 

Big-O Notation: Worst, Avg-O(N²) / Best-O(N)

 

---

 

 

Q. 라이브러리에서 제공하는 퀵 정렬은 O(NlogN)을 보장하는가?

C++와 같이 퀵 정렬 기반 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 시간 복잡도 O(NlogN)을 보장할 수 있도록 피벗 값을 설정할 때 추가적인 로직을 더해준다. 파이썬 또한 마찬가지로 기본 정렬 라이브러리를 이용하면 O(NlogN)를 보장해준다.