Algoritem za naravno, uravnoteženo, večsmerno zlivanje

Večsmerno pomeni n-smerno, da imamo n trakov.

Isto kot trosmerno zlivanje: Algoritem za naravno, uravnoteženo, trosmerno zlivanje. Namesto 3 trakov imamo tu n trakov.. isti princip, prvo ceto na prvi trak, drugo na drug trak...

Referenčna implementacija

Algoritem ima nekaj odvečne kode (kar se tiče kopice in pa pogrezanje, ki ne deluje), ampak vseeno dela kar je potrebno narediti.

Če želite videti kako deluje, naj bo vrstica #define DEBUG odkomentirana, če želite samo uporabiti algoritem, jo zakomentirajte pred prevajanjem.

Uporaba:

gcc -o natbalmultimergesort natbalmultimergesort.c 
./natbalmultimergesort k n m test

Kjer je k stevilo potomcev posameznega elementa v kopici (ni uporabljeno), n je velikost kopice (ni uporabljeno) in m stevilo trakov po katerih naj se zliva.

 /* Naravno, uravnotezeno, vecsmerno zlivanje 
  * 
  * Skoraj perfektna kopija algoritma v knjigi prof. Vilfana.
  * Samo da NI oberon.
  * Datum: 9. marec 2006
  */
 #include <stdlib.h>
 #include <string.h>
 #include <math.h>
 #include <stdio.h>
 int *kopica, *inthisrun;    /* tabeli za kopico */
 int k;                  /* st. potomcev */
 int n;              /* velikost kopice */
 int m;              /* stevilo trakov */
 int dkop;           /* dolzina trnutno aktivnega dela kopice */
 char *in_filename;  /* ime vhodne datoteke */
 int h;              /* stevilo vhodov in izhodov */
 int dest;           /* indeks izhoda na katerega pisemo */
 int nes;            /* stevilo nepraznih vhodov */
 int l;              /* stevilo cet zapisanih v tekoci iteraciji */
 int *pa;            /* tabela kazalcev na vhodne elemente */
 int *pl;            /* tabela vrednosti kljucev, ki so bili nazadnje zapisani na izhode */
 int ppa;            /* */
 int ppl;            /* */
 /* FILE **f;           /* tabela trakov */
 FILE *in;           /* vhodna datoteka */
 int tapen;          /* stevilo trakov, dolzina  f */
 char *filenamegen;  /* string za ustvarjanje  datotek */
 FILE **t_in;        /* vhodni trakovi */
 FILE **t_out;       /* izhodni trakovi */
 int level = 0;      /* nivo zlivanja - za generiranje imen datotek */
 #define TRUE 1
 #define FALSE 0
 #define GET_SIBL(parent, nth)  kopica[n*parent+nth];
 #define ENABLE_HEAP() for(int i=0; i<n; i++) { inthisrun[i] = TRUE };
 #define ENABLE_NODE(n) inthisrun[n] = TRUE;
 #define DEBUG
 void copy_run(FILE *in, FILE *out, int *p, int *lastk);
 /* pretvori niz znakov n v int */
 int str_to_int(char *num) {
    int i, val = 0;
    int decimals = 1;
    int v;
    for (i=strlen(num)-1; i>-1; i--){
        v = -48+(int)(num[i]);
        if (v>=0 && v<=9) {
            val = val + decimals*v;
        } else {
            printf("Napacni vhodni podatki: %s\n",num);
            exit(2);
        }
        decimals = decimals * 10;
    }
    return val;
 }
 /* pogrezaj znak v kopico */
 int pogrezaj(int znak) {
    int last;
    if (znak <= last) {
        inthisrun[0] = TRUE;
        kopica[0] = znak;
        /* TODO POGREZANJE */
    } else {
        dkop--;
        inthisrun[dkop] = FALSE;
        kopica[0] = kopica[dkop];
        kopica[dkop] = znak;
        /* TODO POGREZANJE */
    }
 }
 void init_prog() {
    int i;
    int p;
    int last = EOF;
    #ifdef DEBUG
    printf("init_prog: called\n");
    #endif
    p = fgetc(in);
    #ifdef DEBUG
    printf("init_prog: h = %d\n",h);
    #endif
    /* vhodni in zadnji zapisani elementi */
    pa = (int*)calloc(m,sizeof(int));
    pl = (int*)calloc(m,sizeof(int));
    if (pa == NULL || pl == NULL) {
        printf("init_prog: Napaka pri dodeljevanju pomnilnika.");
        exit(2);
    }
    for (i=0;i++;i<m) {
        pa[i] = EOF;
        pl[i] = EOF;
    }
    /* zacetna porazdelitev */
    i=m-1;
    do {
        if (i==m-1) {
            i=0;
        } else {
            i++;
        }
        copy_run(in, t_out[i], &p, &last);
    } while (p!=EOF);
    #ifdef DEBUG
    printf("init_prog: done ok\n");
    #endif
 }
 void init_loop() {
    int i;
    FILE *p;
    int e = 0;
    #ifdef DEBUG
    printf("init_loop: called\n");
    #endif
    l = 0;
    /* odpremo vhodne datoteke za branje, izhodne datoteke za pisanje */
    /* t_in = (FILE**)calloc(m,sizeof(FILE*)); to naredimo v */
    #ifdef DEBUG
    printf("init_loop: e = %d m = %d\n",e,m);
    #endif
    while (e<m) {
        #ifdef DEBUG
        printf("init_loop: inloop by: e = %d\n",e);
        #endif
        sprintf(filenamegen, "%s-%d-%d", in_filename, level, e+1);
        t_in[e] = fopen(filenamegen,"rb");
        #ifdef DEBUG
        printf("init_loop: inloop: t_in[%d] -> %s\n",e,filenamegen);
        #endif
        if (t_in[e] ==NULL) {
            printf("Ni bilo mogoce odpreti datoteke %s\n",filenamegen);
            exit(2);
        }
        sprintf(filenamegen, "%s-%d-%d", in_filename, level+1, e+1);
        t_out[e] = fopen(filenamegen,"wb");
        #ifdef DEBUG
        printf("init_loop: inloop: t_out[%d] -> %s\n",e,filenamegen);
        #endif
        if (t_out[e] == NULL) {
            printf("Ni bilo mogoce narediti datoteke %s\n",filenamegen);
            exit(2);
        }
        e++;
    }
    #ifdef DEBUG
    printf("init_loop: datoteke odprte ok\n");
    #endif
    level++;
    /* razporedimo prazne/neprazne trakove */
    i = 0;
    nes = m-1;
    while (i <= nes) {
        pa[i] = fgetc(t_in[i]);
        if (pa[i] != EOF) {
            i++;
        } else {
            #ifdef DEBUG
            printf("init_loop: inloop: menjam t_in[%d] s t_in[%d]\n",i,nes);
            #endif
            p = t_in[i];
            t_in[i] = t_in[nes];
            t_in[nes] = p;
            nes--;
        }
    }
    dest = m-1;
    #ifdef DEBUG
    printf("init_loop: nes = %d, m = %d\n",nes,m);
    printf("init_loop: done ok\n");
    #endif
 }
 void merge_run() {
    int i;
    int minx;
    int ner;
    FILE *p;
    ner = nes;
    #ifdef DEBUG
    printf("merge_run: called\n");
    printf("merge_run: ner = %d nes = %d\n",ner, nes);
    printf("merge_run: dest==m ce %d==%d\n",dest,m);
    #endif
    if (dest == m-1) {
        dest = 0;
    } else {
        dest++;
    }
    do {
        minx = 0;
        i = 0;
        while (i<=ner) {
            #ifdef DEBUG
            printf("merge_run: inloop: if (%d <= %d)\n",pa[i], pa[minx]);
            #endif
            if (pa[i] <= pa[minx])
                minx = i;
            i++;
        }
        #ifdef DEBUG
        printf("merge_run: inloop: minx=%d, zapisal bom %d na dest=%d, m=%d\n",minx,pa[minx],dest,m);
        #endif
        fputc(pa[minx],t_out[dest]);
        #ifdef DEBUG
        fflush(t_out[dest]);
        printf("merge_run: inloop: zapisal crko '%c' na %d\n",pa[minx],dest);
        #endif
        pl[minx] = pa[minx];
        pa[minx] = fgetc(t_in[minx]);
        /* ce je konec cete na tem traku */
        if (pa[minx] == EOF || pl[minx] > pa[minx]) {
            #ifdef DEBUG
            /* printf("merge_run: inloop2: minx -> ner = %d -> %d \n",minx,ner); */
            #endif
            p = t_in[minx];
            ppa = pa[minx];
            ppl = pl[minx];
            t_in[minx] = t_in[ner];
            pa[minx] = pa[ner];
            pl[minx] = pl[ner];
            t_in[ner] = p;
            pa[ner] = ppa;
            pl[ner] = ppl;
            ner--;
            #ifdef DEBUG
            printf("merge_run: inloop2: ner = %d\n",ner);
            printf("merge_run: inloop2: pa[ner] = %d '%c'\n",pa[ner], pa[ner]);
            printf("merge_run: inloop2: pa[ner+1] = %d '%c'\n",pa[ner+1],pa[ner+1]);
            #endif
            /* ce konec traku */
            if (pa[ner+1] == EOF) {
                #ifdef DEBUG
                printf("merge_run: inloop3: nes iz %d na %d\n",nes+1,nes);
                #endif
                p = t_in[ner+1];
                ppa = pa[ner+1];
                ppl = pl[ner+1];
                t_in[ner+1] = t_in[nes];
                pa[ner+1] = pa[nes];
                pl[ner+1] = pl[nes];
                t_in[nes] = p;
                pa[nes] = ppa;
                pl[nes] = ppl;
                nes--;
                #ifdef DEBUG
                printf("merge_run: inloop3: nes iz %d na %d\n",nes+1,nes);
                #endif
            }
        }
    } while (ner != -1); /* zlijemo eno ceto */
    #ifdef DEBUG
    printf("merge_run: done ok\n");
    #endif
 }
 /* prekopira ceto */
 void copy_run(FILE *in, FILE *out, int *p, int *lastk) {
    #ifdef DEBUG
    printf("copy_run: called. ceta: '");
    #endif
    do {
        #ifdef DEBUG
        fputc(*p,stdout);
        #endif
        fputc(*p,out);
        *lastk = *p;
        *p = fgetc(in);
    } while( *p!=EOF && *lastk <= *p);
    #ifdef DEBUG
    printf("'\n");
    fflush(out);
    #endif
 }
 /* glavna procedura za sortiranje */
 void main_sort(FILE *input) {
    #ifdef DEBUG
    printf("main_sort: called\n");
    #endif
    in = input;
    init_prog();
    nes = m;
    #ifdef DEBUG
    printf("main_sort: m = %d\n",m);
    #endif
    do {
        init_loop();
        #ifdef DEBUG
        printf("main_sort: init_loop done ok\n");
        #endif
        do {
            l++;
            #ifdef DEBUG
            printf("main_sort: inloop2: pisem ceto: %d\n",l);
            #endif
            merge_run();
        } while (nes != -1);
    } while (l != 1);
    #ifdef DEBUG
    printf("main_sort: ce l==1 sem koncal! (l = %d) \n",l);
    #endif
 }
 /* program entry point */
 int main(int argc, char *argv[]) {
    FILE *fo;
    int e = 0;
    /* prestevilcenje argumentov */
    if (argc != 5) {
        printf("Napacno stevilo argumentov.\n");
        exit(2);
    } else {
        k = str_to_int(argv[1]);
        n = str_to_int(argv[2]);
        m = str_to_int(argv[3]);
        in_filename = argv[4];
        #ifdef DEBUG
        printf("Stevilo potomcev v kopici (k): %d\n", k);
        printf("Stevilo elementov v kopici (n): %d\n", n);
        printf("Stevilo trakov za zlivanje (m): %d\n", m);
        printf("Ime vhodne datoteke: %s\n",in_filename);
        #endif
    }
    /* poznamo velikost kopice, dodelimo pomnilnik */
    kopica = (int*)calloc(n,sizeof(char));
    inthisrun = (int*)calloc(n,sizeof(char));
    if (kopica == NULL || inthisrun == NULL){
        printf("Ni bilo mozno dodeliti pomnilnika za kopico\n");
        exit(2);
    }
    /* odpremo vhodno datoteko */
    filenamegen = (char*)calloc((int)FILENAME_MAX,sizeof(char));
    sprintf(filenamegen,"%s",argv[4]);
    fo = fopen(filenamegen,"rb");
    if (fo == NULL ) {
        printf("Ni bilo mozno odpreti vhodne datoteke.\n");
        exit(2);
    }
    /* alociramo pomnilnik za trakove */
    t_in = (FILE**)calloc(m,sizeof(FILE*));
    t_out = (FILE**)calloc(m,sizeof(FILE*));
    /* nastavimo izhodne trakove za init_prog */
    while (e<m) {
        sprintf(filenamegen, "%s-%d-%d", in_filename, level, e+1);
        t_out[e] = fopen(filenamegen,"wb");
        #ifdef DEBUG
        printf("main: t_out[%d] -> %s\n",e,filenamegen);
        #endif
        if (t_out[e] == NULL) {
            printf("main: NAPAKA: t_out[%d] = NULL!",e);
            exit(2);
        }
        e++;
    }
    e = 0;
    /* uredi! */
    main_sort(fo);
    return 0;
 }