Quick Sort란?
이름에서도 보이듯이 빠른(Quick) 정렬이다.
퀵 정렬의 메커니즘은 크게 다음과 같다.
하나의 리스트를 pivot(피벗)을 기준으로 두 개의 부분리스트로 나누어 하나는 pivot보다 작은 값들의 부분리스트, 다른 하나는 pivot보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위처럼 재귀적으로 수행하여 정렬하는 방법이다.
알고리즘의 '분할 정복(Divide and Conquer)'을 기반으로 정렬되는 방식이다.
다만, Merge Sort(병합 정렬)과 다른 점은 병합정렬의 경우 하나의 리스트를 절반으로 나누어 분할 정복을 하고, Quick Sort(퀵 정렬)의 경우 pivot(피벗)의 값에 따라 pivot보다 작은 값을 갖는 부분리스트와 pivot보다 큰 값을 갖는 부분리스트의 크기가 다를 수 있기 때문에 하나의 리스트에 대해 비균등하게 나뉜다는 점이 있다.
실제로 정렬 방법에서 Merge Sort(병합 정렬)과 Quick Sort(퀵 정렬)은 많이 비교된다. (일반적으로 병합정렬이 퀵 정렬보다 빠르다.)
Quick Sort(퀵 정렬)은 데이터를 비교하면서 찾기 때문에 비교 정렬이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 그러므로 제자리 정렬(in-place sort)이다.
또한, Merge Sort(병합 정렬)과는 다르게 하나의 pivot을 두고 두 개의 부분리스트를 만들 때 서로 떨어진 원소끼리 교환이 일어나기 때문에 불안정정렬(Unstable Sort) 알고리즘이기도 하다.
Process(Ascending)
- 피벗을 하나 선택한다.
- 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.
- 양 방향에서 찾은 두 원소를 교환한다.
- 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때까지 2번으로 돌아가 위 과정을 반복한다.
- 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때까지 1번 과정을 반복한다. (Divide : 분할)
- 인접한 부분리스트끼리 합친다. (Conqure : 정복)
위 6가지 과정에 의해 정렬되는 방식이다.
2~3번 과정의 경우 좀 더 구체적으로 말하자면 대부분의 구현은 현재 리스트의 양 끝에서 시작하여 왼쪽에서는 피벗보다 큰 값을 찾고, 오른쪽에서는 피벗보다 작은 값을 찾아 두 원소를 교환하는 방식이다. 그래야 피벗보다 작은 값은 왼쪽 부분에, 피벗보다 큰 값들은 오른쪽 부분에 치우치게 만들 수 있기 때문이다. 이를 흔히 호어(Hoare)방식이라고 한다.
피벗을 선택하는 과정은 여러 방법이 있는데, 대표적으로 세 가지가 있다.
현재 부분배열의 가장 왼쪽 원소가 피벗이 되는 방법, 중간 원소가 피벗이 되는 방법, 마지막 원소가 피벗이 되는 방법이다.
그림으로 보는 왼쪽 피벗 선택 방식
오른쪽 피벗 선택 방식
중간 피벗 선택 방식
위 3 가지 방식 모두 특징은 '피벗'을 하나 설정하고 피벗보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 치중하도록 하는 것이다. 이 과정을 흔히 파티셔닝(Partitioning)이라고 한다.
그렇게 파티셔닝을 했다면 파티셔닝을 통해 배치된 피벗의 위치를 기준으로 좌우 부분리스트로 나누어 각각의 리스트에 대해 재귀 호출을 해주면 된다.
GIF로 이해하는 Quick Sort
Code
왼쪽 피벗 선택 방식
public class QuickSort {
public static void sort(int[] a) {
l_pivot_sort(a, 0, a.length - 1);
}
/**
* 왼쪽 피벗 선택 방식
* @param a 정렬할 배열
* @param lo 현재 부분배열의 왼쪽
* @param hi 현재 부분배열의 오른쪽
*/
private static void l_pivot_sort(int[] a, int lo, int hi) {
/*
* lo가 hi보다 크거나 같다면 정렬 할 원소가
* 1개 이하이므로 정렬하지 않고 return한다.
*/
if(lo >= hi) {
return;
}
/*
* 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬 된 상태로
* 만들어 준 뒤, 최종적으로 pivot의 위치를 얻는다.
*
* 그리고나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분리스트로 나누어
* 분할 정복을 해준다.
*
* [과정]
*
* Partitioning:
*
* a[left] left part right part
* +---------------------------------------------------------+
* | pivot | element <= pivot | element > pivot |
* +---------------------------------------------------------+
*
*
* result After Partitioning:
*
* left part a[lo] right part
* +---------------------------------------------------------+
* | element <= pivot | pivot | element > pivot |
* +---------------------------------------------------------+
*
*
* result : pivot = lo
*
*
* Recursion:
*
* l_pivot_sort(a, lo, pivot - 1) l_pivot_sort(a, pivot + 1, hi)
*
* left part right part
* +-----------------------+ +-----------------------+
* | element <= pivot | pivot | element > pivot |
* +-----------------------+ +-----------------------+
* lo pivot - 1 pivot + 1 hi
*
*/
int pivot = partition(a, lo, hi);
l_pivot_sort(a, lo, pivot - 1);
l_pivot_sort(a, pivot + 1, hi);
}
/**
* pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
*
* @param a 정렬 할 배열
* @param left 현재 배열의 가장 왼쪽 부분
* @param right 현재 배열의 가장 오른쪽 부분
* @return 최종적으로 위치한 피벗의 위치(lo)를 반환
*/
private static int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[left]; // 부분리스트의 왼쪽 요소를 피벗으로 설정
// lo가 hi보다 작을 때 까지만 반복한다.
while(lo < hi) {
/*
* hi가 lo보다 크면서, hi의 요소가 pivot보다 작거나 같은 원소를
* 찾을 떄 까지 hi를 감소시킨다.
*/
while(a[hi] > pivot && lo < hi) {
hi--;
}
/*
* hi가 lo보다 크면서, lo의 요소가 pivot보다 큰 원소를
* 찾을 떄 까지 lo를 증가시킨다.
*/
while(a[lo] <= pivot && lo < hi) {
lo++;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
swap(a, lo, hi);
}
/*
* 마지막으로 맨 처음 pivot으로 설정했던 위치(a[left])의 원소와
* lo가 가리키는 원소를 바꾼다.
*/
swap(a, left, lo);
// 두 요소가 교환되었다면 피벗이었던 요소는 lo에 위치하므로 lo를 반환한다.
return lo;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
위와 같이 왼쪽 피벗을 선택해서 피벗보다 작은 요소들은 왼쪽에, 피벗보다 큰 요소들은 오른쪽에 치중시킨 뒤, 피벗의 위치를 최종적으로 들어갈 위치와 교환해준 뒤 그 위치를 반환하는 메서드가 partition메서드고, 반환된 피벗의 위치를 기준으로 왼쪽과 오른쪽 부분리스트로 나누어 재귀적으로 분할 정복을 해주는 것이다.
오른쪽 피벗 선택 방식
(왼쪽 피벗 선택 방식에서 역순으로 해주면 된다.)
public class QuickSort {
public static void sort(int[] a) {
r_pivot_sort(a, 0, a.length - 1);
}
/**
* 오른쪽 피벗 선택 방식
* @param a 정렬할 배열
* @param lo 현재 부분배열의 왼쪽
* @param hi 현재 부분배열의 오른쪽
*/
private static void r_pivot_sort(int[] a, int lo, int hi) {
/*
* lo가 hi보다 크거나 같다면 정렬 할 원소가
* 1개 이하이므로 정렬하지 않고 return한다.
*/
if(lo >= hi) {
return;
}
/*
* 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬 된 상태로
* 만들어 준 뒤, 최종적으로 pivot의 위치를 얻는다.
*
* 그리고나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분리스트로 나누어
* 분할 정복을 해준다.
*
* [과정]
*
* Partitioning:
*
* left part right part a[right]
* +---------------------------------------------------------+
* | element < pivot | element >= pivot | pivot |
* +---------------------------------------------------------+
*
*
* result After Partitioning:
*
* left part a[hi] right part
* +---------------------------------------------------------+
* | element < pivot | pivot | element >= pivot |
* +---------------------------------------------------------+
*
*
* result : pivot = hi
*
*
* Recursion:
*
* r_pivot_sort(a, lo, pivot - 1) r_pivot_sort(a, pivot + 1, hi)
*
* left part right part
* +-----------------------+ +-----------------------+
* | element <= pivot | pivot | element > pivot |
* +-----------------------+ +-----------------------+
* lo pivot - 1 pivot + 1 hi
*
*/
int pivot = partition(a, lo, hi);
r_pivot_sort(a, lo, pivot - 1);
r_pivot_sort(a, pivot + 1, hi);
}
/**
* pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
*
* @param a 정렬 할 배열
* @param left 현재 배열의 가장 왼쪽 부분
* @param right 현재 배열의 가장 오른쪽 부분
* @return 최종적으로 위치한 피벗의 위치(lo)를 반환
*/
private static int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[right]; // 부분리스트의 오른쪽 요소를 피벗으로 설정
// lo가 hi보다 작을 때 까지만 반복한다.
while(lo < hi) {
/*
* hi가 lo보다 크면서, lo의 요소가 pivot보다 큰 원소를
* 찾을 떄 까지 lo를 증가시킨다.
*/
while(a[lo] < pivot && lo < hi) {
lo++;
}
/*
* hi가 lo보다 크면서, hi의 요소가 pivot보다 작거나 같은 원소를
* 찾을 떄 까지 hi를 감소시킨다.
*/
while(a[hi] >= pivot && lo < hi) {
hi--;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
swap(a, lo, hi);
}
/*
* 마지막으로 맨 처음 pivot으로 설정했던 위치(a[right])의 원소와
* hi가 가리키는 원소를 바꾼다.
*/
swap(a, right, hi);
// 두 요소가 교환되었다면 피벗이었던 요소는 hi에 위치하므로 hi를 반환한다.
return hi;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
중간 피벗 선택 방식
public class QuickSort {
public static void sort(int[] a) {
m_pivot_sort(a, 0, a.length - 1);
}
/**
* 중간 피벗 선택 방식
* @param a 정렬할 배열
* @param lo 현재 부분배열의 왼쪽
* @param hi 현재 부분배열의 오른쪽
*/
private static void m_pivot_sort(int[] a, int lo, int hi) {
/*
* lo가 hi보다 크거나 같다면 정렬 할 원소가
* 1개 이하이므로 정렬하지 않고 return한다.
*/
if(lo >= hi) {
return;
}
/*
* 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬 된 상태로
* 만들어 준 뒤, 최종적으로 pivot의 위치를 얻는다.
*
* 그리고나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분리스트로 나누어
* 분할 정복을 해준다.
*
* [과정]
*
* Partitioning:
*
* left part a[(right + left)/2] right part
* +---------------------------------------------------------+
* | element < pivot | pivot | element >= pivot |
* +---------------------------------------------------------+
*
*
* result After Partitioning:
*
* left part a[hi] right part
* +---------------------------------------------------------+
* | element < pivot | pivot | element >= pivot |
* +---------------------------------------------------------+
*
*
* result : pivot = hi
*
*
* Recursion:
*
* m_pivot_sort(a, lo, pivot) m_pivot_sort(a, pivot + 1, hi)
*
* left part right part
* +-----------------------+ +-----------------------+
* | element <= pivot | | element > pivot |
* +-----------------------+ +-----------------------+
* lo pivot pivot + 1 hi
*
*/
int pivot = partition(a, lo, hi);
m_pivot_sort(a, lo, pivot);
m_pivot_sort(a, pivot + 1, hi);
}
/**
* pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메소드
*
* @param a 정렬 할 배열
* @param left 현재 배열의 가장 왼쪽 부분
* @param right 현재 배열의 가장 오른쪽 부분
* @return 최종적으로 위치한 피벗의 위치(hi)를 반환
*/
private static int partition(int[] a, int left, int right) {
// lo와 hi는 각각 배열의 끝에서 1 벗어난 위치부터 시작한다.
int lo = left - 1;
int hi = right + 1;
int pivot = a[(left + right) / 2]; // 부분리스트의 중간 요소를 피벗으로 설정
while(true) {
/*
* 1 증가시키고 난 뒤의 lo 위치의 요소가 pivot보다 큰 요소를
* 찾을 떄 까지 반복한다.
*/
do {
lo++;
} while(a[lo] < pivot);
/*
* 1 감소시키고 난 뒤의 hi 위치가 lo보다 크거나 같은 위치이면서
* hi위치의 요소가 pivot보다 작은 요소를 찾을 떄 까지 반복한다.
*/
do {
hi--;
} while(a[hi] > pivot && lo <= hi);
/*
* 만약 hi가 lo보다 크지 않다면(엇갈린다면) swap하지 않고 hi를 리턴한다.
*/
if(lo >= hi) {
return hi;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
swap(a, lo, hi);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
중간 위치를 피벗으로 설정하게 되면 이미지로 첨부한 것에서도 볼 수 있듯이 hi가 가리키는 위치가 pivot의 위치보다 높으면서 hi가 가리키는 원소가 pivot보다 작은 경우가 생긴다.
그렇기 때문에 분할정복으로 재귀를 호출하더라도 파티셔닝을 통해 얻은 피벗까지 포함하여 부분리스트로 나누어야 한다.
장점
- 특정 상태가 아닌 이상 평균 시간 복잡도는 NlogN이며, 다른 NlogN 알고리즘에 비해 대체적으로 속도가 매우 빠르다. 유사하게 NlogN 정렬 알고리즘 중 분할 정복 방식인 merge sort에 비해 2~3배 정도 빠르다. (정리 부분의 표 참고)
- 추가적인 별도의 메모리를 필요로하지 않으며 재귀 호출 스택 프레임에 의한 공간복잡도는 logN으로 메모리를 적게 소비한다.
단점
- 특정 조건하에 성능이 급격하게 떨어진다.
- 재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.
시간복잡도
O(NlogN) 으로 유지.
이상적으로 피벗이 중앙에 위치되어 리스트를 절반으로 나눈다고 할 때, N개의 데이터가 있는 리스트를 1개까지 쪼개어 트리로 나타내게 되면 이진트리(Binary Tree) 형태로 나온다는 것은 우리가 확인할 수 있다.
N개 노드에 대한 이진트리의 높이(h)는 logN 인 것은 힙정렬 해당 링크를 참고하길 바란다.
비교 및 정렬 과정을 생각해보아야 한다.
우리가 피벗을 잡고 피벗보다 큰 요소와 작은 요소를 각 끝단에서 시작하여 탐색하며 만족하지 못하는 경우 swap을 한다. 이는 현재 리스트의 요소들을 탐색하기 때문에 O(N)이다.
좀 더 자세하게 말하자면 i번 째 레벨에서 노드의 개수가 2^i 개이고, 노드의 크기. 한 노드에 들어있는 원소 개수는 N/2^i 개다.
이를 곱하면 한 레벨에서 비교 작업에 대한 시간 복잡도는 O(2^i × N/2^i) 이고 이는 곧 O(N)이다.
그리고 O(N)의 비교 작업을 트리의 높이인 logN -1번 수행하므로 다음과 같이 표기할 수 있다.
O(N) × O(logN)
최종적으로 위를 계산하면 O(NlogN) 의 시간복잡도를 갖는 것을 알 수 있다.
위와 달리 반대로 최악의 경우도 있다. (퀵 정렬의 최대의 단점이다.)
바로 정렬된 상태의 배열을 정렬하고자 할 때다.
간단한 예시로 왼쪽을 기준으로 피벗을 잡을 때를 생각해보자.
우리가 N개가 있는 리스트에 대해 가장 왼쪽 요소를 pivot을 잡고, pivot보다 작은 요소는 왼쪽에, 큰 요소는 오른쪽에 위치시켜 두 부분리스트로 나누게 된다. 이때 만약 pivot이 가장 작은 요소였다면 부분리스트는 어떻게 나눠질까?
왼쪽의 부분리스트는 없고, N-1개의 요소를 갖는 오른쪽 부분리스트만 생성될 것이다.
이를 반복적으로 재귀 호출을 해본다고 해보자.
결과적으로 각 재귀 레벨에서 N개의 비교 작업을 N번 재귀 호출을 하기 때문에 O(N^2)의 최악의 성능을 내기도 한다.
마찬가지로 정렬할 리스트가 이미 내림차순으로 정렬되어있다면 위 트리에서 왼쪽 서브 트리로 치중되어버릴 것이다. 마찬가지로 O(N^2) 의 시간복잡도를 갖게 된다.
이는 왼쪽 피벗을 선택하건, 오른쪽 피벗을 선택하건 위와 같이 트리가 치중되는 건 마찬가지다. 이 때문에 만약 위처럼 치중될 경우 공간 복잡도 또한 O(N)으로 되어버린다.
그래서 중간 피벗이 선호되는 이유가 바로 이러한 이유 때문이다. 그러면 거의 정렬된 배열이더라도 거의 중간지점에 가까운 위치에서 왼쪽 리스트와 오른쪽 리스트가 균형에 가까운 트리를 얻어낼 수 있기 때문이다. (물론 아예 불가능한 건 아니다.)
그러면 위와 같이 거의 정렬 된 상태의 배열에서 효과적으로 해결할 수 있다.
그럼 왜 다른 O(NlogN) 정렬 방법들에 비해 빠른가에 대해 궁금할 것이다. 만약 Shell Sort 가 다른 정렬 알고리즘에 비해 빠른 편에 속하는 이유를 알고 있다면 좀 더 쉽게 이해할 것이다.
기본적으로 Shell Sort나, Quick Sort는 정렬 방식이 '멀리 떨어진 요소와 교환'되는 정렬 방식이다. Shell Sort는 일정 간격을 두고 두 원소의 값을 비교하며 정렬하고, Quick Sort 또한 양 끝에서 피벗을 기준으로 피벗보다 작은 값을 갖는 위치에 있어야 할 원소가 피벗보다 크거나, 그 반대인 경우 서로 원소를 교환하는 방식이다.
이러한 방식은 해당 원소가 최종적으로 있어야 할 위치에 거의 근접하게 위치하도록 하기 때문에 효율이 좋은 것이다.
예를 들어 9번째 원소가 3번째에 위치해야 한다고 할 때, 보통의 경우 9 → 8 → 7 → 6 → 5 → 4 → 3 이런 식으로 자기가 현재 있는 위치와 바로 직전의 원소와 교환되면서 총 6번에 걸쳐 이동을 했었어야 한다면, Shell Sort나 Quick Sort의 경우 9 → 1 -> 4 -> 3 서로 떨어져 있는 비연속적 원소가 교환되면서 원래 있어야 할 위치에 거의 근접하게 위치하도록 하기 때문에 빠른 정렬이 가능한 것이다.
대신에 위와 같이 정렬하는 경우 별도의 배열이나 플래그(flag)를 부여하지 않는 한 대부분의 정렬의 경우 안정 정렬은 안된다고 보면 된다.
'Algorithm & Data Structure > study' 카테고리의 다른 글
| [Algorithm / Java] ✒️ Dijkstra (다익스트라) (0) | 2022.08.16 |
|---|---|
| [Data Structure / Java] ✒️ Tree(트리) (0) | 2022.08.16 |
| [Algorithm / Java] ✒️ Insertion Sort(삽입 정렬) (0) | 2022.08.16 |
| [Algorithm / Java] ✒️ Selection Sort(선택 정렬) (0) | 2022.08.16 |
| [Data Structure / Java] ✒️ Graph(그래프) (0) | 2022.08.16 |
댓글