CODEWITHSUNDEEP
carrayssortingmergesort
osk
osk

Reputation: 810

Merging and sorting two sorted arrays containing doubles in C

So I have two arrays consisting of double numbers, they are sorted.

I would like to most efficiently combine these into one array and have this one array also sorted.

My first thought was that maybe you could simply join them together then use qsort on it, but this wouldn't be that efficient. So maybe instead using merge sort? However, I am kind of lost on how to implement merge sort in C, any ideas?

I am using the code from one of the answers to try merge sorting. I have not made it into its own method just yet, will do that after I have gotten it to work.

double partitions[][5] = {{45.0, 5.0, 88.4, 0.4, 44.0}, {1000.0, 2.0, 3.4, 7.0, 50.0}};
double* res;

int n1 = sizeof(partitions[0])/sizeof(partitions[0][0]);
int n2 = sizeof(partitions[1])/sizeof(partitions[1][0]);
int n3 = n1 + n2;

res = malloc(n3 * sizeof(double));

// Merging starts
int i = 0;
int j = 0;
int k = 0;

while (i < n1 && j < n2) {
    if (partitions[0][i] - partitions[1][j] < 0.000001) {
        res[k] = partitions[0][i];
        i++;
        k++;
    }
    else {
        res[k] = partitions[1][j];
        k++;
        j++;
    }
}

/* Some elements in array 'arr1' are still remaining
where as the array 'arr2' is exhausted */
while (i < n1) {
    res[k] = partitions[0][i];
    i++;
    k++;
}

/* Some elements in array 'arr2' are still remaining
where as the array 'arr1' is exhausted */
while (j < n2) {
    res[k] = partitions[1][j];
    k++;
    j++;
}

int m;
for (m = 0; m < n3; m++)
    printf("%f \n", res[m]);

Upvotes: 1

Views: 325

Answers (1)

coder
coder

Reputation: 12972

Since the arrays are sorted you only need the merge part of the merge sort which is O(n1+n2) where n1 is the length of the one array and n2 is the length of the other array:

For example:

void merge(int n1, int n2){ //suppose global arrays arr1,arr2 and result array

      i = 0;
      j = 0;
      k = 0;

    // Merging starts
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            res[k] = arr1[i];
            i++;
            k++;
        } 
        else {
            res[k] = arr2[j];
            k++;
            j++;
        }
    }

    /* Some elements in array 'arr1' are still remaining
    where as the array 'arr2' is exhausted */

    while (i < n1) {
        res[k] = arr1[i];
        i++;
        k++;
    }

    /* Some elements in array 'arr2' are still remaining
    where as the array 'arr1' is exhausted */

    while (j < n2) {
        res[k] = arr2[j];
        k++;
        j++;
    }
}

Also I just note that your arrays contain double so you need to change the condition when comparing two numbers. For example instead of if (arr1[i] <= arr2[j]) you need to write a condition for: if (arr1[i] < arr2[j]) and then the else part.

Upvotes: 2

Related Questions