Quicksort(퀵정렬)이란?
QuickSort?
- 말 그대로 빠른 정렬이다.
- 퀵 소트는 평균적인 시간복잡도는 O(NlogN), 최악의 경우 O(N^2) 이다.
- 따로 메모리를 저장하여 정렬하지 않아서 공간복잡도는 O(1)이다!
- 이러한 불규칙적 성질 때문에 불안정 정렬이라 한다.
- 일단 이론이 굉장히 어려우므로 바로 설명을 가보도록 하자
과정
1. 리스트 안에 있는 한 요소(pivot)를 고르자!
2. pivot을 기준으로 큰 값은 오른쪽, 작은 값은 왼쪽으로 정렬하자~!
3. pivot의 왼쪽 부분과 오른쪽 부분을 다시 재귀로 정렬하자!
4. 단 리스트의 크기가 0, 혹은 pivot 자신만 있을 때 (1) 이면 하지 않는다!
Quick 정렬에 대한 고찰
- 파티션을 나누는 과정이 MergeSort와 동일하게 2분할이다.
- 따라서 나누는 과정에 대한 시간 복잡도는 O(logN)이다.
- 각각의 파티션의 원소를 전부 비교하므로 O(N)의 연산이 들어간다.
- 따라서!! 총 시간복잡도는 O(NlogN)이다.
* 하지만, pivot에 대한 파티션 분할이 딱 절반이 아니라면?
- 결과적으로.. 파티션이 n개로 결정되어.. O(N^2)이다!
개선방안
* 그럼 어떡하냐?
- pivot을 가운데로 올 수 있게 잡자! = 말이 쉽지
- 그래서, Arrays.sort()는 듀얼 pivot으로 되어있다!
* 하지만, 데이터의 양에 따라서 sort 하는 방법은 다르게 해야된다
- 주어진 N이 작으면 Quick Sort를 호출하는 Function call 비용이 커지게 되어 더 느려지게 된다.
- 이때는 일반적인 Insertion Sort를 통하여 정렬하는 것이 더 빠르다~! ( 비록 O(N^2) 이지만... )
- 실제로 java의 DualPivotQuicksort 클래스는 N의 크기에 따라 정렬방법을 고른다!
- 요약하면, N이 47보다 작을 때는 Insertion Sort
- N이 47보다 크고 286보다 작을 때는 Quick Sort
- 286보다 더 크면 Merge Sort를 이용한다!
코드 구현
|
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
package study;
import java.util.Arrays;
/**
* 퀵 정렬을 구현해보자~!
* 동작 방식은 다음과 같다.
* 1.pivot을 임의로 선정한다.
* 2.선정한 pivot에 대해 왼쪽 파티션은, pivot보다 작은 값! 오른쪽 파티션은, pivot보다 큰 값!
* 3.왼쪽과 오른쪽 파티션에 대하여, 다시 정렬하는 작업을 실시한다.
* 4.이러한 작업을 어레이 크기가 0 또는 1일때까지 반복한다!!
* 1000만개 정렬시 걸리는 시간 : 387ms
* @author huisam
*
*/
public class QuickSort {
private static int SIZE = 10;
/** 배열을 저장할 변수 */
private int arr[] = new int[SIZE];
/** 객체 생성시 난수 뿌리기 */
public QuickSort() {
for (int i = 0; i < SIZE; i++) {
arr[i] = (int) (Math.random() * 100) + 1;
}
}
/**
* 배열을 출력할 메서드
*/
public void print() {
System.out.println(Arrays.toString(arr));
}
/**
* 퀵 정렬이 이루어지는 알고리즘
* pivot을 가운데로 선정하여 파티션 분할하면 성능을 개선할 수 있다.
* @param left
* @param right
*/
public void quicksort(int left, int right) {
if (left >= right) {
return;
}
int l = left - 1;
int r = right + 1;
int mid = arr[(l+r)/2];
while (true) {
while (arr[++l] < mid);
while (arr[--r] > mid);
if (l >= r) {
break;
}
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
quicksort(left, l-1);
quicksort(r + 1, right);
}
public static void main(String[] args) {
QuickSort q = new QuickSort();
long time = System.currentTimeMillis();
q.quicksort(0, 9);
System.out.println(System.currentTimeMillis() - time + "ms");
}
}
|
cs |
참고
[알고리즘] 퀵 정렬(quick sort)이란
Sorting Algorithm을 비판적으로 바라보자