퀵정렬 (QuickSort)

피봇을 정하여 해당 피봇보다 작은 값을 왼쪽에서부터 찾기 시작.

큰 값을 오른쪽에서부터 찾기 시작.

양쪽에서 진행 중 찾아지는 값들을 서로 위치 변경.

반복 중에 양쪽에서 비교하던 인덱스가 만나면 그 위치와 피봇 값을 교환.

이 과정에서 중간지점으로 이동된 피봇을 중심으로 양쪽에 부분집합이 생긴다.

각 부분집합마다 피봇을 다시 정하여 위의 과정을 반복한다.

자료가 균일하게 분포되어 있으면 log2(n)의 연산 횟수가 필요하다.

매번 정렬시마다 n만큼 비교하므로 O(nlog(n))의 평균 효율을 보인다.

데이터 이동 연산은 비교보다 적게 발생한다.

데이터가 불균형하게 분포되어 있으면 최악의 경우 n(2)의 효율성을 지닌다.

기존 피봇을 재사용하지 않고, 먼 곳에 있는 값을 교환하므로 효율이 우수하다.

최악의 경우 효율이 떨어지므로 일반적으로 피봇값은 데이터 중 중간값으로 한다.

데이터 교환은 계속 일어나므로 불안정 정렬이다.

// 퀵 정렬 함수
void QuickSort(int data[], int startIndex, int endIndex)
{
    int pivot = 0;
 
    // 재귀호출을 감안해서 index 정보를 매개변수로 전달받는다.
    if (startIndex < endIndex)
    {
        // 나누어진 부분에서 startIndex와 endIndex가 만나서 pivot과 교환된 인덱스를 반환.
        pivot = patitionQuickSort(data, startIndex, endIndex);
        // 반환된 pivot 인덱스를 기준으로 quicksort 반복
        QuickSort(data, startIndex, pivot - 1);
        QuickSort(data, pivot + 1, endIndex);
    }
}
 
// 실제 pivot 교환 부분
int patitionQuickSort(int data[], int startIndex, int endIndex)
{
    int pivotIndex = endIndex;
    int leftIndex = startIndex;
    int rightIndex = endIndex;
    int temp = 0;
 
    // 양쪽의 Index가 만나기 전까지 반복
    while (leftIndex < rightIndex)
    {
        // left Index 이동, 두 Index가 만나기 전까지 Pivot보다 큰 값을 찾는다.
        while ((data[leftIndex] < data[pivotIndex]) && (leftIndex < rightIndex))
        {
            leftIndex++;
        }
 
        // right Index 이동, 두 Index가 만나기 전까지 Pivot보다 작은 값을 찾는다.
        while ((data[rightIndex] > data[pivotIndex]) && (leftIndex < rightIndex))
        {
            rightIndex--;
        }
 
        // pivot보다 큰 값인 leftIndex와 작은 값인 rightIndex의 위치 변경.
        if (leftIndex < rightIndex)
        {
            temp = data[leftIndex];
            data[leftIndex] = data[rightIndex];
            data[rightIndex] = temp;
        }
    }
 
    // 두 Index가 만나는 곳과 Pivot의 값 변경
    temp = data[pivotIndex];
    data[pivotIndex] = data[rightIndex];
    data[rightIndex] = temp;
 
    // 새로운 pivot의 위치는 rightIndex이다.
    return rightIndex;
}