알고리즘 퀵 정렬(quick sort) C언어

▶퀵 정렬

재귀 알고리즘이다.

피벗(pivot)을 선택해 피벗보다 작은 원소는 배열의 왼쪽으로, 큰 원소는 배열의 오른쪽으로 이동해 두 부분으로 나눈다.

왼쪽과 오른쪽으로 나눈 부분 배열을 각각 정렬한다.

평균 성능 시간 복잡도 : O(nlogn)

최악 성능 시간 복잡도 : O(n^2)

최선 성능 시간 복잡도 : O(nlogn)

 

▶소스코드

void QuickSort(int arr[], int left, int right)
{
    int L = left, R = right;
    int temp;
    int pivot = arr[(L + R) / 2];

    while (L <= R)
    {
        while (arr[L] < pivot) L++;
        while (arr[R] > pivot) R--;
        if (L <= R)
        {
            if (L != R)
            {
                temp = arr[L];
                arr[L] = arr[R];
                arr[R] = temp;
            }
            L++;
            R--;
        }
    }
    if (L < right) QuickSort(arr, L, right);
    if (R > left) QuickSort(arr, left, R);
}

위 소스는 오름차순 정렬이다.

 

▶해석

퀵 정렬 함수 인자 left, right를 L, R에 저장하여 값이 변해도 상관없도록 한다.

pivot변수는 현재 arr배열의 중앙값을 가리킨다.

int L = left, R = right;
int temp;
int pivot = arr[(L + R) / 2];

 

반복문 조건으로는 계속해서 바뀌는 L, R값을 고려해 L <=R 하여 L값과 R값이 서로를 지나칠 때 부분적으로 배열을 나누기 위해 반복문을 종료한다.

while (L <= R)

 

arr [L] 값이 pivot보다 클 때까지 L++하여 점차 오른쪽으로 움직이고, arr [R] 값 또한 pivot보다 작을 때까지 R--하여 왼쪽으로 움직인다.

중앙값을 기준으로 L은 큰 값을 찾고, R은 작은 값을 찾아서 서로 교환해야 정렬이 이루어지기 때문이다.

while (arr[L] < pivot) L++;
while (arr[R] > pivot) R--;

 

L, R값이 변화하면서 L <=R조건에 만족하는지 확인한 후 둘이 같지 않다면 교환을 해준다.

교환을 하든 안 하든 현재 L, R값은 더 이상 불필요하므로 L++, R--한다.

if (L <= R)
{
    if (L != R)
    {
        temp = arr[L];
        arr[L] = arr[R];
        arr[R] = temp;
    }
    L++;
    R--;
}

 

L++했던 L값이 right를 넘지 않았다면 L ~ right 범위의 부분 배열로 다시 함수를 호출한다. 마찬가지로 R또한 left보다 적지 않다면 left ~ R 범위의 부분배열로 다시 함수를 호출한다.

if (L < right) QuickSort(arr, L, right);
if (R > left) QuickSort(arr, left, R);

 

▶예시

#include <stdio.h>

void QuickSort(int arr[], int left, int right)
{
    int L = left, R = right;
    int temp;
    int pivot = arr[(L + R) / 2];

    while (L <= R)
    {
        while (arr[L] < pivot) L++;
        while (arr[R] > pivot) R--;
        if (L <= R)
        {
            if (L != R)
            {
                temp = arr[L];
                arr[L] = arr[R];
                arr[R] = temp;
            }
            L++;
            R--;
        }
    }
    if (L < right) QuickSort(arr, L, right);
    if (R > left) QuickSort(arr, left, R);
}

int main()
{
    int arr[10] = {5, 3, 7, 6, 1, 9, 0, 2, 8, 4};

    QuickSort(arr, 0, 9);

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

결과

0 1 2 3 4 5 6 7 8 9