C++ 中的外部排序示例

2023-06-21 10:58:03 176

外部排序 是一类能够对海量数据进行排序的排序算法。这种类型的排序适用于获得无法在主内存(RAM)中保存并存储在辅助内存（硬盘）中的大内存的数据集。

外部排序中使用的排序思想与归并排序非常相似。在合并排序中也有两个阶段，

在排序阶段，对 小内存大小的数据集进行排序，然后在合并阶段，将它们组合成单个数据集。

外部排序

对于无法一次性处理的庞大数据集。数据被分成小块。这些块被排序，然后存储在数据文件中。

算法：

第一步： 从文件中读取输入数据，作为内存大小的数据集输入。

第2步： 对于这些迷你数据集中的每一个，使用归并排序对它们中的每一个进行排序。

第三步： 将排序后的数据存入文件中。
第4步： 合并每个排序后的数据文件。

说明算法工作的程序：

示例

#include 
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;
}

输入数据是无序数据文件，而输出将具有排序数组。

C++ 中的外部排序示例

示例

热门推荐

随机推荐