시소당

알고리즘 - Quick Sort

최신문서는 Joinc wiki 에서 확인하실 수 있습니다.

Quick 정렬은 버블정렬과 함께, 가장 쉽게 응용할 수 있는 정렬기법이다. 평균적으로 O(n log n)번의 비교를 수행하며, 최악의 경우에 O(n^2)의 비교를 수행하도록 되어 있다.

정렬할 데이터가 이미 준비되어 있으며, 모든 데이터를 정렬해야 할경우 가장 빠른 수행속도를 보여주는 알고리즘으로 평가되고 있다.

퀵정렬은 다음과 같은 방식으로 진행이 된다.

1. 주어진 데이터 목록에서 임의의 원소를 고른다. 이 원소를 피봇이라 한다.
   
2. 피봇을 기준으로 피봇의 앞에는 피봇보다 작은 숫자가 오도록 하고, 피봇 뒤에는 피봇보다 큰 원소
   

들이 오도록 한다. 이것을 분할이라고 한다. 분할이 끝난뒤에 피봇은 더 이상 움직일 필요가 없이 그 자리에 고정된다.

1. 1,2의 과정을 재귀수행한다. 한번의 피봇이 선택되어서 분할이 이루어질 때마다. 반드시 고정되는 값이 생성이 되므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
   
   

위의 프로세스가 퀵소트 알고리즘의 핵심으로 머리속으로 이해했다면, 구현하는 것도 그리 어렵지 않을 것이다. 구현에도 몇가지 방법이 있는데, 그 중에서 별도의 버퍼를 필요로 하지 않는 내부분할 퀵소트가 널리 사용되고 있다. 이 방법은 정렬을 위한 임시버퍼를 필요로 하지 않으므로 메모리를 할당하고 유지하기 위한 비용을 고려할 필요가 없다는 장점이 있다.

다음은 C로 작성된 퀵정렬 알고리즘이다.

void quickSort(int numbers[], int array_size);
void q_sort(int numbers[], int left, int right);

void quickSort(int numbers[], int array_size)
{
    q_sort(numbers, 0, array_size -1);
}

void q_sort(int numbers[], int left, int right)
{
    int pivot, l_hold, r_hold;
    l_hold = left;
    r_hold = right;
    pivot = numbers[left]; // 0번째 원소를 피봇으로 선택
    while (left < right)
    {
        // 값이 선택한 피봇과 같거나 크다면, 이동할 필요가 없다
        while ((numbers[right] >= pivot) && (left < right))
            right --;

        // 그렇지 않고 값이 피봇보다 작다면,
        // 피봇의 위치에 현재 값을 넣는다.
        if (left != right)
        {
             numbers[left] = numbers[right];
        }
        // 왼쪽부터 현재 위치까지 값을 읽어들이면서
        // 피봇보다 큰 값이 있다면, 값을 이동한다.
        while ((numbers[left] <= pivot) && (left < right))
            left ++;
        if (left != right)
        {
             numbers[right] = numbers[left];
             right --;
        }
    }
    // 모든 스캔이 끝났다면, 피봇값을 현재 위치에 입력한다.
    // 이제 피봇을 기준으로 왼쪽에는 피봇보다 작거나 같은 값만 남았다.
    numbers[left] = pivot;
    pivot = left;
    left = l_hold;
    right = r_hold;

    // 재귀호출을 수행한다.
    if (left < pivot)
        q_sort(numbers, left, pivot - 1);
    if (right > pivot)
        q_sort(numbers, pivot+1, right);
}

int main(int argc, char **argv)
{
    int data[] = {3,7,8,5,2,1,9,5,4};
    int i;
    quickSort(data, 9);
    for (i =0; i < 9; i++)
    {
        printf("%d\n", data[i]);
    }
}

하나하나씩 따라가는게 퀵소트 알고리즘을 이용하는 가장 좋은 방법이다.



두꺼운 테두리로 둘러쌓인 숫자가 선택된 피벗이다. 빨간색은 피벗보다 큰 원소, 파란색은 피벗보다 작은 원소다.

1. 피벗으로 3을 선택했다.
   
2. 배열의 가장 오른쪽 부터, 피벗보다 작은 수가 있는지 비교한다.
   
3. 1이 피벗보다 작으므로 swap 한다.
   
4. 이제 왼쪽으로 가서, 인덱스를 증가시키면서 피벗보다 큰수가 있는지 확인한다.
   
5. 7이 피벗보다 크므로 swap 한다.
   
6. 다시 오른쪽으로 가서, 인덱스를 감소시키면서 피벗보다 작은 수가 있는지 확인한다.
   
7. 2와 3을 swap 한다.
   
8. 왼쪽에서 인덱스를 증가시키면서 피벗과 비교한다.
   
9. 8이 3보다 크므로 swap 한다.
   
10. 이제 q_sort 함수를 재귀호출한다. 인자는 data[], 3, 9가 될것이다.
    
    
    

퀵소트 wikipedia

• qsort(3)표준 퀵정렬함수
  
• 퀵소트와 Priority큐와의 성능비교

출처 : http://teamblog.joinc.co.kr/yundream/127