퀵 정렬(Quick Sort) 이란 주어진 입력리스트를 특정한 키(Control Key, Pivot)로 분리하여 왼쪽에는 키 값보다 작은 값, 우측에는 키 값보다 큰 값을 갖는 서브 리스트로 분리한다. 그런 다음 각각의 서브리스트에서도 같은 방법을 반복적으로 수행하여 정렬하는 방법이다.
분할교환정렬 이라고도 한다.
오라클자바커뮤니티에서 설립한 개발자실무교육 6년차 오엔제이프로그래밍
실무교육센터
(신입사원채용무료교육, 오라클, SQL, 튜닝, 자바, 스프링, Ajax, jQuery, 안드로이드, 아이폰, 닷넷, C#,
ASP.Net) www.onjprogramming.co.kr
평균적인 수행시간은 O(Nlog N) 이지만 최악의 경우(역순) O(N2)의 효율을 나타낸다.
//퀵 정렬(재귀방법)
int[] qsort(int a[]) {
//low와 high 값을 parameter로 던지자.
quicksort(0, a.length-1, a); return a;
}
void quicksort(int low, int high, int[] a) {
if (low < high){
int pivot = split(low, high, a); //quick sort후 서브리스트로 분
quicksort(low, pivot-1, a); //생성된 pivot값을 기준으로 재귀호출
quicksort(pivot+1, high, a);
}
}
int[] qsort(int a[]) {
//low와 high 값을 parameter로 던지자.
quicksort(0, a.length-1, a); return a;
}
void quicksort(int low, int high, int[] a) {
if (low < high){
int pivot = split(low, high, a); //quick sort후 서브리스트로 분
quicksort(low, pivot-1, a); //생성된 pivot값을 기준으로 재귀호출
quicksort(pivot+1, high, a);
}
}
//pivot 값이 제위치에 정렬되도록 위치를 계산하고 입력된 레코드를 재배열
private int split(int low, int high, int[] a) {
int avg = (low + high)/2; //pivot위치를 찾는다.
exchange(low, avg, a);
int last = low;
for(int i=low+1; i<=high; i++) {
//i값이 pivot값(low위치 값) 보다 작으면 바꾼다.
//last를 1증가후 i위치값과 low위치값을 바꿈
if (a[i] < a[low]){
last++; exchange(last, i, a);
}
}
exchange(low, last, a);
return last;
}
private void exchange(int low, int high, int[] a) {
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
댓글 없음:
댓글 쓰기