전체 정렬 개요의 설명은 여기를 참조
Bubble / Selection / Insertion 정렬의 설명은 여기를 참조
Shell 정렬의 설명은 여기를 참조
Merge 정렬의 설명은 여기를 참조
Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조
Counting 정렬의 설명은 여기를 참조
Radix 정렬의 설명은 여기를 참조
Bucket 정렬의 설명은 여기를 참조
Topological 정렬의 설명은 여기를 참조
Quick Sort(퀵 정렬)
이름만 봐도 매우 빠르게 동작할 것 같다. 우선 애니메이션으로 한 번 살펴보자.
퀵 정렬은 영국의 Computer Scientist인 Tony Hoare 가 고안한 방식이다. 위의 애니메이션에서 주목할 점은 Pivot이라는 문구이다.
이 Pivot은 하나의 기준으로 선정된 값인데, 이 값을 기준으로 오름차순 정렬을 가정 시, Pivot 보다 작은 값은 왼쪽에, Pivot 보다 큰 값은 오른쪽에 위치시키는 방식을 활용한다.
1회의 작업이 완료되면 위의 Gif처럼 좌측 / 우측의 정렬이 완료되지 않은 부분 집합이 형성된다. 그러면 그 부분 집합 내에서 또 다시 Pivot 값을 하나 선정하고 같은 정렬을 반복하는 것이다.
위와 같이 큰 문제를 지속적으로 작은 문제로 나누어 해결하는 방식을 취하기 때문에 퀵 정렬도 이전 포스팅의 병합 정렬과 같이 분할 정복 알고리즘(Divide and Conquer Algorithm)이다.
※ 분할 정복 알고리즘이란?
하나의 큰 문제를 작은 문제로 분리한 뒤 각각을 해결하여, 결과를 모아 원래 문제를 해결하는 방법.
대개 재귀 호출을 이용하여 구현된다.
퀵 정렬의 특징은 다음과 같다.
| 특성 | 설명 |
| In-place 알고리즘 | 배열을 나누는 과정에서 나누어진 배열을 별도로 저장할 공간이 필요없다. |
| Unstable 알고리즘 | 같은 값의 데이터의 기존 순서 유지를 보장할 수 없다. |
퀵 정렬의 시간 / 공간 복잡도는 아래와 같다.
| 알고리즘 | 시간복잡도(최상) | 시간복잡도(평균) | 시간복잡도(최악) | 공간복잡도 |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n^2) | O(n) |
기본적으로 위와 같은데, 사실 구현하기에 따라 얼마든지 다를 수 있다. 퀵 정렬을 Stable한 알고리즘으로 구현할 수 있고 별도의 메모리 공간이 필요하도록 구현할 수도 있다. 다만, 위의 표에서는 일반적으로 통용되는 개요를 표현한 것이라고 보면 되겠다.
우선 실제 퀵 정렬의 경우를 위의 Gif를 좀 더 세부적으로 분석해서 알아보자.
초기의 상태는 다음과 같다. 여기서 가장 마지막의 값을 Pivot으로 정했다고 가정하자.
그러면, 현재 미정렬된 부분 집합은 전체 집합이므로, 배열의 가장 왼쪽부터 Pivot 바로 전의 값까지를 모두 비교해야 한다. 아래의 그림을 보자.
좌측에는 Pivot보다 작은 값들을, 우측에는 Pivot보다 큰 값들을 놓아야 한다. 따라서, 35는 Pivot 값보다 크고, 26은 Pivot 값보다 작으니까 상호 교환한다. 그 후 다시 좌 / 우측을 좁혀가며 지속 비교한다.
먼저 44를 비교했겠지만, 44는 Pivot 보다 크니까 바로 다음으로 넘어간다. 27은 Pivot보다 작고 33은 Pivot보다 크니 상호 교환한다.
여기서도 42는 Pivot보다 크고, 19는 Pivot보다 작으니 상호 교환한다.
10, 14는 Pivot보다 이미 작은 값이므로 Swap이 불 필요하다. 그리고 이제 Pivot이 위치할 자리를 찾아야 하는데, 이는 Pivot보다 큰 값과 비교해서 Swap을 해야 하므로 위와 같이 진행된다.
이와 같이 마지막 Swap이 마무리 되면 좌측 / 우측에 Pivot을 기준으로 미정렬된 부분 집합(Partition)이 생성된다. 이 때, 각 부분 집합에 대한 Pivot을 기준으로 동일한 정렬을 수행하면 된다.
Pivot 결정하기
위의 예시에서는 배열의 마지막 값을 Pivot으로 결정하여 수행하였다. 그런데 만약 그랬을 때, 아래와 같은 배열을 정렬해야 한다면 어떨까?
Pivot을 가장 좌측(첫 번째 값)으로 지정했고 오름차순 정렬을 하려는데 뒤의 값이 내림차순 기준으로 되어 있으며 41은 이미 가장 큰 숫자라고 해보자. 그럼 1차 정렬을 완료하면 아래와 같은 결과가 된다.
즉, Pivot의 위치를 찾았더니 모든 값과 비교하여 Swap이 되었을 것이고 가장 오른쪽에 위치하게 되었을 것이다.
Pivot이 적당히 중간 즈음 위치했다면 양 쪽의 부분 집합이 균등하게 배분되어 전체 비교 횟수를 현저히 줄일 수 있는데 이와 같은 현상이 반복된다면 비교를 더욱 많이 해야 한다. 사실상 버블 정렬과 다를 바가 없다.
이런 최악의 경우, 전체 시간 복잡도는 O(n^2) 만큼 발생하게 되어 퀵 정렬의 장점이 사라지게 된다.
그래서, 이와 같이 무조건 최 우측/좌측의 값을 Pivot으로 무조건 설정하는 것은 좋은 방법이 아니다. 최악의 성능을 회피하기 위해 아래와 같은 방법을 예시로 사용할 수 있다.
① 그냥 Random하게 골라보기
랜덤하게 설정하면 항상 최악의 Case가 되지는 않을 것이다. 그러나 최악의 Case가 생겨날 수는 있다. (평균적으로 O(nlogn) 유지)
② Median-Of-3 method
이는 배열의 값들 중 가장 좌측 / 우측, 중앙값 3개를 뽑고, 그 3개의 값을 우선적으로 정렬한 뒤, 그 중 중간 값을 가장 좌측 또는 우측으로 이동시켜 Pivot으로 설정한 뒤 퀵 정렬을 수행하는 방법이다.
이 값이 Pivot으로 사용되어 전체 배열을 균등하게 분할할 것이라는 보장은 없지만, 최소한 이 값이 전체 값 중 최대 / 최소값에는 해당하지 않기 때문에 중심 극한 정리에 따라 평균적으로 O(nlogn)의 시간복잡도를 유지할 수 있게 된다.
예를 들어서 상단의 그림으로 설명한 배열을 기준으로 보면 다음과 같다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 35 | 33 | 42 | 10 | 14 | 19 | 27 | 44 | 26 | 31 |
여기서 First 는 35, Mid 는 14, Last는 31인데 정렬하면 Last인 31이 Median 값이 되고 이 값을 Pivot으로 사용하면 되는 것이다. 하필 이번에는 기존의 경우와 동일한데 개념만 이해하면 되겠다.
관련 코드는 아래에서 확인할 수 있다.
퀵 정렬 코드
실제 퀵 정렬의 코드는 다음과 같다. 아래의 예시는 Pivot을 배열의 제일 좌측에 있는 값으로 설정한 경우이다.
public class QuickSort {
static int compare = 0;
static int swap = 0;
public static void main(String[] args){
int[] arr = new int[100];
for(int i=0; i < arr.length; i++){
arr[i] = (int)(Math.random()*100);
}
quick_sort(arr);
// 출력
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + ", ");
}
System.out.println();
System.out.println("비교 횟수 : " + compare);
System.out.println("Swap 횟수 : " + swap);
}
public static void quick_sort(int[] arr){
quick_sort(arr, 0, arr.length);
}
private static void quick_sort(int[] arr, int start, int end){
// Data가 1개만 남은 경우 더 이상 분할할 수 없으니 반환
if(end - start < 2){
return;
}
// partition method를 통해 pivot의 index를 구하면 좌측은 모두 pivot 이하의 값, 우측은 pivot 이상의 값
int pivotIndex = partition(arr, start, end);
// 해당 pivot의 위치만을 제외한 좌 / 우측의 내부를 다시 정렬
quick_sort(arr, start, pivotIndex);
quick_sort(arr, pivotIndex+1, end);
}
private static int partition(int[] arr, int start, int end){
//첫 element를 pivot으로 사용
// pivot이 될 값을 다른 변수에 잠시 저장
int pivot = arr[start];
int i = start;
int j = end;
// start되는 pivot index와 end가 교차되지 않는 동안 반복
while(i < j){
// end부분에서 --한 값이 pivot보다 큰 동안 계속 j의 값을 감소
// 왜 prefix냐면 우측 Partition인 경우 length로 시작하니까 Index가 초과해 값이 없으며
// 좌측 Partition이라면 이전 pivot의 위치이므로 역시 비교할 이유가 없기 때문
// 최초 정렬 시라면 length로 시작하니 Index가 초과해 값이 없음.
// i < j 구간에서만 수행한다. 왜냐하면 j 값이 0미만으로 갈 수 있음
while(i < j && arr[--j] > pivot) compare++;
// ++i동안 pivot보다 작거나 같다면 이미 더 작은 값이므로 계속 ++
// 왜 prefix냐면 최초 i는 pivot값이기 때문이다.
// i < j 구간에서만 수행한다. i 값이 전체 index를 초과할 수 있음
while(i < j && arr[++i] < pivot) compare++;
// 만약 i와 j가 교차되지 않았다면 i의 index자리에 j의 index 값을 넣는다.
// 왜냐하면 그 값은 pivot보다 작으니까 pivot보다 좌측에 놓아야 하기 때문
if(i < j){
swap(arr, i, j);
swap++;
}
}
// 교차되었다면 반복문을 빠져나온 것이므로 pivot의 값과 현재 j 위치의 값을 Swap
swap(arr, start, j);
// 해당 pivot의 위치를 반환
return j;
}
private static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
위 내용에선, 주석 등을 통해 각각의 Logic을 좀 더 자세히 분석하기 위해 길게 썼는데, 간결한 코드로 Quick sort를 아래와 같이 작성할 수 있다.(Pivot값, End의 전달 index가 다른 점을 유의)
public class Quicksort {
static int compare = 0;
static int swap = 0;
public static void main(String[] args){
int[] arr = new int[100];
for(int i=0; i < arr.length; i++){
arr[i] = (int)(Math.random()*100);
}
quick_sort(arr);
// 출력
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + ", ");
}
System.out.println();
System.out.println("비교 횟수 : " + compare);
System.out.println("Swap 횟수 : " + swap);
}
public static void quick_sort(int[] arr){
// end 부분이 바뀐 점 유의
quick_sort(arr, 0, arr.length-1);
}
private static void quick_sort(int[] arr, int start, int end){
int pivot = arr[(start + end) / 2];
int i = start;
int j = end;
while(i <= j){
while(arr[i] < pivot) i++; compare++;
while(arr[j] > pivot) j--; compare++;
if(i <= j) {
swap(arr, i, j);
i++; j--;
swap++;
}
}
// 해당 pivot의 위치만을 제외한 좌 / 우측의 내부를 다시 정렬
if(start < j) quick_sort(arr, start, j);
if(end > i) quick_sort(arr, i, end);
}
private static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
위 코드는 Pivot을 가장 좌측의 값으로 설정했는데, 이번엔 Median-Of-Three 방식으로 해보자. 줄여서 MotQuickSort로 구현
public class MotQuickSort {
static int compare = 0;
static int swap = 0;
public static void main(String[] args){
int[] arr = new int[100];
for(int i=0; i < arr.length; i++){
arr[i] = (int)(Math.random()*100);
}
quick_sort(arr);
// 출력
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + ", ");
}
System.out.println();
System.out.println("비교 횟수 : " + compare);
System.out.println("Swap 횟수 : " + swap);
}
public static void quick_sort(int[] arr){
quick_sort(arr, 0, arr.length-1);
}
private static void quick_sort(int[] arr, int start, int end){
int pivot = get_median(arr, start, end);
int i = start;
int j = end;
while(i <= j){
while(arr[i] < pivot) i++; compare++;
while(arr[j] > pivot) j--; compare++;
if(i <= j) {
swap(arr, i, j);
i++; j--;
swap++;
}
}
// 해당 pivot의 위치만을 제외한 좌 / 우측의 내부를 다시 정렬
if(start < j) quick_sort(arr, start, j);
if(end > i) quick_sort(arr, i, end);
}
// 3개 중 중앙값을 가져온다.
private static int get_median(int[] arr, int start, int end){
// end 값이 현재의 length 혹은 이전 pivot index 이므로 1을 빼준다.
int center = (start+end)/2;
// 3개의 값을 크기 순서대로 정렬해서 Low / Median / High의 순서로 만든다.
if(arr[start] > arr[center])
swap(arr, start ,center);
if(arr[start] > arr[end-1])
swap(arr, start, end-1);
if(arr[center] > arr[end-1])
swap(arr, center, end-1);
// 정렬된 상태에서 마지막과 중간을 교환하여 중간값을 최 좌측으로 이동시킨다.
swap(arr, start, center);
return arr[start];
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
위의 코드들은 비교 횟수 / Swap 횟수를 계산하도록 구현되어 있으니 실제로 구현 방식에 따라 얼마나 비교 / Swap을 적게 하는지 테스트 해보는 것도 좋다.
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - 정렬 6 (Radix) (0) | 2020.11.14 |
|---|---|
| 자료구조 - 정렬 5 (Counting) (0) | 2020.11.14 |
| 자료구조 - 정렬 3 (Merge) (0) | 2020.11.09 |
| 자료구조 - 정렬 2 (Shell) (0) | 2020.11.09 |
| 자료구조 - 정렬 1 (Bubble / Selection / Insertion) (0) | 2020.11.07 |
