퀵 정렬 (Quick Sort)
1. 개념 설명
(1) 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 정렬하는 알고리즘이다.
(2) 방식은 적절한 원소 하나를 기준(pivot)으로 삼아 그보다 작은 것을 앞으로 빼내고 피벗 뒤로 옮겨
작은 것, 큰 것으로 나눈 뒤 나누어진 각각에서 다시 피벗을 잡고 정렬해서 각각의 크기가 0이나 1이 될 때까지 정렬한다.
( 설명 글보다 아래 과정과 코드를 하나씩 써보며 이해하는 것을 추천합니다. )
(3) 퀵 정렬은 컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나이다.
2. 과정
3. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
public class QuickSort {
public static void main(String[] args) {
int[] src = { 38, 27, 43, 9, 3, 82, 10 };
quickSort(src, 0, src.length-1);
System.out.println(Arrays.toString(src));
}
static void quickSort(int[] A, int low, int high) {
// 원소가 더이상 쪼개지지 않는다면, 리턴
if (low >= high) return;
int mid = partition(A, low, high);
quickSort(A, low, mid - 1);
quickSort(A, mid, high);
}
static int partition(int[] A, int low, int high) {
// 피봇 값을 제일 왼쪽에 있는 원소로 지정한다.
int pivot = A[low];
while (low <= high) {
// 만약 원소 값이 피봇 값보다 작다면 옮길 필요 없으므로, 다음 원소 비교
while (A[low] < pivot) low++;
// 만약 원소 값이 피봇 값보다 크다면 옮길 필요 없으므로, 다음 원소 비교
while (A[high] > pivot) high--;
// 만약 옮길 대상이 존재한다면, 바로 swap()으로 원소 교체
if (low <= high) {
int tmp = A[low];
A[low] = A[high];
A[high] = tmp;
low++;
high--;
}
}
return low;
}
}
|
cs |
4. 시간 복잡도
(1) 레코드 개수 N이 N=2^k개의 원소를 정렬한다고 가정했을 때, 최선의 경우, 배열이 균등하게 이등분 되어
순환 호출의 깊이는 k가 된다. 또한 각각의 단계에서 비교 연산 횟수는평균적으로 N번 이루어지므로 O(kN)이다.
이때, k=logN이므로 O(kN)=(순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산)= O(NlogN)이 된다.
(2) 최악의 경우는 정렬하고자 하는 배열이 오름 차순으로 정렬되어 있거나 내림차순으로 정렬되어 있는 경우이다.
그러므로, (비교횟수*순환호출의 깊이) = O(n²)의 시간복잡도를 가진다.
5. 공간 복잡도
(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(n)이다.
6. 장점
(1) 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
(2) 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이
추후 연산에서 제외되는 특성 때문에, 시간 복잡도 O(NlogN)을 가지는 다른 정렬 알고리즘과 비교했을 때도
가장 빠르다.
7. 단점
(1) 정렬된 배열에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
(2) 불안정 정렬이다.