Lec 15: External Sorting⚓︎

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100010

struct element {
    int val;
    int run;
};
typedef struct element Element;

struct heap {
    int size;
    Element * data;
};
typedef struct heap * Heap;

typedef struct node * Node;
struct node {
    int data;
    Node next;
};

struct queue {
    Node head;
    Node tail;
    int size;
};
typedef struct queue * Queue;

void InitQueue(int m);
void Enqueue(int data, Queue Q);
Heap InitHeap();
void PercolateUp(int p, Heap H);
void PercolateDown(int p, Heap H);
void Insert(Element x, Heap H);
Element DeleteMin(Heap H);
int cmp(Element a, Element b);

Queue * arr;
Heap H;

int main() {
    int n, m;
    Element cur;
    Element tmp;
    Node curr;
    int data;
    int i, num, flag;

    scanf("%d%d", &n, &m);
    H = InitHeap();
    InitQueue(n);
    curr = (Node)malloc(sizeof(struct node));

    for (i = 0; i < n; i++) {
        scanf("%d", &data);
        tmp.val = data;
        if (H->size < m)
            tmp.run = 1;
        else {
            cur = DeleteMin(H);
            if (data >= cur.val)
                tmp.run = cur.run;
            else
                tmp.run = cur.run + 1;
            num = cur.run - 1;
            Enqueue(cur.val, arr[num]); 
        }
        Insert(tmp, H);
    }

    while (H->size > 0) {
        cur = DeleteMin(H);
        num = cur.run - 1;
        Enqueue(cur.val, arr[num]); 
    }

    for (i = 0; i < n; i++) {
        curr = arr[i]->head->next;
        flag = 0;
        while (curr != NULL) {
            flag = 1;
            if (curr == arr[i]->head->next)
                printf("%d", curr->data);
            else
                printf(" %d", curr->data);
            curr = curr->next;
        }
        if (flag)
            printf("\n");
    }

    return 0;
}

void InitQueue(int m) {
    int i;

    arr = (Queue *)malloc((MAXSIZE) * sizeof(Queue));
    for (i = 0; i < m; i++) {
        arr[i] = (Queue)malloc(sizeof(struct queue));
        arr[i]->head = (Node)malloc(sizeof(struct node));
        arr[i]->tail = (Node)malloc(sizeof(struct node));
        arr[i]->head->next = NULL;
        arr[i]->tail = arr[i]->head;
        arr[i]->size = 0;
    }
}

void Enqueue(int data, Queue Q) {
    Node cur = (Node)malloc(sizeof(struct node));

    cur->data = data;
    cur->next = Q->tail->next;
    Q->tail->next = cur;
    Q->tail = cur;
}

Heap InitHeap() {
    Heap H;

    H = (Heap)malloc(sizeof(struct heap));
    H->data = (Element *)malloc(MAXSIZE * sizeof(Element));
    H->size = 0;
    H->data[0].val = INT_MIN;
    H->data[0].run = 0;

    return H;
}

void PercolateUp(int p, Heap H) {
    int i;
    Element x = H->data[p];

    for (i = p; cmp(H->data[i / 2], x) > 0; i /= 2)
        H->data[i] = H->data[i / 2];

    H->data[i] = x;
}

void PercolateDown(int p, Heap H) {
    int i, child;
    Element last = H->data[p];

    for (i = p; i * 2 <= H->size; i = child) {
        child = i * 2;
        if (child != H->size && cmp(H->data[child + 1], H->data[child]) < 0)
            child++;
        if (cmp(last, H->data[child]) > 0)
            H->data[i] = H->data[child];
        else
            break;
    }
    H->data[i] = last;
}

void Insert(Element x, Heap H) {
    int p = ++H->size;
    H->data[p] = x;
    PercolateUp(p, H);
}

Element DeleteMin(Heap H) {
    Element min;
    min = H->data[1];
    H->data[1] = H->data[H->size--];
    PercolateDown(1, H);
    return min;
}

int cmp(Element a, Element b) {
    if (a.run != b.run)
        return a.run - b.run;
    else
        return a.val - b.val;
}