퀵 정렬 : Pivot
이번 포스팅에서는 정렬의 종류 중 하나인 퀵 정렬에 대해서 알아보겠습니다.
대다수의 정렬이 구현된 언어, 프레임워크 등에서 자료구조를 정렬할 때 퀵 정렬 로직을 사용하고 있습니다.
어떠한 이유 때문에 이처럼 선호하는 것일까요?
지금부터 알아보도록 하겠습니다.
1. 퀵 정렬이란?
퀵 정렬 (Quick Sort)은 이름에서도 알 수 있듯이 지금까지 포스팅한 정렬 알고리즘 중 상대적으로 빠른 효율적 정렬 알고리즘입니다.
일반적인 평균 시나리오에서 효율적이며 최악의 시나리오라 할지라도 삽입 정렬, 선택 정렬 등과 유사한 시간 복잡도를 가지고 있습니다.
2. 핵심 개념 : 분할 (Partition)
퀵 정렬에서 배열을 분할 한다는 것은 배열에서 임의의 수 (pivot)을 선택한 후 pivot보다 작은 것은 왼쪽, 큰 것은 오른쪽으로 두는 것입니다.
본 포스트에서는 항상 배열의 오른쪽 끝 에 있는 값을 pivot으로 선택하겠습니다.
다음으로 두 개의 포인터를 사용해 하나는 배열 가장 왼쪽에 있는 값에, 다른 하나는 pivot을 제외한 가장 오른쪽 값에 할당합니다.
준비된 결과의 모습입니다.
이제 해당 도구들을 가지고 분할을 진행합니다.
- 왼쪽 포인터를 오른쪽으로 한 셀 씩 옮기며 pivot보다 크거나 같은 값에 도달하면 멈춥니다.
- 이어서 오른쪽 포인터를 왼쪽으로 한 셀씩 옮기며 pivot 보다 작거나 같은 값에 도달하면 멈춥니다.
- 오른쪽 포인터가 멈춘 경우
- 왼쪽 포인터가 오른쪽 포인터에 도달하거나 넘어선 경우 => 4로 이동
- 왼쪽 포인터가 오른쪽 포인터에 도달하지 못한 경우 => 왼쪽 포인터가 가리키는 값과 오른쪽 포인터가 가리키는 값을 교환 후 다시 1 ~ 3 진행
- 왼쪽 포인터가 가리키고 있는 값과 pivot을 교환합니다.
해당 단계를 마치면 pivot을 기준으로 왼쪽은 pivot보다 작은 값, 오른쪽은 pivot 보다 큰 값으로 나누어집니다.
이는 pivot이 정렬을 마친 최종 상태에서의 올바른 위치에 위치해 있음을 의미합니다.
코드로 구현해 보겠습니다.
class SortableArray {
arr = [];
constructor(arr) {
this.arr = arr;
}
partition(leftPointer, rightPointer) {
// 가장 오른쪽 위치를 Pivot으로 선정
const pivotIndex = rightPointer
// Pivot 값 저장
const pivot = this.arr[pivotIndex]
// Right pointer 선정
rightPointer -= 1
while (true) {
// Left pointer pivot보다 크거나 같은 값 찾으며 이동
while (this.arr[leftPointer] < pivot) {
leftPointer += 1
}
// Right pointer pivot보다 작거나 같은 값 찾으며 이동
while (pivot < this.arr[rightPointer]) {
rightPointer -= 1
}
// 만일 Left pointer가 Right pointer에 도달하거나 넘은 경우 Pivot 교환 단계로
if (rightPointer <= leftPointer) {
break;
} else {
// 아직 Left pointer가 Right pointer에 도달 하지 못한경우 양쪽 값 교환 후 다시 처음으로
const temp = this.arr[leftPointer]
this.arr[leftPointer] = this.arr[rightPointer]
this.arr[rightPointer] = temp
// 다음 셀부터 탐색 위해 한 셀 이동
leftPointer += 1
}
}
// Pivot과 Left pointer 위치 값 교환
const leftTemp = this.arr[leftPointer]
this.arr[leftPointer] = this.arr[pivotIndex]
this.arr[pivotIndex] = leftTemp
// 현재 Pivot 위치 반환
return leftPointer
}
}
이제 pivot을 기준으로 왼쪽 배열과 오른쪽 배열을 나누고 각각 하위 배열들에서 위의 절차를 반복하여 pivot을 찾고 분할하는 단계를 원소가 1개 혹은 0개 남는 배열이 될 때까지 재귀 호출합니다.
// ... 생략 ....
quickSort(leftIndex, rightIndex) {
// 배열 내 원소 갯수가 1개 또는 0개인 경우 ( 기저 조건 )
if (rightIndex - leftIndex <= 0) return
// 분할
let pivotIndex = this.partition(leftIndex, rightIndex)
// 왼쪽 재귀 호출
this.quickSort(leftIndex, pivotIndex - 1)
// 오른쪽 재귀 호출
this.quickSort(pivotIndex + 1, rightIndex)
}
3. 퀵 정렬의 시간 복잡도
배열을 한 번 분할 할때마다
- 비교 : 각원소를 pivot과 비교 => $ N $ 단계
- 교환 : 평균 - $ N/4 $ 단계, 최대 - $ N/2 $단계
- 시간 복잡도 : $ O(N + N/4) $
배열 분할 횟수
- ex) 크기가 8인 배열 은 각 원소로 나뉠 때까지 반으로 나누는 횟수가 3번입니다.
- $ O(logN) $
총 시간 복잡도 : $ O(NlogN) $
4. 퀵 정렬의 상황별 효율성
- 최선의 시나리오 : Pivot이 하위 배열의 가운데에 위치하는 경우
- 최악의 시나리오 : Pivot이 하위 배열의 한쪽 끝에 위치하는 경우 ( 오름차순 or 내림차순 )=> 이 경우 Pivot이 매 재귀 호출마다 하위 배열에 끝에 위치하게 되고 교환은 1회 지만 비교가 많이 일어난다. 시간 복잡도 : $ O(N^2) $
4. 퀵 셀렉트
무작위로 정렬된 배열에서 랭크를 매기고 특정 랭크에 해당하는 원소를 가져와야 할 때가 있다.
우선 정렬을 한 후 인덱스로 접근하는 방법이 존재하지만 퀵 셀렉트 (Quick select)라는 더 나은 방법이 있다.
퀵 셀렉트 또한 퀵정렬과 같이 분할에 기반하며 퀵 정렬과 이진 검색의 하이브리드라 할 수 있다.
ex ) 길이가 8인 배열에서 두 번째로 작은 값을 찾는 경우
퀵 정렬의 분할과 동일하게 진행하는데 하위 배열로 분할을 진행하며 찾고자 하는 랭크와 피벗의 인덱스를 비교하며 재귀 호출할 하위 배열을 선택한다.
// 생략
quickSelect(nthLowestValue, leftIndex, rightIndex) {
if (rightIndex - leftIndex <= 0) return this.arr[leftIndex]
let pivotIndex = this.partition(leftIndex, rightIndex)
// 값이 Pivot의 오른쪽에 있는 경우
if (pivotIndex < nthLowestValue) {
this.quickSelect(nthLowestValue, pivotIndex + 1, rightIndex)
}
// 값이 Pivot의 왼쪽에 있는 경우
else if (pivotIndex > nthLowestValue) {
this.quickSelect(nthLowestValue, leftIndex, pivotIndex - 1)
}
// 값이 Pivot 과 동일한 경우
else {
return this.arr[pivotIndex]
}
}