Intermediate vectors in C

Question

People have to develop a code that reads the size of 2 vectors dps the elements of it (these vectors are increasing), transform into a single vector (it doesn’t have to be ordered), and then using the interlink function, transform into an ordered vector and print it. The question is, is it possible to do this without using Mergesort? only using the " Merge" function? I tried a lot of things here but there’s always two elements that should be at the beginning that are getting at the end.

Edit: In short, the doubt is even if it is possible to do what the exercise asks without using any sort algorithm, only the "Interlayer" function that in this case would interlink the vector from position 0 to half-1 with the vector half to size-1 Follows the code.

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



int intercala(int *v, int inicio, int n, int t){

    int v1 = inicio;
    int fim = (n+t)-1;
    int meio = (n+t)/2;
    int v2 = meio+1;
    int i,j;
    int tamanho = fim-inicio+1;
    int vet[tamanho];


    for(i=0; i<tamanho; i++){

     if(v[v1] <= v[v2]){
        vet[i]=v[v1++];
     }
        else{
        vet[i]=v[v2++];
        }
    }
   while(v1<=meio){
       vet[i++] = v[v1++];

   }

    while(v2<=fim){
       vet[i++] = v[v2++];

   }


    for(i=0; i<tamanho; i++){
        printf("%d ", vet[i]);
    }


    return 0;


}





int main (){


int n, t, i;

printf("Tamanho do primeiro vetor\n");
scanf("%d", &n);


printf("Tamanho do segundo vetor\n");
scanf("%d", &t);

int v[t+n];
printf("elementos do primeiro vetor\n");
for(i=0; i <n; i++){

    scanf("%d", &v[i]);
}
 printf("Elementos do segundo vetor\n");
for(i=n; i <(n+t); i++){
    scanf("%d", &v[i]);
}




intercala(v, 0, n, t);




return 0;



}

Answer 1

You can solve this easily with Bubble Sort, but it is very slow, or if the vectors are composed only by positive values you can apply Counting Sort, a very good algorithm for this type of case.

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

void countingSort(int *vet, int vetSize, int maior) {
    int *aux = (int *) malloc(sizeof(int) * (maior + 1));
    int i, j;
    for (i = 0; i < vetSize; i++) {
        aux[vet[i]]++;
    }
    for (i = 0, j = 0; i < maior + 1; i++) {
        if (aux[i] != 0) {
            while (aux[i] > 0) {
                vet[j] = i;
                aux[i]--;
                j++;
            }
        }
    }
    free(aux);
}

void bubbleSort(int *vet, int vetSize) {
    int i, j;
    for (i = 0; i < vetSize - 1; i++) {
        for (j = 0; j < vetSize - i - 1; j++) {
            if (vet[j] > vet[j + 1]) {
                int aux = vet[j];
                vet[j] = vet[j + 1];
                vet[j + 1] = aux;
            }
        }
    }
}

int main() {
    int n, t, i, maior = 1;

    printf("Tamanho do primeiro vetor\n");
    scanf("%d", &n);

    printf("Tamanho do segundo vetor\n");
    scanf("%d", &t);

    int v[t + n];
    printf("elementos do primeiro vetor\n");
    for(i = 0; i < n; i++){
        scanf("%d", &v[i]);
        if (v[i] > maior) {
            maior = v[i];
        }
    }
    printf("Elementos do segundo vetor\n");
    for(i = n; i < (n + t); i++){
        scanf("%d", &v[i]);
        if (v[i] > maior) {
            maior = v[i];
        }
    }
    //countingSort(v, n + t, maior);
    bubbleSort(v, n + t);
    for (i = 0; i < n + t; i++) {
        printf("%d\n", v[i]);
    }
    return 0;
}

Answer 2

I managed to create a function that does this in O(n+m):

//n é o tamanho do vetor a, m é o tamanho do vetor b
int *intercala(int *a, int *b, int n, int m){
    int i = 0, j = 0;
    int *c = (int*)malloc((n + m)*sizeof(int));
    int k = 0;
    while((i + j) < (n + m)){
        if(i >= n){
            for (; j < m; j++, k++){
                c[k] = b[j];
            }
            break;
        }
        else if(j >= m){
            for (; i < n; i++, k++){
                c[k] = a[i];
            }
            break;
        }
        if (a[i] < b[j])
            c[k] = a[i++];

        else 
            c[k] = b[j++];

        k++;
    } 
    return c;
}

Given the two vectors a, b with sizes n, m, respectively, you just go through the two vectors at the same time using indices i, j seeing which is smaller. So when you take an element of any vector, just increment the index used. If you go through one vector to the end, just take the remaining elements of the other vector.