Thread: Merge two sorted arrays recursively

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    13

    Merge two sorted arrays recursively

    Hi, the exercise is this:
    I got two sorted arrays (of any length) and I got to merge them into a new array (of correct length, and still sorted), recursively.

    I solved the problem like this:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    void merge(int *v1, int *v2, int l1, int l2, int *v3);
    int *newArray(int n);
    
    int main (void) {
        int *v1, *v2, *v3;
        int i, l1, l2, l3;
    
        v1 = v2 = v3 = NULL;
    
        printf("Enter the numbers in increasing order.\n\n");
    
        printf("First's array length: ");
        do{
            scanf("%d", &l1);
        }while(l1 <= 0);
    
        v1 = newArray(l1);
    
        printf("\nSecond's array length: ");
        do{
            scanf("%d", &l2);
        }while(l2 <= 0);
    
        v2 = newArray(l2);
    
        l3 = l1 + l2;
    
        v3 = malloc(l3 * sizeof(int));
        if(!v3)
            return -1;
    
        merge(v1, v2, l1, l2, v3);
    
        printf("\nResult:\n");
        for(i=0; i<l3; ++i)
            printf("%d ", v3[i]);
    
        return 0;
    }
    
    void merge(int *v1, int *v2, int l1, int l2, int *v3){
        if(l1 && l2){ // verifying if both vectors got elements
            if(*v1 <= *v2){
                *v3 = *v1;
                merge(++v1, v2, --l1, l2, ++v3);
            }
            else{
                *v3 = *v2;
                merge(v1, ++v2, l1, --l2, ++v3); // notare ++v2 e --l2 e ++v3
            }
        }
    
        else if(l1){ // verifying if only v1 got elements
            *v3 = *v1;
            merge(++v1, v2, --l1, l2, ++v3);
        }
    
        else if(l2){ // verifying if only v2 got elements
            *v3 = *v2;
            merge(v1, ++v2, l1, --l2, ++v3);
        }
    }
    
    int *newArray(int n){
        int *v = NULL;
        int i;
    
        v = malloc(n * sizeof(int));
    
        if(!v)
            return NULL;
    
        for(i=0; i<n; ++i){
            printf("[%d]: ", i);
            scanf("%d", &v[i]);
        }
    
        return v;
    }
    My solution seems to work well. I only got a doubt about how I solved it, it is: is there a way to make it in the form "v3 = merge(parameters);" ?
    I would like to know if I can do it with returns... it would be a non-void function.

    Thanks
    Last edited by kr0n1x; 06-04-2012 at 09:55 AM.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by kr0n1x View Post
    I would like to know if I can do it with returns... it would be a non-void function.
    I think that will be a little awkward, actually. What you have now is very clear; if it works, just leave it that way. Why do you think using the return value would represent an improvement?
    Last edited by MK27; 06-04-2012 at 10:30 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Aug 2011
    Posts
    13
    Quote Originally Posted by MK27 View Post
    I think that will be a little awkward, actually. What you have now is very clear; if it works, just leave it that way. Why do you think using the return value would represent an improvement?
    A lot of the recursive functions I've been using have returns (for example those with trees and lists management). Since I was not able to make it with returns (in this exercise), I was curious to know if the reason was behind my lack of experience or if, as you said, it is actually better to make it without returns.
    If you say this is a good solution, it's ok to me xD

    Thanks!

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    A return value can be viewed as syntactic sugar. A reference parameter could always be added and used allowing the function to be `void'. That alone doesn't make one design better or worse.

    Soma

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Conceptually, you should be returning the array. Unfortunately, C doesn't really let you do that (without a lot of memory overhead).

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    If you wanted to pass v3 out then you'd probably also want to avoid passing it in. Therefore you'd probably want to move the malloc inside the merge function. Then you'd probably end up making lots of malloc calls, possibly leak memory, or return a buffer that had been freed, and ultimately end up with a worse solution.
    You're probably best doing it as you have now. However I suggest using better variable names as that would make it easier to follow.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Can you merge arrays?
    By SeriousTyro in forum C Programming
    Replies: 14
    Last Post: 09-21-2009, 10:38 AM
  2. how to merge two arrays recursevly..
    By transgalactic2 in forum C Programming
    Replies: 117
    Last Post: 01-11-2009, 04:47 PM
  3. Merge sort (sorted arrays)
    By myle in forum C++ Programming
    Replies: 3
    Last Post: 05-09-2007, 02:48 AM
  4. ordered binary tree
    By Ami_01 in forum C Programming
    Replies: 3
    Last Post: 07-05-2005, 06:44 PM
  5. How to merge 2 arrays?
    By planet_abhi in forum C Programming
    Replies: 3
    Last Post: 02-16-2003, 12:23 AM

Tags for this Thread