퀵 정렬 ( Quick Sort )

퀵 정렬 ( Quick Sort )

퀵 정렬은 분할 정복 ( Divide and Conquer ) 방법을 사용하는 정렬 알고리즘이다.

배열에서 피벗 ( Pivot )을 선택하고 , 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한다.

이 과정을 재귀적으로 반복하여 정렬한다.

배열에서 기준값 피벗 ( pivot )을 하나 정한다
피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 보낸다
이렇게 나뉜 두 구간을 다시 퀵 정렬로 정렬한다
더 이상 나눌 수 없을 때까지 재귀적으로 반복한다

 

 

동작 과정

1. 배열에서 하나의 원소를 피벗 ( pivot )으로 선택한다.

2. 피벗보다 작은 원소들은 왼쪽 , 큰 원소들은 오른쪽에 배치한다.

3. 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열을 재귀적으로 정렬한다.

4. 더 이상 분할할 원소가 없으면 정렬이 완료된다.

 

 

의사코드 ( PseudoCode ) 표현

QuickSort(arr, start, end)
    start가 end 이상이면 정렬 종료

    pivot = arr[end]
    i = start - 1

    for (j = start, end 이전까지 반복)
        if (arr[j]가 pivot보다 작거나 같으면)
            i를 1 증가
            arr[i]와 arr[j]를 교환

    arr[i + 1]과 arr[end]를 교환
    pivot 위치는 i + 1로 확정

    QuickSort(arr, start, i)
    QuickSort(arr, i + 2, end)

 

 

 

C# 예제 코드

public static void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivotIndex = Partition(arr, low, high);

        QuickSort(arr, low, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, high);
    }
}

private static int Partition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp2 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp2;

    return i + 1;
}

 

 

정리

- 분할 정복 기반의 효율적인 정렬 알고리즘

- 피벗을 기준으로 배열을 두 부분으로 나누고 재귀적으로 정렬

- 평균적으로 매우 빠르다. in-place 정렬 가능하다

- 최악의 경우 성능 저하, 재귀 호출로 스택 오버플로우 위험