/media/sda-magnetic/david/Dokumente-15/fernuni-hagen/cs-i-ii/old-cs-2-03/sort-and-algorithms/sortingbymerging/merge.txt

Ich habe die Idee für meinen Sortieralgorithmus. Zunächst viel mir auf, dass optisch ein wenig Ähnlichkeit besteht, zwischen Insertion-Sort und der Transponierung einer Matrix. Nur, dass die Transponierung meiner Matrix im zweidimensionalen Bereich besteht. Daran werde ich arbeiten.
Mein Sortieralgorithmus sollte lauten: Verschmelze zwei sortierte Felder. Zunächst haben die Felder, die Länge 1, dann 2, dann 4, ...
Meine Idee ist nun, was it wenn ich diesen Sortieralgorithmus auf Matrizen im zweidimensionalen Bereich anwende?
Problem dabei ist es - beim Sortieralgorithmus, immer den gescheiten Anfang und das gescheite Ende für die Felder zu finden. Doch in C ist es einfach möglich ein zweidimensionales Array als ein eindimensionales zu verwenden. Was ist, wenn ich das für unseren Sortieralgorithmus nutze?

Was ich in C nicht kann, ist ein eindimensionales Array, zum zweidimensionalen mache, habe ich gerade getestet. Wieso auch? Woher soll er wissen, wo die Grenze bei der größeren Dimension ist? Insofern wird das für den Sortieralgorithmus nichts nutzen.

Trotzdem interessant: Sortieralgorithmen auf mehrdimensionale Felder.

#include <stdio.h>

#define N 32

int merge(int startdes, int startsrc1, int startsrc2, int enddes, int endsrc1, int endsrc2, int a[N]) {
    int b[N];
    int c[N];
    int i;
    int j;
    
    int n1, n2;
    
    int k, l;
    
    n1 = endsrc1 - startsrc1;
    n2 = endsrc2 - startsrc2;
    
    for (i = startsrc1, j = 0;  i <= endsrc1;  i++, j++)
        b[j] = a[i];
    for (i = startsrc2, j = 0;  i <= endsrc2;  i++, j++) 
        c[j] = a[i];
    
    for(i = startdes, l = 0, k = 0;  i < enddes;  i++) {;
        if((l < n1) && (k >= n2)) {
            a[i] = b[l];
            l++;
        }
        else if((l >= n1) && (k < n2)) {
            a[i] = c[k];
            k++;
        }
        else if(b[l] <= c[k]) {
            a[i] = b[l];
            l++;
        }
        else if(b[l] > c[k]) {
            a[i] = c[k];
            k++;
        }
    }
    
}

int main(void) {
    int i;
    
    int a[] = {1, 2, 3, 4, 1, 2, 3, 4};
    
    printf("\n");
    
    
    for(i = 0;  i < 7;  i+=2) {
        merge(i, i, i+1, i+1, i, i+1, a);
    }
    
    for(i = 0;  i < 8;  i++)
        printf("%i\n", a[i]);
    
return 0;
}


So, ich bin mit dem Sortieralgorithmus fertig. Zunächst da war noch ein Fehler drin, nächster Beitrag.

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

#define N 32

int merge(int startdes, int startsrc1, int startsrc2, int enddes, int endsrc1, int endsrc2, int a[N]) {
    int b[N];
    int c[N];
    int i;
    int j;
    
    int n1, n2;
    
    int k, l;
    
    n1 = endsrc1 - startsrc1;
    n2 = endsrc2 - startsrc2;
    
    for (i = startsrc1, j = 0;  i <= endsrc1;  i++, j++) 
        b[j] = a[i];
    for (i = startsrc2, j = 0;  i <= endsrc2;  i++, j++)  
        c[j] = a[i];
    
    for(i = startdes, l = 0, k = 0;  i <= enddes;  i++) {
        if((l <= n1) && (k > n2)) {
            a[i] = b[l];
            l++;
        }
        else if((l > n1) && (k <= n2)) {
            a[i] = c[k];
            k++;
        }
        else if(b[l] <= c[k]) {
            a[i] = b[l];
            l++;
        }
        else if(b[l] > c[k]) {
            a[i] = c[k];
            k++;
        }
    }    
}


Komplett sieht das Programm so aus, nächster Beitrag.

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

#define N 32

int merge(int startdes, int startsrc1, int startsrc2, int enddes, int endsrc1, int endsrc2, int a[N]) {
    int b[N];
    int c[N];
    int i;
    int j;
    
    int n1, n2;
    
    int k, l;
    
    n1 = endsrc1 - startsrc1;
    n2 = endsrc2 - startsrc2;
    
    for (i = startsrc1, j = 0;  i <= endsrc1;  i++, j++) 
        b[j] = a[i];
    for (i = startsrc2, j = 0;  i <= endsrc2;  i++, j++)  
        c[j] = a[i];
    
    for(i = startdes, l = 0, k = 0;  i <= enddes;  i++) {
        if((l <= n1) && (k > n2)) {
            a[i] = b[l];
            l++;
        }
        else if((l > n1) && (k <= n2)) {
            a[i] = c[k];
            k++;
        }
        else if(b[l] <= c[k]) {
            a[i] = b[l];
            l++;
        }
        else if(b[l] > c[k]) {
            a[i] = c[k];
            k++;
        }
    }    
}

int main(void) {
    int i;
    int diff;
    int j;
    
    int a[] = {1, 2, 3, 4, 1, 2, 3, 4};
    int b[32];

    for(diff = 1; diff <  8;  diff *=2) 
        for(i = 0;  (i+diff) < 8;  i+=(2*diff)) 
            merge(i, i, i+diff, i+diff*2-1, i+diff-1, i+diff*2-1, a);
            
    for(i = 0; i < 8;  i++)
        printf("%i\n", a[i]);

    srand(5);
    for (i = 0;  i < 32;  i++)
        b[i] = rand() % 64;
    
    for(diff = 1; diff <  32;  diff *=2) 
        for(i = 0;  (i+diff) < 32;  i+=(2*diff)) 
            merge(i, i, i+diff, i+diff*2-1, i+diff-1, i+diff*2-1, b);

    for (i= 0;  i < 32;  i++)
        printf("%i ", b[i]);
return 0;
}

Ankommen tut es auch darauf:

    for(diff = 1; diff <  32;  diff *=2) 
        for(i = 0;  (i+diff) < 32;  i+=(2*diff)) 
            merge(i, i, i+diff, i+diff*2-1, i+diff-1, i+diff*2-1, b);