다양한 정렬 알고리즘 구현 및 성능 비교

이번 포스팅에서는 대표적인 정렬 알고리즘을 C 언어로 직접 구현하고,
100만 개 데이터를 기준으로 수행 시간을 측정해 비교해보았습니다.

 

실험 환경

• 데이터 개수: 1,000,000개 (난수로 생성)
• 측정 방법: clock() 함수를 이용해 실행 시간 계산

 

구현한 정렬 알고리즘

각 정렬 알고리즘은 별도로 함수를 구현해 테스트했습니다.

1. 선택 정렬 (Selection Sort)

• 모든 요소를 비교하여 가장 작은 값을 선택해 앞으로 보냄
• 시간 복잡도: O(N²)

void selection_sort(int list[], int n) { 
    int i, j, least, tmp;
    for (i = 0; i < n - 1; i++)
    {
        least = i;
        for (j = i + 1; j < n; j++)
            if (list[j] < list[least]) least = j;
        SWAP(list[i], list[least], tmp);
    }
}

 

2. 삽입 정렬 (Insertion Sort)

• 이미 정렬된 구간에 새로운 데이터를 삽입하는 방식
• 시간 복잡도: O(N²)

void insertion_sort(int list[], int n) { 
	int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = list[i];
        for (j = i - 1; j >= 0 && list[j] > key; j--)
            list[j + 1] = list[j];
        list[j + 1] = key;
    }
}

 

 

3. 버블 정렬 (Bubble Sort)

• 인접한 두 데이터를 비교해 작은 값을 앞으로 이동
• 시간 복잡도: O(N²)

void bubble_sort(int list[], int n) { 
    int i, j, tmp;
    for (i = n - 1; i > 0; i--)
    {
        for (j = 0; j < i; j++)
            if (list[j] > list[j + 1])
                SWAP(list[j], list[j + 1], tmp);
    }
}

 

4. 쉘 정렬 (Shell Sort)

• 삽입 정렬의 개선 버전, 일정 간격(gap)으로 나누어 부분 정렬 수행
• 시간 복잡도: O(Nlog²N) ~ O(N¹.³) (gap 설정에 따라 다름)

void inc_insertion_sort(int list[], int first, int last, int gap)
{
    int i, j, key;
    for (i = first + gap; i <= last; i += gap)
    {
        key = list[i];
        for (j = i - gap; j >= first && key < list[j]; j -= gap)
            list[j + gap] = list[j];
        list[j + gap] = key;
    }
}

void shell_sort(int list[], int n)
{
    int i, gap;
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        if (gap % 2 == 0) gap++;
        for (i = 0; i < gap; i++)
            inc_insertion_sort(list, i, n - 1, gap);
    }
}

 

5. 합병 정렬 (Merge Sort)

• 배열을 반씩 나누고, 정렬하며 합치는 분할 정복 기법
• 시간 복잡도: O(NlogN)

void merge(int list[], int left, int mid, int right)
{
    int i = left, j = mid + 1, k = left, l;
    while (i <= mid && j <= right)
    {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
    if (i > mid)
        for (l = j; l <= right; l++)
            sorted[k++] = list[l];
    else
        for (l = i; l <= right; l++)
            sorted[k++] = list[l];

    for (l = left; l <= right; l++)
        list[l] = sorted[l];
}

void merge_sort(int list[], int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        merge_sort(list, left, mid);
        merge_sort(list, mid + 1, right);
        merge(list, left, mid, right);
    }
}

 

6. 퀵 정렬 (Quick Sort)

• 피벗을 기준으로 작은 값과 큰 값을 분할해 재귀적으로 정렬
• 평균 시간 복잡도: O(NlogN)
• 최악의 경우: O(N²)

int partition(int list[], int left, int right)
{
    int pivot = list[left], tmp, low = left, high = right + 1;

    do {
        do low++; while (low <= right && list[low] < pivot);
        do high--; while (high >= left && list[high] > pivot);

        if (low < high) SWAP(list[low], list[high], tmp);
    } while (low < high);

    SWAP(list[left], list[high], tmp);
    return high;
}

void quick_sort(int list[], int left, int right)
{
    if (left < right)
    {
        int q = partition(list, left, right);
        quick_sort(list, left, q - 1);
        quick_sort(list, q + 1, right);
    }
}

 

원본 배열 복사 및 실행시간 측정

void CopyArr(void)
{
    int i;
    for (i = 0; i < n; i++)
        list[i] = original[i];
}

void CalcTime(void)
{
    used_time = finish - start;
    printf("완료!\n소요 시간 : %f sec\n\n", (float)used_time / CLOCKS_PER_SEC);
}

 

전체 메인 함수

void main()
{
    int i;
    n = MAX_SIZE;

    for (i = 0; i < n; i++)
        original[i] = rand();

    printf("데이터의 개수 : %d\n\n", n);

    CopyArr();
    start = clock();
    selection_sort(list, n);
    finish = clock();
    CalcTime();

    CopyArr();
    start = clock();
    insertion_sort(list, n);
    finish = clock();
    CalcTime();

    CopyArr();
    start = clock();
    bubble_sort(list, n);
    finish = clock();
    CalcTime();

    CopyArr();
    start = clock();
    shell_sort(list, n);
    finish = clock();
    CalcTime();

    CopyArr();
    start = clock();
    printf("합병 정렬 중... ");
    merge_sort(list, 0, n - 1);
    finish = clock();
    CalcTime();

    CopyArr();
    start = clock();
    printf("퀵 정렬 중... ");
    quick_sort(list, 0, n - 1);
    finish = clock();
    CalcTime();
}

 

정렬별 수행 시간 비교 (데이터 1,000,000개 기준)

정렬 방법소요 시간 (초)

선택 정렬	44.174 sec
삽입 정렬	39.424 sec
버블 정렬	96.395 sec
쉘 정렬	0.094 sec
합병 정렬	0.093 sec
퀵 정렬	0.048 sec

 

분석 및 정리

• 버블/선택/삽입 정렬은 모두 O(N²) 시간 복잡도를 갖기 때문에, 데이터가 많아질수록 급격히 느려집니다.
• 쉘 정렬은 데이터가 많아도 빠른 편이지만, gap 설정에 따라 성능 차이가 발생할 수 있습니다.
• 합병 정렬과 퀵 정렬은 대량 데이터에서도 매우 빠르게 동작합니다.
  • 특히 퀵 정렬은 최적화가 잘 된 경우 가장 빠른 결과를 보여줬습니다.

 

결론

대량의 데이터를 다룰 때는 반드시 O(NlogN) 수준의 알고리즘(합병정렬, 퀵정렬, 힙정렬 등)을 사용해야 합니다.
기본적인 버블/선택/삽입 정렬은 개념 이해나 소규모 데이터용으로만 사용하는 것이 적합합니다.