Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 외부 정렬(External Sorting) 완벽 가이드: 개념부터 실전 예제까지

외부 정렬(External Sorting)이란?

외부 정렬(External Sorting)은 대용량 데이터를 정렬할 수 있도록 설계된 정렬 알고리즘의 한 범주입니다. 일반적인 내부 정렬은 데이터 전체를 주 메모리(RAM)에 올려 처리하지만, 외부 정렬은 주 메모리에 한 번에 담을 수 없을 만큼 방대한 데이터셋을 다룰 때 사용됩니다. 이 경우 데이터는 보조 기억 장치(하드 디스크)에 저장된 상태에서 정렬이 진행됩니다.

빅데이터 처리, 데이터베이스 시스템, 로그 파일 정렬 등 디스크 기반 대규모 데이터를 다루는 환경에서 필수적으로 활용되는 기법입니다.

외부 정렬의 동작 원리

외부 정렬의 핵심 아이디어는 병합 정렬(Merge Sort)과 매우 유사하며, 역시 두 단계로 구성됩니다.

  • 정렬 단계(Sort Phase): 메모리에 들어갈 만큼 작은 크기의 데이터셋으로 나눈 뒤, 각각을 개별적으로 정렬합니다.
  • 병합 단계(Merge Phase): 정렬된 여러 개의 데이터 조각을 하나의 정렬된 데이터셋으로 합칩니다.

즉, 한 번에 처리할 수 없는 거대한 데이터셋은 먼저 작은 덩어리(chunk)로 분할되고, 각 덩어리는 정렬된 후 별도의 데이터 파일로 저장됩니다. 이후 이 파일들을 다시 병합하여 최종 결과를 얻습니다.

알고리즘 단계

  1. 1단계: 파일에서 입력 데이터를 읽어 메모리 크기만큼씩 데이터셋으로 나누어 입력받습니다.
  2. 2단계: 각각의 작은 데이터셋을 병합 정렬(Merge Sort)을 사용해 정렬합니다.
  3. 3단계: 정렬된 데이터를 임시 파일에 저장합니다.
  4. 4단계: 정렬된 모든 데이터 파일을 k-way 병합(k-way merge) 방식으로 하나로 합칩니다.

C++ 구현 예제

다음은 위 알고리즘의 동작을 보여주는 C++ 프로그램입니다. 최소 힙(Min Heap)을 활용해 여러 개의 정렬된 파일을 효율적으로 병합하는 것이 특징입니다.

#include <bits/stdc++.h>
using namespace std;

struct MinHeapNode {

    int element;
    int i;
};

void swap(MinHeapNode* x, MinHeapNode* y);

class MinHeap {

    MinHeapNode* harr;
    int heap_size;

    public:
        MinHeap(MinHeapNode a[], int size);
        void MinHeapify(int);
        int left(int i) {
            return (2 * i + 1);
        }
        int right(int i) {
            return (2 * i + 2);
        }
        MinHeapNode getMin() {
            return harr[0];
        }
        void replaceMin(MinHeapNode x) {
            harr[0] = x;
            MinHeapify(0);
        }
};

MinHeap::MinHeap(MinHeapNode a[], int size) {

    heap_size = size;
    harr = a;
    int i = (heap_size - 1) / 2;
    while (i >= 0) {
        MinHeapify(i);
        i--;
    }
}

void MinHeap::MinHeapify(int i) {

    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l].element < harr[i].element)
        smallest = l;
    if (r < heap_size && harr[r].element < harr[smallest].element)
        smallest = r;
    if (smallest != i) {
        swap(&harr[i], &harr[smallest]);
        MinHeapify(smallest);
    }
}

void swap(MinHeapNode* x, MinHeapNode* y)
{
    MinHeapNode temp = *x;
    *x = *y;
    *y = temp;
}

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {

    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

FILE* openFile(char* fileName, char* mode)
{
    FILE* fp = fopen(fileName, mode);
    if (fp == NULL) {
        perror("Error while opening the file.\n");
        exit(EXIT_FAILURE);
    }
    return fp;
}

void mergeData(char* opFile, int n, int k) {

    FILE* in[k];
    for (int i = 0; i < k; i++) {
        char fileName[2];
        snprintf(fileName, sizeof(fileName), "%d", i);
        in[i] = openFile(fileName, "r");
    }
    FILE* out = openFile(opFile, "w");
    MinHeapNode* harr = new MinHeapNode[k];
    int i;
    for (i = 0; i < k; i++) {
        if (fscanf(in[i], "%d ", &harr[i].element) != 1)
            break;
        harr[i].i = i;
    }
    MinHeap hp(harr, i);
    int count = 0;
    while (count != i) {
        MinHeapNode root = hp.getMin();
        fprintf(out, "%d ", root.element);
        if (fscanf(in[root.i], "%d ",
                &root.element)
            != 1) {
            root.element = INT_MAX;
            count++;
        }
        hp.replaceMin(root);
    }
    for (int i = 0; i < k; i++)
        fclose(in[i]);

    fclose(out);
}

void initialiseData( char* ipFile, int memory, int num_ways) {

    FILE* in = openFile(ipFile, "r");
    FILE* out[num_ways];
    char fileName[2];
    for (int i = 0; i < num_ways; i++) {

        snprintf(fileName, sizeof(fileName), "%d", i);
        out[i] = openFile(fileName, "w");
    }
    int* arr = (int*)malloc( memory * sizeof(int));
    bool more_input = true;
    int next_opFile = 0;

    int i;
    while (more_input) {
        for (i = 0; i < memory; i++) {
            if (fscanf(in, "%d ", &arr[i]) != 1) {
                more_input = false;
                break;
            }
        }
        mergeSort(arr, 0, i - 1);
        for (int j = 0; j < i; j++)
            fprintf(out[next_opFile], "%d ", arr[j]);
        next_opFile++;
    }
    for (int i = 0; i < num_ways; i++)
        fclose(out[i]);

    fclose(in);
}

void externalSort( char* ipFile, char* opFile, int num_ways, int memory) {

    initialiseData(ipFile, memory, num_ways);
    mergeData(opFile, memory, num_ways);
}

int main() {

    int num_ways = 10;
    int memory = 1000;

    char ipFile[] = "inputFile.txt";
    char opFile[] = "outputFile.txt";

    FILE* in = openFile(ipFile, "w");

    srand(time(NULL));
    for (int i = 0; i < num_ways * memory; i++)
        fprintf(in, "%d ", rand());
    fclose(in);
    externalSort(ipFile, opFile, num_ways, memory);
    return 0;
}

코드 핵심 요소 살펴보기

  • MinHeapNode / MinHeap 클래스: k-way 병합 단계에서 여러 파일의 현재 값을 관리하는 최소 힙입니다. 힙의 루트에는 항상 가장 작은 값이 위치하며, 이 값을 출력 파일에 기록한 뒤 해당 파일의 다음 값으로 교체합니다.
  • mergeSort / merge 함수: 정렬 단계에서 메모리에 올린 각 데이터 조각을 정렬하는 데 사용되는 표준 병합 정렬 구현입니다.
  • initialiseData 함수: 입력 파일을 메모리 크기(memory)만큼씩 읽어 정렬한 후, 번호가 붙은 임시 파일들에 저장합니다.
  • mergeData 함수: 앞서 생성된 정렬된 파일들을 최소 힙을 이용해 하나의 최종 출력 파일로 병합합니다.
  • main 함수: 난수 10,000개(10개 파일 × 1,000개)를 입력 파일에 생성한 뒤 외부 정렬을 실행합니다.

실행 결과

입력 데이터는 정렬되지 않은 상태의 데이터 파일이며, 프로그램 실행이 완료되면 출력 파일에는 오름차순으로 정렬된 배열이 저장됩니다. 이처럼 외부 정렬은 제한된 메모리 환경에서도 디스크를 활용해 대용량 데이터를 효율적으로 정렬할 수 있는 강력한 방법입니다.