[ 자료구조 ] Quick sort

퀵 정렬 : 특정한 값(Pivot)을 기준으로 큰 숫자와 작은 숫자를 구분하는 정렬입니다.

 - 분할정복 알고리즘을 사용한다.

 - 피봇을 설정하고, data[i] > data[pivot]이고, data[j] < data[pivot]인 i, j를 구한다.

 - i > j 처럼 엇갈린경우, 피봇과 j를 바꾼다.

 - i <= j 이고, data[i] > data[pivot] 이고 data[j] < data[pivot] 인 경우 data[i]와 data[j]를 스왑한다.

 - 재귀 함수를 이용해서, 분할 알고리즘을 실행한다.

int array[10] = { 1, 9, 4, 10, 6, 2, 5, 3, 7, 8 };
 
void quick_sort(int *array, int start, int end)
{
    if (start >= end) // 원소가 1개인 경우
        return;
 
    int pivot = start; // 기준점
    int i = pivot + 1; // 왼쪽 출발 지점
    int j = end; // 오른쪽 출발 지점
    int temp;
 
    while (true) // 포인터가 엇갈릴때까지 반복한다.
    {
        while (i <= end && array[i] <= array[pivot]) // 기준점보다 큰 값을 찾는다.
            i++;
 
        while (j > start&& array[j] >= array[pivot]) // 기준점보다 작은 값을 찾는다.
            j--; 
 
        if (i > j) // 엇갈릴 경우 기준점을 바꾼다.
        {
            temp = array[j];
            array[j] = array[pivot];
            array[pivot] = temp;
 
            quick_sort(array, start, j - 1); // 기준점 기준으로 왼쪽 퀵 정렬
            quick_sort(array, j + 1, end); // 기준점 기준으로 오른쪽 퀵 정렬
            
            return;
        }
        else // i와 j를 바꾼다.
        {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
 
}
 
int main()
{
    quick_sort(array, 0, 9);
 
    return 0;
}