반응형
-
주어진 배열을 두 개로 분할하고, 정렬하는 알고리즘
-
MergeSort와의 차이점 1
- MergeSort는 그냥 두 부분으로 나누는 반면에, QuickSort는 분할할 때,
기준 피봇(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다. -
MergeSort와의 차이점 2
- 각 부분 정렬이 끝난 후, MergeSort는 "Merge"이란 후처리 작업이 필요하나,
QuickSort는 필요로 하지 않는다.
.
- 시간복잡도 O(n²)
- MergeSort보다 빠르지 않지만 평균 시간 복잡도가 nlogn이기 때문에 평균적으로 가장 빠르다.
구현코드
package Stack2;
import java.util.Arrays;
public class QuickSort2 {
//퀵소트
public static int[] a = {69, 10, 30, 2, 16, 8, 31, 22};
public static int hoare(int begin, int end) {
int P = a[begin];
int L = begin;
int R = end;
while(L<R) {
while(a[L]<= P && L<end ) L++;
while(a[R]> P && begin<R) R--;
if(L<R) {
int T = a[R]; a[R] = a[L]; a[L] = T;
}
}
int T = a[R]; a[R] = a[begin]; a[begin] = T;
return R;
}
public static void quick(int begin, int end) {
if(begin < end) {
int p = hoare(begin, end);
quick(begin,p-1);
quick(p+1,end);
}
}
public static void main(String[] args) {
System.out.println(Arrays.toString(a));
quick(0,a.length-1);
System.out.println(Arrays.toString(a));
}
}
반응형
'1. 알고리즘 이론 > 3. 정렬' 카테고리의 다른 글
병합정렬(MergeSort) (0) | 2020.03.01 |
---|---|
카운팅정렬(CountingSort) (0) | 2020.03.01 |
삽입정렬(InsertionSort) (0) | 2020.03.01 |
선택정렬(SelectionSort) (0) | 2020.03.01 |
버블정렬(BubbleSort) (0) | 2020.03.01 |