오늘은 퀵 정렬에 대하여 알아보도록 하겠습니다.

개요

퀵 정렬은 정렬할 전체 원소에 대하여 정렬을 수행하는 방식이 아니고, 기준값을 먼저 잡고전체 원소에서 왼쪽 집합과 오른쪽 집합을 분할합니다.

왼쪽 집합에는 기준값보다 작은 원소들을 이동시키고, 오른쪽 집합에는 기준값보다 큰 원소들을 이동시킵니다. 이때 일반적으로 전체 원소중에 가운데 원소를 피벗으로 설정합니다.

퀵 정렬은 두번의 작업을 반복합니다.

1. 정렬할 자료들을 가지고 기준값을 중심으로 2개의 집합을 만듭니다.

2. 두 집합의 원소들을 가지고 기준값보다 작은 원소들은 왼쪽으로 이동시키고, 기준값보다 큰 원소들은 오른족으로 이동시킵니다.

위 과정을 두 집합중에 하나가 1이하가 되면 분할 작업을 멈춥니다.

집합으로 분할하기 위해 보통은 L과 R을 사용합니다.

왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하며 피벗보다 크거나 같은 원소를 찾아 L로 표기하고, 오른쪽 끝에서 왼쪽으로 움직이면서 크기를 비교하며 피벗보다 작은 원소를 찾아 R로 표기하고 두 원소를 서로 교환합니다.

만약 L과 R이 서로 만나면 피봇과 R의 위치를 교환하고 피벗의 위치를 확정합니다.

확정된 피벗의 위치를 기준으로 왼쪽과 오른쪽 집합을 만들어 퀵 정렬을 제귀적으로 수행합니다.

알고리즘

quick(arr[],begin,end){
    if(m<n)then{
        pivoot <- (begin + end)/2;
        l<-begin;
        r<-end;
        while(l<r) do{
            while(arr[l]<arr[pivot]&&l<r) do l++;
            while(arr[l]>=arr[pivot]&&l<r) do r--;
            if(l<r) then{
                swap(arr[l],arr[r]);
            }
        }
        swap(arr[pivot],arr[r]);
        p <- l;
        quick(arr[],begin,p-1);
        quick(arr[],p+1,end);
    }
}

퀵 정렬의 실행 성능은 선택된 피벗에 의해 왼쪽 집합과 오른쪽 집합이 정확히 n/2개 되는 경우에 수행단계가 최소로 되는 경우가 있으며, 1개와 n-1개로 치우쳐있는 경우도 있습니다.

일반적으로 평균 시간 복잡도는 O(n log2 n)입니다.