외부 정렬 방대한 양의 데이터를 정렬할 수 있는 정렬 알고리즘의 범주입니다. 이 유형의 정렬은 주 메모리(RAM)에 저장할 수 없는 대용량 메모리를 획득하고 보조 메모리(하드 디스크)에 저장되는 데이터 세트에 적용됩니다.
외부 정렬에 사용되는 정렬 개념은 병합 정렬과 매우 유사합니다. 또한 병합 정렬과 같은 두 단계를 가지고 있습니다.
정렬 단계에서 작은 메모리 크기의 데이터 세트는 정렬된 다음 병합 단계에 있습니다. , 이들은 단일 데이터세트로 결합됩니다.
외부 정렬
한 번에 처리할 수 없는 거대한 데이터 세트의 경우. 데이터는 작은 청크로 나뉩니다. 이러한 청크는 정렬된 다음 데이터 파일에 저장됩니다.
알고리즘:
1단계: 파일에서 입력 데이터를 읽어 메모리 크기의 데이터 세트로 입력합니다.
2단계: 이러한 미니 데이터 세트 각각에 대해 병합 정렬을 사용하여 각 데이터 세트를 정렬했습니다.
3단계: 정렬된 데이터를 파일에 저장합니다.
4단계: 정렬된 각 데이터 파일을 병합합니다.
알고리즘의 작동을 설명하는 프로그램:
예
#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;
} 입력 데이터는 정렬되지 않은 데이터 파일인 반면 출력에는 정렬된 배열이 있습니다.