[c++] 외부정렬

12 Dec 2023

외부 정렬은 컴퓨터 프로그램이 주 메모리보다 더 많은 데이터를 정렬해야 할 때 사용하는 정렬 알고리즘의 한 종류입니다. 주로 디스크와 같은 외부 저장 장치를 사용하여 대용량 데이터를 정렬하는 데 사용됩니다.

왜 외부 정렬이 필요한가?

대용량의 데이터를 메인 메모리에 한번에 올릴 수 없는 경우가 많습니다. 만약 모든 데이터를 메모리에 올려서 정렬을 한다면, 대규모의 데이터에 대해서는 메모리 부족 오류가 발생할 수 있습니다. 이런 경우에 외부 정렬이 필요하게 됩니다.

외부 정렬 알고리즘의 예시

가장 널리 사용되는 외부 정렬 알고리즘에는 Merge Sort가 있습니다. 이 알고리즘은 주 메모리를 넘어선 큰 데이터 집합을 정렬하는 데 사용되며, 데이터를 일정한 크기로 나눈 뒤 각각의 부분을 정렬합니다. 이후 병합 단계를 통해 정렬된 데이터를 합칩니다.

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

const int MAX_MEMORY = 10000;

void externalSort(string inputFileName, string outputFileName) {
    ifstream input(inputFileName);
    int fileCount = 0;
    vector<int> buffer(MAX_MEMORY);
  
    while (!input.eof()) {
        int i = 0;
        for (; i < MAX_MEMORY && !input.eof(); ++i) {
            input >> buffer[i];
        }
        sort(buffer.begin(), buffer.begin() + i);
      
        string tempFileName = "temp" + to_string(fileCount) + ".txt";
        fileCount++;
        ofstream tempFile(tempFileName);
        for (int j = 0; j < i; ++j) {
            tempFile << buffer[j] << endl;
        }
    }
  
    // 병합 정렬 단계
    vector<string> fileNames(fileCount);
    for (int i = 0; i < fileCount; ++i) {
        fileNames[i] = "temp" + to_string(i) + ".txt";
    }

    // 병합 정렬을 통해 최종 결과 파일 생성
    ofstream output(outputFileName);
    mergeFiles(fileNames, output);
}

요약

외부 정렬은 대용량의 데이터를 메모리에 올리지 않고도 효율적으로 정렬하는 데 사용되는 알고리즘입니다. Merge Sort와 같은 알고리즘이 주로 활용되며, 외부 저장장치를 사용하여 데이터를 일정한 크기로 잘라 정렬한 뒤 병합하는 방식으로 작동합니다.

왜 외부 정렬이 필요한가?

외부 정렬 알고리즘의 예시

요약

참고 자료