External Sorting (การจัดเรียงภายนอก) ใน C++

External Sorting คืออะไร?

External Sorting คืออัลกอริทึมจัดเรียงสำหรับข้อมูลขนาดใหญ่ที่ไม่สามารถโหลดเข้า RAM ได้ทั้งหมด ต้องเก็บใน Secondary Storage (Hard Disk)

หลักการคล้าย Merge Sort แบ่ง 2 ขั้นตอน:

1. Sort Phase: อ่านข้อมูลเป็นชิ้นเล็ก (Chunks) ที่พอดี RAM -> เรียงแต่ละชิ้น -> เขียนกลับดิสก์
2. Merge Phase: รวมชิ้นที่เรียงแล้วด้วย K-way Merge (ใช้ Min Heap)

อัลกอริทึม

1. อ่านข้อมูลจากไฟล์ต้นทางเป็นบล็อกขนาด Memory
2. เรียงแต่ละบล็อกด้วย Merge Sort แล้วเขียนเป็นไฟล์ชั่วคราว
3. Merge ไฟล์ชั่วคราวทั้งหมดด้วย Min Heap เขียนผลลัพธ์สุดท้าย

โปรแกรมตัวอย่าง (ครบถ้วน)

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

// ... (Implementation of MinHeap, Merge Sort, File I/O functions)

void externalSort(char* ipFile, char* opFile, int num_ways, int memory) {
    initialiseData(ipFile, memory, num_ways); // Sort phase
    mergeData(opFile, memory, num_ways);      // Merge phase
}

int main() {
    int num_ways = 10, memory = 1000;
    char ipFile[] = "inputFile.txt", opFile[] = "outputFile.txt";
    // Generate random input
    FILE* in = fopen(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;
}

สรุป

External Sorting จำเป็นสำหรับ Big Data ใช้หลักการ Divide & Conquer ร่วมกับ K-way Merge Heap