Reference URL : https://st-lab.tistory.com/250
🌱 퀵 정렬(Quick Sort)
하나의 리스트를 피벗(pivot)을 기준으로 하나는 pivot보다 작은 값들의 부분리스트, 하나는 pivot보다 큰 값들의 부분리스트로 정렬한 뒤, 각 부분리스트에 대해 위 방식대로 재귀적으로 수행하여 정렬하는 방법
분할 정복(Divide and Conqure)
퀵 정렬은 기본적으로 '분할 정복' 알고리즘을 기반으로 정렬되는 방식이다. 다만, 병합 정렬(Merge Sort)과 다른 점은 병합 정렬은 하나의 리스트를 '절반'으로 나누어 분할 정복을 하고, 퀵 정렬의 경우 피벗(pivot)을 기준으로 분할 정복을 하기 때문에 하나의 리스트에 대해 비균등하게 나뉠 수 있다는 점이다.
일반적인 성능 : 퀵 정렬 > 병합 정렬
퀵 정렬은 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않으므로 '제자리 정렬(in-place sort)'이다. 또한, 두 개의 부분 리스트를 만들 때 서로 떨어진 원소끼리 교환이 일어나므로 불안정정렬(Unstable Sort) 알고리즘이기도 하다.
🌿 정렬 과정
-
피벗 선택
-
피벗을 기준으로 왼쪽은 피벗보다 큰 값, 오른쪽은 피벗보다 작은 값을 탐색
-
양 방향에서 찾은 두 원소를 교환
-
왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때까지 2번으로 돌아가 위 과정을 반복
-
엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때까지 1번 과정을 반복 (Divide : 분할)
-
인접한 부분리스트끼리 합침 (Conqure : 정복)
2-3번 방식을 흔히 호어(Hoare) 방식이라고 한다.
🌿 왼쪽 피벗 선택 방식
package sort;
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개 이하이므로
* 정렬하지 않고 리턴
* */
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]; //부분리스트의 왼쪽 요소를 피벗으로 설정
while (lo < hi) {
//hi 방향에서 pivot보다 작거나 같은 요소 탐색
while (a[hi] > pivot && lo < hi) hi--;
/*
* lo 방향에서 pivot보다 큰 요소 탐색
* 작거나 같은 이유는 pivot의 시작 위치가 lo와 같기 때문
* */
while (a[lo] <= pivot && lo < hi) lo++;
swap(a, lo, hi);
}
/*
* 마지막으로 맨 처음 pivot으로 설정했던 위치(a[left])의 원소와
* lo가 가리키는 원소를 바꾼다.
* */
swap(a, left, lo);
return lo;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
🌿 오른쪽 피벗 선택 방식
package sort.quickSort;
public class RightQuickSort {
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개 이하이므로
* 정렬하지 않고 리턴
* */
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 : 최종적으로 위치한 피벗의 위치(hi)
* */
private static int partition(int[] a, int left, int right) {
int lo = left;
int hi = right;
int pivot = a[right]; //부분리스트의 오른쪽 요소를 피벗으로 설정
while (lo < hi) {
//lo 방향에서 pivot보다 크거나 같은 요소 탐색
while (a[lo] < pivot && lo < hi) lo++;
/*
* hi 방향에서 pivot보다 작은 요소 탐색
* 크거나 같은 이유는 pivot의 시작 위치가 hi와 같기 때문
* */
while (a[hi] >= pivot && lo < hi) hi--;
swap(a, lo, hi);
}
/*
* 마지막으로 맨 처음 pivot으로 설정했던 위치(a[right])의 원소와
* hi가 가리키는 원소를 바꾼다.
* */
swap(a, right, hi);
return hi;
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
🌿 중간 피벗 선택 방식
package sort.quickSort;
public class CenterQuickSort {
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개 이하이므로
* 정렬하지 않고 리턴
* */
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) {
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보다 작은 경우가 생긴다.
=> hi > pivot && a[hi] < pivot
그렇기 때문에, 파티셔닝을 통해 얻은 피벗까지 포함하여 부분리스트로 나누어야 한다.
=> m_pivot_sort(a, lo, pivot); m_pivot_sort(a, pivot + 1, hi);
lo와 hi를 배열 인덱스 범위에서 1씩 벗어나게 한 후, do-while을 사용한 것은 중앙 인덱스를 얻기 위함이 아니라 피벗을 찾기 위한 루프가 중지되지 않도록 하기 위함이다. 즉, 이전에 비교했던 pivot 다음 값부터 루프를 시작하기 위함이다.
5 3 8 9 2 4 7
1. 첫 do-while에서 lo는 9 위치에서 멈춤
2. hi는 마지막 블럭에 위치함
3. 따라서, return되지 않고 swap 후 다음 while(true) 이 시작됨
4. 그런데, hi든 lo든 pivot에서 멈추기 때문에 while을 통해 a[lo] < pivot 식으로 비교하면 같은 값이므로 루프를 돌지 않고 바로 끝나버린다.
5. 따라서, do-while을 통해 lo++ or hi--를 한 후에 pivot과 겹치지 않는 값과 비교하도록 해야 적절한 시간복잡도에 구할 수 있다.
🌿 퀵 정렬의 장단점
📌 장점
-
특정 상태(정렬된 상태)가 아닌 이상 평균 시간 복잡도는 O(NlogN)이며, 다른 O(NlogN) 알고리즘에 비해 대체적으로 속도가 매우 빠르다. 유사하게 O(NlogN) 정렬 알고리즘 중 분할정복 방식인 merge sort에 비해 2~3배 정도 빠르다.
-
추가적인 별도의 메모리를 필요로 하지 않으며 재귀 호출 Stack 프레임에 의한 공간 복잡도는 logN으로 메모리를 적게 소비함
📌 단점
-
특정 조건(정렬된 상태) 하에 성능이 급격하게 떨어진다. (O(n2))
-
재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.
🌿 시간 복잡도
이상적으로 피벗이 중앙에 위치되어 리스트를 절반으로 나눈다고 할 때, N개의 데이터가 있는 리스트를 1개까지 쪼개어 트리로 나타내게 되면 Binary Tree 형태로 나온다.
알고리즘에서 피벗을 잡고 큰 요소와 작은 요소를 각 끝단에서 시작하여 탐색하며 만족하지 못하는 경우 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)의 시간복잡도를 갖는 것을 알 수 있다.
퀵 정렬은 정렬된 상태의 배열을 정렬하고자 할 때 최악의 성능을 보인다.
예를 들어, 가장 왼쪽 요소를 pivot으로 잡았을 때, pivot보다 작은 요소는 왼쪽에, 큰 요소는 오른쪽에 위키시켜 두 부분리스트로 나누게 된다. 이때 만약 pivot이 가장 작은 요소였다면 왼쪽의 부분리스트는 없고 오른쪽 부분리스트만 생성될 것이다. 이를 반복적으로 재귀호출을 한다고 해보자
결과적으로 각 재귀 레벨에서 N개의 비교 작업을 N번 재귀호출하기 때문에 O(N^2)의 최악의 성능을 내기도 한다.
마찬가지로 정렬할 리스트가 이미 내림차순으로 정렬되어있다면 위 트리에서 왼쪽 서브 트리로 치중되어버릴 것이다. 마찬가지로 O(N^2)의 시간복잡도를 갖게 된다. 이는 왼쪽, 오른쪽 피벗 선택 모두 같다. 이 때문에 만약 위처럼 치중될 경우 공간복잡도 또한 O(N)으로 되어버린다.
그래서 중간 피벗이 선호되는 이유가 바로 이러한 이유 때문이다. 그러면 거의 정렬된 배열이더라도 거의 중간 지점에 가까운 위치에서 왼쪽 리스트와 오른쪽 리스트가 균형에 가까운 트리를 얻어낼 수 있기 때문이다.
📌 퀵 정렬이 빠른 이유
기본적으로 Shell Sort나 Quick Sort는 정렬 방식이 '멀리 떨어진 요소와 교환'되는 정렬 방식이다. Shell Sort는 일정 간격을 두고 두 원소의 값을 비교하며 정렬하고, Quick Sort 또한 양 끝에서 피벗을 기준으로 피벗보다 작은 값을 갖는 위치에 있어야 할 원소가 피벗보다 크거나, 그 반대인 경우 서로 원소를 교환하는 방식이다.
이러한 방식은 해당 원소가 최종적으로 있어야 할 위치에 거의 근접하게 위치하도록 하기 때문에 효율이 좋은 것이다.
대신에 위와 같이 정렬하는 경우 별도의 배열이나 플래그(flag)를 부여하지 않는 한 대부분의 정렬의 경우 안정정렬은 안된다고 보면 된다.
각 정렬 알고리즘별 시간복잡도와 평균 정렬 속도
Reference URL : https://st-lab.tistory.com/250
