처음하시는 분들을 위한 C언어 기초강의 시즌2 - 40 [정렬 알고리즘(퀵 정렬)]

제 40강) 정렬 알고리즘 - 퀵 정렬

오늘은 정렬 알고리즘의 다섯번째 시간으로 "퀵 정렬"에 대해서 알아봅니다.

기본적으로 퀵 정렬은 배열에서 사용합니다.

(Quick Sort라고 불립니다.)

 

 

퀵 정렬이란

(사진 출처 : 위키 백과 - 퀵정렬)

퀵 정렬은 말 그대로 퀵(Quick), 빠른 정렬입니다.

퀵 정렬은 "분할 정복(Divide and conquer)" 라는 것에 기반한 알고리즘인데요.

말이 어렵지 사실상 합병 정렬의 기본원리를 따릅니다.

퀵 정렬은 "피벗" 이라는 임의의 기준값을 잡게 됩니다.

(이 기준값에 따라서 성능이 좌우됩니다.)

이 임의의 값을 기준으로 큰 값은 피벗의 오른쪽으로, 작은 값은 왼쪽으로 정렬하게 됩니다.

여기서 이동된 값을 다시 오름차순 또는 내림차순으로 정렬하기 위해서 피벗을 제외하고 오른쪽 구역과 왼쪽구역으로 나누어 각 구역에 피벗값을 설정하고 다시 반복하게 됩니다.

 

하지만 위의 방법을 코드로 구현하기 위해서는 2가지의 추가적인 인덱스가 필요하게 됩니다.

위에서는 기본적인 원리를 설명하기 위해서 각 단위당 큰 값을 피벗의 왼쪽에 밀어넣고, 작은 값을 오른쪽에 밀어넣었지만 실제로는 2가지 인덱스를 사용하여 자리바꿈을 합니다.

실질적으로는 위의 그림처럼 맨 앞부터 시작하는 인덱스와 맨 뒤부터 시작하는 인덱스, 2개의 인덱스를 사용하여 먼저 해당 하는 값이 피벗보다 큰지, 혹은 작은지 판단하여 그곳에 인덱스를 멈추고 두 인덱스의 값을 바꿉니다.

(사진 출처 : 위키 백과 - 퀵 정렬)

그렇게 하여 시간 복잡도는 위와 같이 됩니다.

상당히 빠르죠?

 

퀵 정렬 구현

이제 퀵 정렬을 구현하여 봅시다.

퀵 정렬은 기본적으로 "재귀" 방식을 사용합니다.

#include <stdio.h>
#include <stdlib.h>
 
void printArr(int* arr, int length)
{
    printf("arr: ");
    for (int i = 0; i < length; i++)
    {
        printf("%d", arr[i]);
        if (i + 1 < length)
            printf(", ");
        else
            printf("\n");
    }
    printf("\n");
}
 
void quickSort(int* arr, int start, int end)
{
    int pivot = arr[end];           // 피벗 값을 정합니다. 가장 오른쪽으로 정했습니다.
    int left = start;               // 정렬이 시작 위치를 왼쪽부터 진행하는 인덱스변수 left에 저장합니다.
    int right = end - 1;            // 정렬이 끝나는 위치를 오른쪽부터 진행하는 인덱스변수 right에 저장합니다.(피벗 제외)
    int tmp;                        // 값을 스왑하기 위해서 사용할 임시변수
 
    while (left <= right)           // 만약에 왼쪽 인덱스가 오른쪽 인덱스보다 작거나 같을때 계속 반복합니다.
    {
        while (pivot >= arr[left] && left <= end - 1)  // 왼쪽의 인덱스에 위치한 값이 피벗값보다 큰 값을 찾기 위해서 왼쪽에서부터 찾습니다.
            left++;
        while (pivot <= arr[right] && right >= start)  // 오른쪽의 인덱스에 위치한 값이 피벗값보다 작은 값을 찾기위해서 오른쪽에서부터 찾습니다.
            right--;    
        if (left <= right)          // 해당 두 인덱스가 맞는 자리(왼쪽 인덱스가 오른쪽 인덱스보다 작거나 같을때)에 있을 때
        {
            tmp = arr[left];        
            arr[left] = arr[right]; // 왼쪽 인덱스에는 현재 피벗값보다 큰 값이, 오른쪽 인덱스에는 현재 피벗값보다 작은 값이 있기에
            arr[right] = tmp;       // 두 인덱스에 위치한 값을 바꾸어 줍니다.
            left++;
            right--;
        }
    }
                                    
    tmp = arr[end];                 // 최종적으로 right가 가리키는 위치와 right+1이 경곗값이 됩니다.
    arr[end] = arr[right + 1];      // right + 1부터 피벗값보다 큰 값이 들어가게 됩니다.
    arr[right + 1] = tmp;           // 그러므로 피벗값과 right + 1 위치의 값을 바꾸어줍니다.
 
    if (start <= end)
    {
        quickSort(arr, start, right);     // 현재 피벗값은 right + 1에 위치하였으므로 피벗을 제외한 start ~ right 까지 재정렬
        quickSort(arr, right + 2, end);   // right + 2 ~ end 까지 재정렬 합니다.
    }
}
 
int main(void)
{
    int arr[] = { 9,11,8,2,3 };
    int length = sizeof(arr) / sizeof(int);
 
    printf("[정렬 전 배열]\n");
    printArr(arr, length);
 
    quickSort(arr, 0, length - 1);
    
    printf("[정렬 후 배열]\n");
    printArr(arr, length);
 
    return 0;
}

사실상 구현해보니 별거 아니긴 하죠?

 

이번시간에는 성능이 정말 좋은 "퀵 정렬"을 보았습니다.

이 알고리즘은 실제적으로도 사용되는 정렬이니 꼭 숙달하는게 좋습니다.

 

다음 시간에는 힙정렬에 대해서 알아봅니다.