C 배열 정렬 알고리즘 구현부터 응용 예시까지

배열 정렬은 C 언어로 알고리즘을 학습할 때 가장 먼저 접하게 되는 핵심 주제입니다. 간단한 예시부터 고급 기법까지, 배열의 원소를 오름차순 또는 내림차순으로 정렬하는 방법을 익히는 과정에서 포인터, 메모리 관리, 함수 활용 등 C의 기초 문법과 로직 설계의 중요성을 자연스럽게 체득할 수 있습니다.

목차

버블 정렬: 교환 방식의 이해와 구현


버블 정렬(Bubble Sort)은 인접한 원소 쌍을 비교하고, 조건에 맞지 않으면 교환(Swap)하는 과정을 반복해 전체 배열을 정렬하는 대표적 교환 방식 알고리즘입니다. 특징은 구현이 간단하고 직관적이지만, 배열 크기가 커질수록 상대적으로 처리 시간이 길어집니다.

버블 정렬의 기본 개념


버블 정렬은 각 단계에서 배열의 인접한 두 원소를 비교합니다. 만약 정렬 순서에 맞지 않으면 두 원소의 위치를 바꾸어 원하는 순서를 만들어 나갑니다. 예를 들어 오름차순 정렬의 경우, 앞의 원소가 뒤의 원소보다 더 크다면 둘의 위치를 교환하게 됩니다.

단계별 작동 방식

  1. 첫 번째 반복에서, 인접 원소들을 순서대로 비교·교환해 가장 큰(또는 작은) 원소가 맨 끝에 위치합니다.
  2. 두 번째 반복에서는 마지막 위치를 제외한 나머지 원소들에 대해 동일한 과정을 반복합니다.
  3. 모든 원소가 올바른 위치에 정렬될 때까지 위 과정을 되풀이합니다.

버블 정렬 구현 예시 (C 언어)


아래 예시 코드는 배열 arr에 대해 버블 정렬을 수행하는 간단한 함수입니다.

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            // 오름차순 기준: 앞 원소가 더 클 경우 교환
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    printf("정렬된 배열: ");
    for(int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

시간 복잡도와 특징

  • 최악의 경우와 평균 시간 복잡도: O(n²)
  • 구현이 직관적이고 코드가 간결
  • 비교 및 교환 과정이 많아 배열 크기가 클 때는 비효율적

버블 정렬은 학습 목적으로는 훌륭하지만, 실제 대용량 데이터 처리 시에는 더 효율적인 다른 정렬 알고리즘을 고려해야 합니다.

선택 정렬: 최소값 선택 로직 구현


선택 정렬(Selection Sort)은 매 단계마다 현재 위치를 기준으로 배열의 나머지 부분 중 최솟값(또는 최댓값)을 찾아 위치를 바꾸는 방식으로 동작합니다. 버블 정렬처럼 단순하지만, 매번 필요한 교환 횟수가 비교적 적어 실제 실행 시 조금 더 효율적일 수 있습니다.

선택 정렬의 기본 개념


선택 정렬은 크게 다음과 같은 과정을 거칩니다. 정렬을 원하는 배열에서 첫 번째 원소를 기준으로, 나머지 원소 중 최솟값을 찾아 두 원소를 교환합니다. 그 후 두 번째 원소를 기준으로 다시 나머지 원소 중 최솟값을 찾아 교환하는 과정을 배열의 끝까지 반복합니다.

단계별 알고리즘 흐름

  1. i = 0부터 시작하여 n-1까지 반복
  2. i번째 원소를 기준으로 i+1부터 n-1까지 순회하며 최소값을 찾음
  3. 찾은 최솟값을 i번째 원소와 교환
  4. i를 1 증가시킨 뒤 같은 과정을 끝까지 반복

선택 정렬 구현 예시 (C 언어)


아래 예시는 배열 arr을 오름차순으로 정렬하는 간단한 선택 정렬 함수입니다.

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        // 나머지 범위에서 최솟값 인덱스 찾기
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // i번째 원소와 최솟값 위치 교환
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {8, 3, 7, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    printf("정렬된 배열: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

시간 복잡도와 특징

  • 평균 및 최악의 경우 시간 복잡도: O(n²)
  • 불필요한 교환이 상대적으로 적고 구현이 직관적
  • 큰 데이터셋에서는 더 효율적인 다른 알고리즘을 고려해야 함

삽입 정렬: 부분 배열에 대한 반복 삽입


삽입 정렬(Insertion Sort)은 이미 정렬된 부분 배열에 새로운 원소를 적절한 위치에 삽입해 정렬을 유지하는 방식으로 동작합니다. 초기에는 배열의 첫 번째 원소만이 “정렬된 상태”이며, 두 번째 원소부터 차례로 나머지 원소를 삽입해 전체 배열이 오름차순(또는 내림차순) 순서를 갖도록 합니다.

삽입 정렬의 기본 개념

  1. 배열에서 두 번째 원소(인덱스 1)부터 시작합니다.
  2. 해당 원소를 임시 변수(key)에 저장하고, 그보다 앞에 있는 원소들이 key보다 큰(또는 작은) 경우 한 칸씩 뒤로 이동시킵니다.
  3. 적절한 위치에 key를 삽입해 정렬 상태를 유지합니다.
  4. 다음 원소로 이동하며 이 과정을 배열의 끝까지 반복합니다.

삽입 정렬 구현 예시 (C 언어)

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        // key가 정렬된 부분 배열의 원소보다 작다면 한 칸씩 뒤로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 이동이 끝난 지점에 key 삽입
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {4, 1, 3, 9, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    printf("정렬된 배열: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

시간 복잡도와 특징

  • 평균 및 최악의 경우 시간 복잡도: O(n²)
  • 자료의 일부만 변경되는 상황에서 비교적 효율적
  • 버블 정렬이나 선택 정렬보다 구현이 조금 더 복잡하지만, 정렬되어 있는 구간이 늘어나면서 재배치를 최소화해 나가는 개념이 핵심입니다.

병합 정렬: 분할과 정복 개념 적용


병합 정렬(Merge Sort)은 분할(Divide)과 정복(Conquer) 전략을 사용해 배열을 효율적으로 정렬하는 알고리즘입니다. 배열을 일정하게 분할한 뒤 각 부분을 정렬하고, 이를 병합(Merge)하는 과정으로 전체를 오름차순 또는 내림차순으로 정렬합니다. 배열 크기가 클수록 그 진가를 발휘하며, 구현은 다소 복잡하지만 높은 효율을 제공합니다.

병합 정렬의 기본 개념

  1. 분할(Divide): 정렬할 배열을 반으로 나누어 각각을 재귀적으로 정렬
  2. 정복(Conquer): 정렬된 두 부분 배열을 하나로 합치면서 전체를 정렬

이 과정을 재귀적으로 반복하며, 배열의 길이가 1이 될 때까지 쪼갠 후 다시 병합을 수행합니다.

병합 절차

  • 두 부분 배열이 각각 정렬되어 있다는 가정 하에, 두 배열의 가장 앞 원소끼리 비교해 더 작은 원소를 결과 배열에 삽입합니다.
  • 어느 한 쪽 배열이 먼저 모두 처리되면, 나머지 배열의 원소를 순서대로 결과 배열 뒤에 붙입니다.

병합 정렬 구현 예시 (C 언어)


아래 코드는 배열을 분할하고 병합하는 과정을 통해 오름차순 정렬을 수행합니다.

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    int temp[right - left + 1];

    // 두 부분 배열을 비교해 더 작은 원소부터 temp에 복사
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 남은 원소 처리
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // temp 배열을 원본 배열로 복사
    for (int t = 0; t < k; t++) {
        arr[left + t] = temp[t];
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        // 분할
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 병합
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {10, 3, 7, 15, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    printf("정렬된 배열: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

시간 복잡도와 특징

  • 최선·평균·최악 시간 복잡도: O(n log n)
  • 안정 정렬(Stable Sort)이며, 분할과 병합을 위한 추가 메모리 공간을 사용
  • 대규모 데이터 정렬 시에도 일정한 성능을 보여주어, 실무에서도 널리 활용됨

퀵 정렬: 피벗을 활용한 빠른 정렬


퀵 정렬(Quick Sort)은 평균적으로 O(n log n)의 시간 복잡도를 가지는 정렬 알고리즘으로, 병합 정렬처럼 분할과 정복을 이용합니다. 배열에서 특정 원소를 피벗(Pivot)으로 선택한 뒤, 피벗보다 작은 원소들은 왼쪽 부분 배열, 큰 원소들은 오른쪽 부분 배열에 위치시키고, 각 부분 배열에 대해 같은 과정(재귀 호출)을 반복해 정렬합니다.

퀵 정렬의 기본 개념


일반적으로 피벗을 어떻게 선택하느냐가 성능에 큰 영향을 미칩니다. 가장 단순하게는 배열의 첫 번째 혹은 마지막 원소를 피벗으로 선택할 수 있지만, 무작위 피벗(Random Pivot)이나 중앙값(Median of Three) 기법 등을 활용하면 최악의 경우(O(n²))가 발생하는 확률을 낮출 수 있습니다.

퀵 정렬 구현 예시 (C 언어)

#include <stdio.h>

// 피벗을 기준으로 배열을 분할하는 함수
int partition(int arr[], int left, int right) {
    int pivot = arr[right]; // 간단하게 배열의 마지막 원소를 피벗으로 선택
    int i = left - 1;       // i는 피벗보다 작은 원소들의 끝 지점을 가리킴
    int temp;

    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            // arr[i]와 arr[j]를 교환
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 피벗을 올바른 위치로 이동
    temp = arr[i + 1];
    arr[i + 1] = arr[right];
    arr[right] = temp;

    return (i + 1);
}

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        // partition 함수로 피벗의 위치를 구한 뒤,
        // 왼쪽과 오른쪽 부분 배열을 재귀적으로 정렬
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

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

    quickSort(arr, 0, n - 1);

    printf("정렬된 배열: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

퀵 정렬의 특징


퀵 정렬은 배열을 분할해가면서 정렬하는 방식이므로, 재귀 함수를 통해 구현할 때 직관적입니다. 평균적으로 O(n log n)의 훌륭한 성능을 보이지만, 피벗 선택이 좋지 않을 경우 O(n²)까지 시간이 소요될 수 있습니다. 또한 대부분의 구현이 제자리 정렬(In-place Sort)이라는 점에서 추가 메모리 사용량이 적다는 장점이 있습니다.

오름차순·내림차순 구현 및 비교


일반적으로 정렬 알고리즘은 오름차순(작은 값에서 큰 값으로) 정렬을 기본으로 설명합니다. 하지만 내림차순(큰 값에서 작은 값으로) 정렬도 원리는 동일하며, 비교 연산의 방향만 반대로 설정해 주면 됩니다.

오름차순 vs. 내림차순

  • 오름차순: 예를 들어 버블 정렬의 경우, 현재 원소가 다음 원소보다 크다면 교환합니다. 삽입 정렬에서는 이미 정렬된 부분 배열의 원소가 새로운 원소보다 크면 뒤로 이동합니다.
  • 내림차순: 오름차순 로직에서 비교 연산자를 반대로 설정하거나, 최솟값 대신 최댓값을 찾도록 변경해주면 됩니다.

간단 코드 비교 예시 (C 언어)


다음 예시는 버블 정렬을 기준으로 오름차순과 내림차순을 구현한 예시입니다.

#include <stdio.h>

void bubbleSortAscending(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 오름차순에서 arr[j]가 arr[j+1]보다 크면 교환
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void bubbleSortDescending(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {
                // 내림차순에서 arr[j]가 arr[j+1]보다 작으면 교환
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arrAsc[] = {10, 5, 7, 2, 9};
    int arrDesc[] = {10, 5, 7, 2, 9};
    int n = sizeof(arrAsc) / sizeof(arrAsc[0]);

    bubbleSortAscending(arrAsc, n);
    bubbleSortDescending(arrDesc, n);

    printf("오름차순 정렬: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arrAsc[i]);
    }

    printf("\n내림차순 정렬: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arrDesc[i]);
    }
    return 0;
}

장단점 비교

  • 오름차순
  • 일반적인 상황에서 많이 사용
  • 알고리즘 학습과 구현에 대한 자료가 풍부
  • 내림차순
  • 특정 상황(예: 점수가 높은 순서로 정렬 등)에 유용
  • 오름차순 알고리즘에서 비교 연산자를 반대로 바꿔주면 동일하게 적용 가능

정렬 알고리즘을 응용할 때, 오름차순과 내림차순 모두를 자유롭게 구현할 수 있도록 비교 연산자만 유연하게 변경해 줄 수 있으면 됩니다.

배열 정렬 응용 예시와 연습 문제


정렬 알고리즘은 단순히 배열의 순서를 바꾸는 데 그치지 않고, 탐색(Search)이나 통계적 계산 등 다양한 응용에서 활용됩니다. 예를 들어 학생 점수를 정렬한 뒤 특정 범위에 속한 학생만 골라내거나, 쇼핑몰 상품 데이터를 정렬해 가격대별로 나눠 볼 수 있습니다. 정렬 과정을 여러 알고리즘으로 구현해 보면서 C 언어의 함수, 반복문, 조건문 이해도를 높일 수 있습니다.

정렬 후 탐색 예시


정렬된 배열 위에서 이진 탐색(Binary Search) 알고리즘을 사용하면, 찾고자 하는 값의 위치를 O(log n) 시간 안에 효율적으로 확인할 수 있습니다. 아래 예시 코드는 오름차순으로 정렬된 배열을 대상으로 특정 값을 이진 탐색하는 간단한 구조입니다.

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 찾지 못한 경우
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;

    // 이미 정렬된 상태로 가정
    int index = binarySearch(arr, n, key);

    if (index != -1) {
        printf("%d는 배열의 %d번 인덱스에 있습니다.\n", key, index);
    } else {
        printf("%d를 배열에서 찾을 수 없습니다.\n", key);
    }
    return 0;
}

응용 시나리오

  • 학생 성적 관리 프로그램: 특정 과목 점수만 따로 정렬하고, 등수 확인하기
  • 파일 데이터 처리: 대규모 데이터(예: 로그 파일)를 정렬한 뒤, 특정 패턴이나 구간만 분석

연습 문제

  1. 혼합 정렬: 큰 배열에서 절반은 퀵 정렬로, 나머지 절반은 병합 정렬로 처리한 뒤 결과를 하나의 배열로 병합하는 방법을 고민해 보세요.
  2. 가변 길이 배열 정렬: 사용자로부터 배열의 길이와 원소를 입력받은 뒤, 원하는 정렬 방식(버블·삽입·퀵 등)을 선택해 정렬 결과를 출력해 보세요.
  3. 내림차순 이진 탐색: 배열을 내림차순으로 정렬한 뒤, 기존의 이진 탐색 코드를 수정해 올바른 인덱스를 찾도록 만들어 보세요.

위 연습 문제들은 배열 정렬에 대한 이해를 확장시켜 줄 뿐 아니라, 실제 코드 작성과 응용 상황에서 마주칠 수 있는 구현상의 문제를 파악하고 해결하는 능력도 기를 수 있습니다.

에러 상황 예측과 디버깅 접근법


정렬 알고리즘을 구현하다 보면, 의외로 사소한 실수나 논리적 오류로 인해 결과가 엉뚱하게 나오는 경우가 많습니다. 예를 들어, 배열의 인덱스를 잘못 접근하거나 교환 조건이 반대로 설정되어 무한 루프가 발생하는 오류가 대표적입니다. 이러한 문제 상황을 미리 예측하고, 디버깅 과정을 체계적으로 접근하면 시간을 절약할 수 있습니다.

대표적 에러 상황과 예방법

  • 인덱스 범위 초과: 배열 범위를 벗어난 접근은 프로그램 충돌(세그멘테이션 폴트)을 유발합니다. 반복문의 종료 조건을 점검하고, 정렬 알고리즘 구현 시 i와 j 같은 변수를 주의 깊게 확인해야 합니다.
  • 비교 조건의 반대 설정: 오름차순과 내림차순을 혼동해 반대로 교환하거나, 부등호를 잘못 사용하면 원하는 정렬 순서를 얻을 수 없습니다. 정렬 목적(오름차순 또는 내림차순)을 먼저 명확히 정의한 뒤 로직을 구성해야 합니다.
  • 무한 루프: 반복문의 인덱스가 정상적으로 감소(또는 증가)되지 않거나, 재귀 호출 종료 조건이 적절히 설정되지 않으면 무한 루프가 발생할 수 있습니다. 정렬 함수 내부에서 탈출 조건을 반드시 확인해야 합니다.

디버깅 접근법

  • 출력문 활용: 각 반복문의 순회마다 중간 결과(배열 상태)를 printf로 확인해 보는 것이 가장 간단한 방법입니다. 정렬 과정의 변화를 추적하면서 어디서 로직이 어긋나는지 빠르게 확인할 수 있습니다.
  • 디버거 사용: GDB 같은 디버거 도구를 활용하면, 코드가 실행되는 과정을 단계별로 추적할 수 있습니다. 변수의 값 변화, 함수 호출 스택, 메모리 상태 등을 확인하여 오류 지점을 정확히 파악할 수 있습니다.
  • 소규모 데이터 테스트: 먼저 작은 크기의 배열로 정렬을 실행해 본 뒤, 작동이 정상적임을 확인하면 점진적으로 배열 크기를 늘려 가며 검증하는 방식이 좋습니다.
  • 단계별 검증: 버블 정렬, 삽입 정렬 등 단계가 비교적 단순한 알고리즘으로 먼저 로직을 확인해 보고, 병합 정렬이나 퀵 정렬처럼 구조가 복잡한 알고리즘으로 넘어가면 오류를 최소화할 수 있습니다.

정렬 알고리즘을 구현할 때는 단순한 실수로도 올바른 결과를 얻지 못하는 경우가 자주 생깁니다. 에러 상황을 미리 예측하고 적절한 디버깅 접근법을 습득하면 문제를 빠르게 해결하는 것은 물론, C 언어 프로그래밍 능력도 한층 더 향상시킬 수 있습니다.

요약


본 기사에서는 C 언어 배열 정렬 알고리즘의 구현, 장단점, 디버깅 방법까지 살펴보았습니다. 각 알고리즘 특성과 효율성을 비교함으로써 상황에 맞는 정렬 방식을 선택할 수 있는 능력을 기를 수 있습니다.

목차