퀵 정렬 (Quick sort) 쉽게 알기

퀵 정렬(Quick sort)

퀵 정렬은 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법입니다.

그렇기에 이름부터가 다소 건방진 '퀵' 정렬인데요. 보통 다른 정렬 방법들은 이름으로부터 어떻게 정렬을 하는지 유추할 수 있습니다. 선택 정렬은 최솟값을 찾아 선택한다고 해서 선택 정렬이라든지 병합 정렬은 병합하면서 정렬한다고 해서 병합 정렬이라든지. 퀵 정렬을 그런 방식으로 이름을 바꾸면 피벗 정렬(pivot sort)이 될 거 같네요. 퀵 정렬은 피벗을 기준으로 목록을 큰 값과 작은 값으로 나누어 가며 정렬하기 때문입니다.

퀵 정렬 예시로 살펴보기

실제 알고리즘을 보면서 어떻게 정렬을 하는지 살펴보죠.

실생활의 예를 들어보려 합니다. 9명의 학생이 운동장에 떠들고 있으니 선생님이 한 마디 합니다.

학창 시절 선생님이 키순으로 서라고 하면 어떻게 하셨나요? 대충 크다 싶으면 뒤로 가고 작다 싶으면 앞으로 가면서 섰던 거 같습니다. 하지만 이번엔 퀵 정렬 방식으로 키순으로 서보려 합니다.

시끄럽던 와중에 제일 뒤에 서 있던 친구가 Pivot! (우리 말로는 기준! 이 되겠네요)을 외치며 자기보다 작은 사람은 자기 앞으로 가고 큰 사람은 자기 뒤로 가라고 합니다.

착한 친구들은 어리둥절하지만 말은 또 잘 듣습니다.

5번 말을 듣고 난 결과입니다. 5번이 똑똑한 친구인 게 5번은 말 한마디로 자기가 서야 될 위치를 찾았습니다. 5번은 자기 위치를 찾았으니 가만히 있으면 됩니다.

하지만 5번만 좋은 건 아닙니다. 기존에는 9명의 친구들이 서로 키를 비교했어야 됐다면 이제는 5번 앞에 있는 친구들은 앞에 친구들끼리, 5번 뒤에 있는 친구들은 뒤에 친구들끼리 정렬하면 됩니다. 5번보다 작은 그룹과 5번보다 큰 그룹으로 나뉘었습니다.

각 그룹에 제일 뒤에 서 있던 3번과 7번은 5번처럼 Pivot! 을 외칩니다. 5번 친구를 보며 느낀 게 있나봅니다. 각 그룹에서 3, 7 보다 작은 친구는 3, 7 보다 앞으로 가고 3,7 보다 큰 친구는 3, 7 보다 뒤로 가게 됩니다.

3번과 7번이 Pivot! 을 외친 결과 3번과 7번도 자기 자리를 찾았습니다. 이번에는 두 명의 학생이 자기 자리를 찾은 셈입니다. 다음에 할 일이 예상되시나요? 1~4번 그룹은 다시 두 그룹으로 나뉘었습니다. 아마 나뉜 두 그룹에서 마지막에 선 친구는 다시 Pivot! 을 외칠 겁니다. 하지만 4번은 혼자 남게 되었으니 더 이상 Pivot! 을 외칠 필요가 없습니다.

마찬가지로 6~9번 그룹도 두 그룹으로 나뉘었습니다. 7보다 큰 그룹에는 두 명이 남았으니 마지막에 선 친구가 Pivot! 을 외치고 6번은 혼자 남았으니 외칠 필요가 없습니다.

1과 9번이 Pivot!을 외칩니다. 9번은 이미 8번이 9번보다 작으니 가만히 있으면 되고 1번과 2번은 순서가 바뀌게 됩니다.

이렇게 되면 키순으로 정렬을 마치게 됩니다.

코드 보기

키순으로 정렬하는 과정에서 재귀적인 형태가 보이시나요?

처음에는 9명의 학생 중 제일 뒤에 있던 5번이 Pivot! 을 외쳤습니다. 그 후에는 5번보다 작은 그룹과 큰 그룹으로 나눠졌습니다. 각 그룹에 가장 뒤에 서 있던 학생은 다시 Pivot! 을 외쳤습니다. Pivot! 을 외칠 때마다 그룹은 두 개로 나눠졌고 나눠진 그룹에서는 또 Pivot! 을 외치는 학생이 나왔습니다.

재귀 호출은 함수가 자기 자신을 호출하는 방식을 말합니다. 자기 자신을 호출하게 되니 같은 일을 반복하게 됩니다. 마치 반복해서 Pivot! 을 외치는 것처럼요. 재귀 호출은 종료 조건이 필요한데 그렇지 않으면 무한히 자기 자신을 호출하게 되기 때문입니다. 여기서 종료 조건은 그룹에 1명이 남았을 때입니다. 한 명이 남았을 때는 더 이상 Pivot! 을 외칠 필요가 없습니다.

이러한 방법은 문제를 2개의 작은 문제로 분할하고 결과를 모아서 문제를 해결한다고 해서 분할 정복 방법이라고도 합니다.

이를 코드로 살펴보면 다음과 같습니다.

#define LENGTH	(9)

void quick_sort(int nums[])
{
    quick_sort_recursive(nums, 0, LENGTH - 1);
}

void quick_sort_recursive(int nums[], int left, int right)
{
    if (left >= right)
    {
        return;
    }

    int pivotPosition = partition(nums, left, right);

    quick_sort_recursive(nums, left, pivotPosition - 1);
    quick_sort_recursive(nums, pivotPosition + 1, right);
}

partition()은 그룹 내 제일 뒤에 있던 학생이 외쳤던 "Pivot! 내 키는 5야. 나보다 작으면 앞으로 가고 크면 뒤로와"를 함수로 구현한 것입니다. partition()은 조금 뒤에서 자세히 살펴보겠습니다.

partition()의 반환 값은 Pivot의 위치입니다. 이를 통해 Pivot 보다 작은 그룹에 대해서 quick_sort_recursive를 호출하고 큰 그룹에 대해서 quick_sort_recursive를 호출합니다.

partition() 함수

5번이 외친 "Pivot! 내 키는 5야. 나보다 작으면 앞으로 가고 크면 뒤로와"는 사실 많은 게 생략되어 있습니다. 위의 예시에서야 학생이니까 5번 말을 듣고 알아서 앞으로 가거나 뒤로 갈 수 있지만 데이터들은 그럴 수 없습니다.

메모리에 있는 데이터들은 알아서 움직일 수 없으므로 직접 값을 비교하며 옮겨주어야 합니다.

여러 가지 방법으로 구현할 수 있겠지만 여기서는 Lomuto(로무토) 분할 방법을 사용하려 합니다.

Lomuto(로무토) 분할 방법은 다음과 같습니다.

배열의 가장 오른쪽 값을 pivot으로 사용

배열의 가장 왼쪽 위치 - 1을 i로 둠

범위 안의 요소들을 pivot 값 전까지 방문

방문한 값(j)와 pivot을 비교해서

pivot 보다 값이 크면 넘어가고
pivot 보다 값이 작으면
- i 위치 1 증가
- i 위치의 값과 방문한 값을 swap

j가 기준값에 도달하면 i를 1 증가하고 i 위치의 값과 pivot을 swap

예시를 통해 살펴보도록 하죠.

보이는 것처럼 기준 값이었던 5 앞에는 5보다 작은 값들이 오고 5 뒤에는 5보다 큰 값들이 오게 됩니다.

이를 코드로 구현하면 다음과 같습니다.

int partition(int nums[], int left, int right)
{
    int pivot = nums[right];

    int i = left - 1;
    for (int j = left; j < right; ++j)
    {
        if (nums[j] < pivot)
        {
            ++i;
            swap(nums, i, j);
        }
    }

    int pivotPosition = i + 1;
    swap(nums, pivotPosition, right);

    return pivotPosition;
}

void swap(int nums[], int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

이로써 퀵 정렬 구현을 마치게 됩니다.

퀵 정렬의 시간 복잡도

퀵 정렬의 평균 시간 복잡도는 O(N * logN)입니다.

매 단계마다 그룹이 균등하게 나뉘면 자리가 정해지는 사람이 1, 2, 4, 8과 같이 지수적으로 증가하므로 단계는 O(logN)이 됩니다. 각 단계마다 방문해야 하는 요소 수는 O(N)이므로 전체 시간 복잡도는 O(N * logN)이 됩니다.

하지만 Pivot 값이 그룹 내의 가장 큰 값이나 작은 값이 되면 단계는 O(N)이 되고 퀵 정렬의 최악의 시간 복잡도는 O(N^2)이 됩니다.

최악의 상황을 피하기 위해 Pivot 값을 제일 마지막이 아닌 다른 위치로 뽑을 수 있습니다. 하지만 100프로 방지는 안되므로 O(N^2)을 허용할 수 없으면 다른 정렬 방법을 택해야 합니다.

전체 코드 보기

#include <stdio.h>

#define LENGTH (9)

void quick_sort(int nums[]);
void quick_sort_recursive(int nums[], int left, int right);
int partition(int nums[], int left, int right);
void swap(int nums[], int i, int j);

int main(void)
{
    int nums[] = {2, 4, 7, 9, 1, 3, 6, 8, 5};
    quick_sort(nums);

    for (int i = 0; i < LENGTH; ++i)
    {
        printf("%d ", nums[i]);
    }
    printf("\n");
}

void quick_sort(int nums[])
{
    quick_sort_recursive(nums, 0, LENGTH - 1);
}

void quick_sort_recursive(int nums[], int left, int right)
{
    if (left >= right)
    {
        return;
    }

    int pivotPosition = partition(nums, left, right);

    quick_sort_recursive(nums, left, pivotPosition - 1);
    quick_sort_recursive(nums, pivotPosition + 1, right);
}

int partition(int nums[], int left, int right)
{
    int pivot = nums[right];

    int i = left - 1;
    for (int j = left; j < right; ++j)
    {
        if (nums[j] < pivot)
        {
            ++i;
            swap(nums, i, j);
        }
    }

    int pivotPosition = i + 1;
    swap(nums, pivotPosition, right);

    return pivotPosition;
}

void swap(int nums[], int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

저작자표시

'Algorithm' 카테고리의 다른 글

[Python] 파이썬으로 DFS와 BFS 구현하기 (0)	2021.08.18
[Python] 스택, 큐 사용하기 (0)	2021.08.18
C언어로 RSA 암호화 프로그램 만들기 (1)	2021.07.31

Atom's Space

퀵 정렬 (Quick sort) 쉽게 알기