Sắp xếp bên ngoài là một loại thuật toán sắp xếp có thể sắp xếp một lượng lớn dữ liệu. Kiểu sắp xếp này được áp dụng trên tập dữ liệu thu được bộ nhớ lớn không thể chứa trong bộ nhớ chính (RAM) và được lưu trữ trong bộ nhớ phụ (đĩa cứng).
Ý tưởng sắp xếp được sử dụng trong sắp xếp bên ngoài khá giống với sắp xếp hợp nhất. Trong cũng có hai giai đoạn như trong sắp xếp hợp nhất,
Trong giai đoạn sắp xếp, tập dữ liệu kích thước bộ nhớ nhỏ được sắp xếp và sau đó trong giai đoạn hợp nhất , chúng được kết hợp thành một tập dữ liệu duy nhất.
Sắp xếp bên ngoài
Đối với một tập dữ liệu khổng lồ không thể được xử lý trong một lần. Dữ liệu được chia thành nhiều phần nhỏ. Các phần này được sắp xếp và sau đó được lưu trữ trong các tệp dữ liệu.
Thuật toán:
Bước 1: đọc dữ liệu đầu vào từ tệp và nhập dữ liệu đó dưới dạng tập dữ liệu có kích thước của bộ nhớ.
Bước 2: Đối với mỗi tập hợp dữ liệu nhỏ này, từng tập hợp dữ liệu trong số chúng được sắp xếp bằng cách sử dụng sắp xếp hợp nhất.
Bước 3: lưu trữ dữ liệu đã được sắp xếp vào một tệp.
Bước 4: Hợp nhất từng tệp dữ liệu đã sắp xếp.
Chương trình minh họa hoạt động của Thuật toán:
Ví dụ
#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;
} Dữ liệu đầu vào là tệp dữ liệu không có thứ tự trong khi đầu ra sẽ có mảng được sắp xếp.