Clasificación externa

CPP

// C++ program to implement
// external sorting using
// merge sort
#include <bits/stdc++.h>
using namespace std;
  
struct MinHeapNode {
    // The element to be stored
    int element;
  
    // index of the array from which
    // the element is taken
    int i;
};
  
// Prototype of a utility function
// to swap two min heap nodes
void swap(MinHeapNode* x, MinHeapNode* y);
  
// A class for Min Heap
class MinHeap {
    // pointer to array of elements in heap
    MinHeapNode* harr;
  
    // size of min heap
    int heap_size;
  
public:
    // Constructor: creates a min
    // heap of given size
    MinHeap(MinHeapNode a[], int size);
  
    // to heapify a subtree with
    // root at given index
    void MinHeapify(int);
  
    // to get index of left child
    // of node at index i
    int left(int i) { return (2 * i + 1); }
  
    // to get index of right child
    // of node at index i
    int right(int i) { return (2 * i + 2); }
  
    // to get the root
    MinHeapNode getMin() { return harr[0]; }
  
    // to replace root with new node
    // x and heapify() new root
    void replaceMin(MinHeapNode x)
    {
        harr[0] = x;
        MinHeapify(0);
    }
};
  
// Constructor: Builds a heap from
// a given array a[] of given size
MinHeap::MinHeap(MinHeapNode a[], int size)
{
    heap_size = size;
    harr = a; // store address of array
    int i = (heap_size - 1) / 2;
    while (i >= 0) {
        MinHeapify(i);
        i--;
    }
}
  
// A recursive method to heapify
// a subtree with root
// at given index. This method
// assumes that the
// subtrees are already heapified
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);
    }
}
  
// A utility function to swap two elements
void swap(MinHeapNode* x, MinHeapNode* y)
{
    MinHeapNode temp = *x;
    *x = *y;
    *y = temp;
}
  
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
  
    /* create temp arrays */
    int L[n1], R[n2];
  
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
  
    /* Merge the temp arrays back into arr[l..r]*/
    // Initial index of first subarray
    i = 0;
  
    // Initial index of second subarray
    j = 0;
  
    // Initial index of merged subarray
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
  
    /* Copy the remaining elements of L[],
        if there are any */
    while (i < n1)
        arr[k++] = L[i++];
  
    /* Copy the remaining elements of R[],
        if there are any */
    while (j < n2)
        arr[k++] = R[j++];
}
  
/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l + (r - l) / 2;
  
        // Sort first and second halves
        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;
}
  
// Merges k sorted files. Names of files are assumed
// to be 1, 2, 3, ... k
void mergeFiles(char* output_file, int n, int k)
{
    FILE* in[k];
    for (int i = 0; i < k; i++) {
        char fileName[2];
  
        // convert i to string
        snprintf(fileName, sizeof(fileName),
                 "%d", i);
  
        // Open output files in read mode.
        in[i] = openFile(fileName, "r");
    }
  
    // FINAL OUTPUT FILE
    FILE* out = openFile(output_file, "w");
  
    // Create a min heap with k heap
    // nodes. Every heap node
    // has first element of scratch
    // output file
    MinHeapNode* harr = new MinHeapNode[k];
    int i;
    for (i = 0; i < k; i++) {
        // break if no output file is empty and
        // index i will be no. of input files
        if (fscanf(in[i], "%d ", &harr[i].element) != 1)
            break;
  
        // Index of scratch output file
        harr[i].i = i;
    }
    // Create the heap
    MinHeap hp(harr, i);
  
    int count = 0;
  
    // Now one by one get the
    // minimum element from min
    // heap and replace it with
    // next element.
    // run till all filled input
    // files reach EOF
    while (count != i) {
        // Get the minimum element
        // and store it in output file
        MinHeapNode root = hp.getMin();
        fprintf(out, "%d ", root.element);
  
        // Find the next element that
        // will replace current
        // root of heap. The next element
        // belongs to same
        // input file as the current min element.
        if (fscanf(in[root.i], "%d ",
                   &root.element)
            != 1) {
            root.element = INT_MAX;
            count++;
        }
  
        // Replace root with next
        // element of input file
        hp.replaceMin(root);
    }
  
    // close input and output files
    for (int i = 0; i < k; i++)
        fclose(in[i]);
  
    fclose(out);
}
  
// Using a merge-sort algorithm,
// create the initial runs
// and divide them evenly among
// the output files
void createInitialRuns(
    char* input_file, int run_size,
    int num_ways)
{
    // For big input file
    FILE* in = openFile(input_file, "r");
  
    // output scratch files
    FILE* out[num_ways];
    char fileName[2];
    for (int i = 0; i < num_ways; i++) {
        // convert i to string
        snprintf(fileName, sizeof(fileName),
                 "%d", i);
  
        // Open output files in write mode.
        out[i] = openFile(fileName, "w");
    }
  
    // allocate a dynamic array large enough
    // to accommodate runs of size run_size
    int* arr = (int*)malloc(
        run_size * sizeof(int));
  
    bool more_input = true;
    int next_output_file = 0;
  
    int i;
    while (more_input) {
        // write run_size elements
        // into arr from input file
        for (i = 0; i < run_size; i++) {
            if (fscanf(in, "%d ", &arr[i]) != 1) {
                more_input = false;
                break;
            }
        }
  
        // sort array using merge sort
        mergeSort(arr, 0, i - 1);
  
        // write the records to the
        // appropriate scratch output file
        // can't assume that the loop
        // runs to run_size
        // since the last run's length
        // may be less than run_size
        for (int j = 0; j < i; j++)
            fprintf(out[next_output_file],
                    "%d ", arr[j]);
  
        next_output_file++;
    }
  
    // close input and output files
    for (int i = 0; i < num_ways; i++)
        fclose(out[i]);
  
    fclose(in);
}
  
// For sorting data stored on disk
void externalSort(
    char* input_file, char* output_file,
    int num_ways, int run_size)
{
    // read the input file,
    // create the initial runs,
    // and assign the runs to
    // the scratch output files
    createInitialRuns(input_file,
                      run_size, num_ways);
  
    // Merge the runs using
    // the K-way merging
    mergeFiles(output_file, run_size, num_ways);
}
  
// Driver program to test above
int main()
{
    // No. of Partitions of input file.
    int num_ways = 10;
  
    // The size of each partition
    int run_size = 1000;
  
    char input_file[] = "input.txt";
    char output_file[] = "output.txt";
  
    FILE* in = openFile(input_file, "w");
  
    srand(time(NULL));
  
    // generate input
    for (int i = 0; i < num_ways * run_size; i++)
        fprintf(in, "%d ", rand());
  
    fclose(in);
  
    externalSort(input_file, output_file, num_ways,
                 run_size);
  
    return 0;
}