퀵 정렬
비교 기반 알고리즘 중 분할 정복 방식을 이용하며 평균적으로 좋은 성능을 보여 널리 사용되는 퀵 정렬에 대해 알아본다.
아이디어
이진 탐색과 같은 분할 정복 원리를 이용한다.
-> 특정 원소를 기준으로 배열을 두 부분 배열로 분할한다.
-> 각 부분배열에 대해 퀵 정렬을 순환적으로 적용한다.
이때 특정 원소, 즉 피벗을 정하는 것이 퀵 정렬의 핵심이다. 뒤에서 살피겠지만 피벗을 어떤 것으로 지정하느냐에 따라 성능 차이가 크게 나기 때문이다.
퀵 정렬에서는 결합은 별도로 필요 없다. 피벗을 기준으로 나눠진 두 부분 배열을 순환적으로 적용하되, 그 과정에서 정렬이 일어나므로 최종 분할이 끝나는 시점에는 모든 배열이 정렬되어 있다.
작동 원리
다음과 같은 데이터를 정렬하는 과정을 통해 실제 작동 원리를 살펴보자 .
int[] arr2 = {30, 45, 20, 15, 40, 25, 35, 10};
전체 과정
피벗을 첫 번째 원소로 잡고 오름차순으로 정렬하는 것을 가정한다. 피벗 설정은 어떤 것으로 해도 사실은 상관 없지만 일반적인 상황을 가정하기 위해 첫 번째 원소로 잡도록 한다.
따라서 위 배열에서 피벗은 30이다.
이제 30을 기준으로 두 배열로 나눌 것이다. 그런데 어떻게 나누느냐? 피벗을 배치시키는 것이다. 피벗의 자리를 옮겨야 한다.
피벗이 자리를 옮기는 배치 과정을 살펴보면 다음과 같다. 이는 전체적인 수행 과정을 보여준다.
i) {25 10 20 15 30 40 35 45}
ii) {15 10 20 25 30 35 40 45}
iii) {10 15 20 25 30 35 40 45}
iV) {10 15 20 25 30 35 40 45}
V) {10 15 20 25 30 35 40 45}
Vi) {10 15 20 25 30 35 40 45}
Vii) {10 15 20 25 30 35 40 45}
이처럼 먼저 첫 번째 피벗인 30이 자리가 옮겨지고 나면, 각 나눠진 두 부분 배열에 대해 또 다시 피벗을 정하고 옮겨지고 과정을 반복하는 것이다. 예를 들어 ii) 번째 상황에서의 피벗은 25이다.
이렇게 피벗 배치 과정을 반복하다 보면 정렬이 되어 있다. 따라서 피벗이 어떻게 움직이며 정렬을 시키느냐, 즉 분할함수가 퀵 정렬에서는 핵심이 된다.
partition()
첫 번재 피벗인 30이 배치되는 과정을 살펴보자. 진행 과정은 다음과 같다.
1) 피벗 다음 요소를 left 로 설정한다.
2) 맨 마지막 요소를 right 로 설정한다.
3) left가 right보다 작은 경우 (즉 while left< right)
4) left는 피벗보다 큰 값을 찾고 (찾을 때까지 -> 방향 진행)
5) right는 피벗보다 작은 값을 찾는다 (찾을 때까지 <- 방향 진행)
6) 찾았으면 찾은 값을 교환한다.
7) 만약 left가 right보다 크다면 이제 피벗 위치를 찾은 것이므로 right(작은 값)를 피벗과 교환한다.
예시로 살펴보자.
피벗 다음의 숫자인 45를 left로 설정한다. 그리고 맨 마지막 숫자인 10을 right로 설정한다.
left와 right는 각각 피벗보다 큰 값, 작은 값을 찾을 때까지 진행한다. 먼저 자기 자신에 대해 탐색 후, left는 -> , right는 <- 방향으로 한 칸씩 탐색한다.
예를 들어, 45를 살펴보자. 30인 피벗보다 큰 값이다. 그러면 해당 값은 선택된다. 10은 어떨까? 30인 피벗보다 작다. 역시 선택된다. 그러면 요소의 위치를 바꿔준다. 즉,
{30, 10, 20, 15, 40, 25, 35, 45} 가 된다.
탐색에 성공했으므로 다음 방향으로 진행한다. 만약 탐색에 실패한다면 성공할 때까지 계속 진행한다. 예를 들어 left의 현재 위치는 20이 된다. 하지만 30보다 크지 않으므로 계속 진행하며 피벗보다 큰 값, 즉 40을 만날 때까지 자리를 옮긴다.
마찬가지로 right 역시 25를 만날때까지 진행하다가 25를 만났을 때 멈춘다.
두 요소를 교환한다.
배열은 {30, 10, 20, 15, 25, 40 35, 45} 가 된다. 이때, 이제 left와 right의 비교를 보면 left>right가 되었다.
따라서 right인 25를 피벗과 교환한다.
그 결과 {25, 10, 20, 15, 30, 40, 35, 45} 가 되었으며, 왼쪽과 오른쪽 두 부분 배열로 나뉜 것을 볼 수 있다.
퀵 정렬은 이와 같은 분할함수를 계속해서 반복한다.
다음은 이 과정을 나타내는 코드이다.
// 퀵 정렬을 호출하는 메인 함수
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right); // 피벗을 기준으로 분할
quickSort(arr, left, pivot - 1); // 왼쪽 부분 배열에 대해 퀵 정렬 재귀 호출
quickSort(arr, pivot + 1, right); // 오른쪽 부분 배열에 대해 퀵 정렬 재귀 호출
}
}
분할 함수는 다음과 같다.
// 퀵 정렬에 핵심이 되는 분할 함수
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 맨 첫 번째 요소를 피벗으로 선택
int i = left + 1;
int j = right;
while (i <= j) {
if (arr[i] <= pivot) {
i++;
} else if (arr[j] > pivot) {
j--;
} else {
swap(arr, i, j); // 찾은 두 요소를 교환
i++;
j--;
}
}
swap(arr, left, j); // 피벗을 분할 기준으로 위치시킴
return j;
}
위에서 설명한 내용을 실제 코드 작동과 함께 살펴보면 다음과 같다.
시간 복잡도 (성능)
퀵 정렬의 성능을 분석해보자.
먼저 분할 함수 partition()의 수행 시간은 피벗과의 비교 횟수로 계산된다.
n개의 데이터에 대해 left -> | <- right 가 각각 진행을 하면서 하나씩 요소를 탐색하므로 쎄타(n)으로 표기할 수 있다.
- 초기화: pivot, i, j를 각각 상수 시간 내에 초기화한다. => O(1)
- 반복문: 반복문은 i가 j보다 작거나 같은 동안 실행된다. 반복문 내에서 수행되는 각각의 비교 연산과 증감 연산은 상수 시간에 수행되므로 반복문의 실행 횟수에 비례한다. => O(j-i)
- swap 함수 호출: swap 함수는 배열에서 두 요소를 교환하는 연산을 수행한다. swap 함수 호출의 횟수는 i와 j의 차이에 비례하며, 이는 반복문의 실행 횟수와 동일하다. => O(j-i)
- 피벗 위치 조정: 반복문이 종료되면 i와 j의 값은 교차한다. 이때 i와 j가 교차한 위치를 기준으로 피벗을 위치시키기 위해 피벗과 해당 위치의 요소를 교환하므로 상수 시간. => O(1)
즉, 데이터 개수에 선형적으로 비례하므로 O(n)으로 표기할 수 있다.
그렇다면 순환 호출을 하는 전체 함수의 수행 시간은 어떻게 될까?
순환 호출을 하므로 폐쇄형으로 구해야 한다.
퀵 정렬의 특성을 고려해보면 분할 후 데이터는 T(x) 와 T(y)로 나뉜다. 분할되는 두 부분 배열의 크기는 다음과 같은 경우의 수를 갖는다.
0 : n-1
1 : n-2
2: n-3
.
.
.
n-1 : 0
이처럼 다양하게 나뉠 수 있으므로 점화식은 다음과 같이 작성할 수 있다.
T(n) = T(x) + T(y) + 쎄타(n)
x와 y는 임의의 데이터를 의미하는데, 두 배열을 합쳤을 때는 n-1개이다.
이와 같이 데이터 분할은 여러 가지 경우가 발생할 수 있기 때문에 최선의 경우와 최악의 경우를 나누어 살펴보아야 한다.
i) 최악의 경우
-> 배열이 항상 0:n-1 혹은 n-1:0으로 분할되는 경우이다.
예를 들어 {10, 20, 30, 40, 50} 혹은 {50, 40, 30, 20, 10}으로 분할되는 경우이다.
이는 극심한 불균형적 분할을 의미한다.
피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분 배열이 되는 경우를 의미하며 이는 다른 말로, 피벗이 항상 부분 배열의 최솟값 또는 최댓값이 되는 것을 뜻한다.
이 경우 점화식은 다음과 같다.
T(n) = T(n-1) + T(0) + 쎄타(n)
=> T(n) = T(n-1) + 쎄타(n)
=> T(n) = O(n^2)
각 단계에서 피벗을 기준으로 분할한 결과 하나의 부분 배열은 크기가 1 감소하게 되므로 배열의 크기는 n, n-1, n-2, ..., 1이 된다. 따라서 점화식의 크기는 O(n)이다. 각 분할 단계마다 O(n)의 시간이 소요되므로 총 시간 복잡도는 O(n^2)라는 결론이 나온다.
이와 같이 일반적인 정렬 방식과 다를바 없는 성능을 나타내게 된다.
한편, 최선의 경우는 어떠할까?
배열이 항상 n/2 : n/2, 즉 반반으로 분할되는 경우일 것이다.
{30, 45, 35, 40, 20, 15, 25}의 경우 => {20, 25, 15, 30, 40, 35, 45}로 정확히 반반으로 분할된다.
이를 점화식으로 나타내면
T(n) = T(floor(n/2)) + T(floor(n/2)) + 쎄타(n)
=> T(n) = 2T(n/2) + 쎄타(n)
=> T(n) = O(nlogn)
분할 단계에서 배열을 균등하게 분할하므로 배열의 크기가 매 단계마다 절반으로 줄어든다. 따라서 점화식의 크기는 O(log n)이다.
이제서야 비교 기반 정렬의 하한 값인 O(nlogn) 의 성능을 보인다.
그렇다면 평균의 경우는 어떨까?
0:n-1, 1:n-2, 2:n-3, ... n-2:1, n-1:0 의 경우를 다 더해서 평균을 구하면 된다.
피벗을 기준으로 분할된 부분 배열의 크기가 k와 (n-k-1)인 경우를 고려한다.
T(n) = 1/n∑(T(i-1) + T(n-i)) + 쎄타(n) {i=1, n>=2}
이를 풀이하면 T(n) = O(nlogn)이다.
결론적으로
최선/평균 -> O(nlogn)
최악 -> O(n^2)
그렇다면 최악의 성능이 일반 정렬과 다르지 않으므로 퀵 정렬은 좋지 못한 정렬일까?
그렇지 않다. 실제로 퀵 정렬은 다양한 곳에서 많이 쓰이는데 Java의 Arrays.sort() 역시 퀵 정렬을 사용한 방식으로 정렬을 구현한다. 듀얼 피벗 방식의 퀵 정렬을 사용하는 Arrays.sort()에 대한 자세한 설명은 아래 글에서 볼 수 있다.
https://upcurvewave.tistory.com/379
Java의 Arrays.sort() 정렬 메서드
Java.util 패키지의 Arrays 클래스에 정의된 sort() 메서드에 대해 살펴본다. 아래와 같이 다양한 sort() 메서드가 오버로딩 되어 있다. public class Arrays { private Arrays() {} public static void sort(int[] a) { DualPivotQ
upcurvewave.tistory.com
결론적으로 퀵 정렬의 성능은 피벗 선택의 임의성만 보장된다면 평균 성능을 보인다. 거의 일정하게 O(nlogn) 성능을 보이는 병합정렬이 있음에도 퀵 정렬이 사용되는 이유는 제자리 정렬(in-place)이 아닌 병합정렬에 비해 퀵 정렬은 (일반적으로) 제자리 정렬이기 때문이다. 즉, 별도의 추가 메모리 저장 공간을 필요로 하지 않으며, 이는 대량의 데이터 정렬시 유용할 수 있다.
특징
1. 분할 정복 방식을 이용한다.
2. 경우에 따른 성능 차이가 발생한다.
- 최악 => O(n^2)
- 평균/최선 => O(nlogn)
3. 피벗 선택의 임의성만 보장되면 평균적인 성능을 보이는 효율적인 알고리즘이다.
4. 안정적인 알고리즘 x
5. 제자리 정렬 알고리즘 o
자바 구현 코드
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr1 = {5, 2, 8, 6, 1, 9, 3};
int[] original1 = Arrays.copyOf(arr1, arr1.length);
quickSort(arr1, 0, arr1.length - 1);
System.out.println("원본 배열: " + Arrays.toString(original1) + " 정렬된 배열: " + Arrays.toString(arr1));
int[] arr2 = {30, 45, 20, 15, 40, 25, 35, 10};
int[] original2 = Arrays.copyOf(arr2, arr2.length);
quickSort(arr2, 0, arr2.length - 1);
System.out.println("원본 배열: " + Arrays.toString(original2) + " 정렬된 배열: " + Arrays.toString(arr2));
}
// 퀵 정렬을 호출하는 메인 함수
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right); // 피벗을 기준으로 분할
quickSort(arr, left, pivot - 1); // 왼쪽 부분 배열에 대해 퀵 정렬 재귀 호출
quickSort(arr, pivot + 1, right); // 오른쪽 부분 배열에 대해 퀵 정렬 재귀 호출
}
}
// 퀵 정렬에 핵심이 되는 분할 함수
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 맨 첫 번째 요소를 피벗으로 선택
int i = left + 1;
int j = right;
while (i <= j) {
if (arr[i] <= pivot) {
i++;
} else if (arr[j] > pivot) {
j--;
} else {
swap(arr, i, j); // 찾은 두 요소를 교환
i++;
j--;
}
}
swap(arr, left, j); // 피벗을 분할 기준으로 위치시킴
return j;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
'알고리즘 > 기초' 카테고리의 다른 글
| 자바 숫자의 자릿수를 판별하는 5가지 방식 (1) | 2023.06.21 |
|---|---|
| 자바 문자열 역순 뒤집기 4가지 방법 (1) | 2023.06.21 |
| 절대값을 이용한 i, j의 증감 규칙 찾기 (절대값과 나머지를 이용하기) (0) | 2023.06.18 |
| 선택 정렬, 아이디어, 작동 원리, 자바 구현 코드 (0) | 2023.06.10 |
| 계수 정렬(countin/카운팅 정렬) 아이디어, 작동원리, 시간 복잡도, 자바 구현 코드 (0) | 2023.06.10 |
