[프로그래밍/알고리즘] Quick Sort

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

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

소트효율 

가장 비효율적인 '''버블소트'''는 O(N^2)이고, 퀵소트는 평균 O(NlogN)이다.

아무리 뛰어난 정렬 알고리즘(:12)을 개발한다고 하더라도, 데이터의 갯수가 N이면 O(NlogN)보다 더 좋을 수 없다는 것이 증명되어 있다.

즉 정렬알고리즘의 lower bound는 O(NlogN)이다.

단 최대값이 정해져 있는 데이터라면 counting 방식을 쓸수 있고 - counting sort, bucket sort, radix sort - 이 경우 O(n)이 보장될 것이다.

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

주어진 데이터 목록에서 임의의 원소를 고른다. 이 원소를 피봇이라 한다.

피봇을 기준으로 피봇의 앞에는 피봇보다 작은 숫자가 오도록 하고, 피봇 뒤에는 피봇보다 큰 원소가 오도록한다. 필요할 경우 피봇은 움지일 수 있다.

분할과정을 거치게 됨을 알 수 있다. 분할이 끝난뒤에 피봇은 더 이상 움직일 필요가 없이 그 자리에 고정된다. 흔히 분할정복알고리즘이라고 한다. 퀵소트는 분할정복방식을 쓰는 정렬알고리즘이라고 달리 부를 수 있을 것이다.

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]); 

    } 

}