การเรียงลำดับภายนอกด้วยตัวอย่างใน C++

การเรียงลำดับภายนอก เป็นหมวดหมู่ของอัลกอริธึมการเรียงลำดับที่สามารถจัดเรียงข้อมูลจำนวนมากได้ การเรียงลำดับประเภทนี้ใช้กับชุดข้อมูลที่ได้รับหน่วยความจำขนาดใหญ่ซึ่งไม่สามารถเก็บไว้ในหน่วยความจำหลัก (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;
}

ข้อมูลที่ป้อนเข้าเป็นไฟล์ข้อมูลที่ไม่เรียงลำดับในขณะที่เอาต์พุตจะมีอาร์เรย์ที่จัดเรียง