퀵 정렬은 정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준값을 중심으로왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다. 왼쪽 부분집합에는 기준값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준값보다 큰 원소들을 이동시킨다. 이때 사용하는 기준값을 피봇(Pivot)이라고 하는데, 일반적으로 전체 원소 중에서 가운데에 위치한 원소를 피봇으로 선택한다.
퀵정렬은 다음의 2가지 기본 작업을 반복수행하여 완성한다.
1) 분할(Divide) : 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할한다.
2) 정복(Conquer) : 부분집합의 우너소들 중에서 기준값보다 작은 원소들은 왼쪽 부분집합으로, 기준값보다 큰 원소들은 오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 1이하로 충분히 작지 않으면 순환호출을 이용하여 다시 분할한다.
분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 부분집합과 오른쪽 부분집합을 정렬하는 방법으로 전체 원소들을 정렬한다. 부분집합으로 분할하기 위해서 L과 R을 사용한다.
퀵 정렬을 위한 동작규칙
1. 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피복보다 크거나 같은 원소를 찾아 L로 표시한다.
2. 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시한다. 단, R은 L과 만나면 더 이상 왼쪽으로 이동하지 못하고 멈춘다.
3. 1과 2에서 찾은 L원소와 R원소를 서로 교환한다.
4. L과 R이 같은 원소에서 만나면 피봇과 R의 원소를 서로 교환한다.
5. 3이나 4에서 피봇에 대한 자리 교환이 발생하면, 교환 후의 자리를 피봇의 위치로 확정하고 현재 단계의 퀵 정렬이 끝난다.
6. 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분집합과 오른쪽 부분집합에 대해서 퀵 정렬을 순환적으로 반복 수행하는데, 모든 부분집합의 크기가 1 이하가 되면 퀵 정렬을 종료한다.
시간복작도 : O(nlog2n), 같은 시간 복잡도를 가지는 다른 정렬 방법에 비해 자리교환 횟수를 줄임으로써 실행 시간 성능을 향상시킨 정렬 방법이다.
public class quickSort {
public static void main(String[] args) {
int a[]={69,10,30,16,2,8,31,22};
int size=a.length;
quicksort(a,0,size-1);
}
public static void quicksort(int a[], int begin, int end)
{
if(begin<end){
int p;
p=partition(a,begin,end);
quicksort(a, begin, p-1);
quicksort(a, p+1, end);
}
}
public static int partition(int a[], int begin, int end)
{
int pivot, temp, L, R, t;
L=begin;
R=end;
pivot=(begin+end)/2;
while(L<R){
while((a[L]<a[pivot])&&(L<R)) L++;
while((a[R]>=a[pivot])&&(L<R)) R--;
temp=a[L];
a[L]=a[R];
a[R]=temp;
if(L==pivot){
for(int i=0 ; i<a.length ; i++) System.out.print(a[i]+" ");
System.out.println();
return R;
}
}
temp=a[pivot];
a[pivot]=a[R];
a[R]=temp;
for(int i=0 ; i<a.length ; i++) System.out.print(a[i]+" ");
System.out.println();
return R;
}
}