Ayuda con Ejercicio de arreglos en Lenguaje C

[marting]

Hola buenas tengo que hacer este ejercicio de una guia de C, lo estoy intentando pero no me esta saliendo, si me pudieran dar una mano por favor se los agradeceria, muchas gracias!

realizar la carga de 2 vectores A Y B ambos contendrán números enteros, se solicita que generen un tercer VECTOR C, con los valores de los vectores A Y B cargados,pero  mezclados y ordenados en ascendente. mostrar por pantalla el vector C al terminar.


ejercicio resuelto:


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

int main()
{
  int aux, lista1[5],lista2[5],lista3[10];
  int i,j,k;
      //carga de lista 1
  for (i=0;i<5;i++){
                    printf("Escriba un número");
                    scanf("%d",&lista1);
      }
     //carga de lista 2
  for (j=0;j<5;j++){
                    printf("Escriba un número");
                    scanf("%d",&lista2);
      }

// copiando a lista 3
 
  for(i=0;i<5;i++)
  {
   lista3=lista1;
  }
  for ( j=0;j<5;j++)
  {
     lista3[i++]=lista2[j];
  }


printf("El Tercer arreglo es");
  for (i=0;i<10;i++){
      printf("%d\n",lista3);
  }
     
  system("PAUSE");     
  return 0;
}

[K-YreX]

Pon el código entre etiquetas de Código GeSHi (en lenguaje C).

La solución en pseudocódigo sería algo así:

Código [Seleccionar] Expandir


lista1 : array[n]
lista2 : array[m]
listaMezcla : array[n+m]
INICIO
    PARA i := 0 hasta n-1 HACER
        PEDIR lista1[i]
    FIN PARA
    PARA i := 0 hasta m-1 HACER
        PEDIR lista2[i]
    FIN PARA
   
    i := 0
    j := 0
    k := 0
    MIENTRAS i < n && j < m HACER // Mientras ninguna de las lista llegue al final...
        SI lista1[i] < lista2[j] ENTONCES // Si el valor actual de lista1 es menor...
            listaMezcla[k++] := lista1[i] // ...guardas dicho valor e...
            i := i + 1 // ...incrementas el valor del indice que recorre la lista1
        SINO // Si el valor actual de la lista2 es menor o igual
            listaMezcla[k++] := lista2[j] // ...guardas dicho valor e...
            j := j + 1 // ...incrementas el valor del indice que recorre la lista2
        FIN SI
    FIN MIENTRAS

    MIENTRAS i < n HACER // Si lista 1 es mas larga, terminas de meterla
        listaMezcla[k++] := lista1[i]
    FIN MIENTRAS

    MIENTRAS j < n HACER // Si lista 2 es mas larga, terminas de meterla
        listaMezcla[k++] := lista2[j]
    FIN MIENTRAS
FIN

[Serapis]

Eso se llama "refundición".

Primero debes crear el array de salida con el tamaño de ambos (no se pide retirar repetidos).

Luego debes tener en cuenta el tamaño de ambos arrays, cuando tienen el mismo tamaño puede parecer más sencillo obviamente, pero no es el caso.
Entonces se crea una variabe que actúa control de fin, que sucederá cuando uno de los arrays llegue al final, lo operación continuará luego poniendo tras el final el resto del segundo array si queda algo. Date cuenta pués que ese 'siq queda algo' no depende del tamaño del array si no de los valores que contenga cada uno.

Código [Seleccionar] Expandir


entero j, k, n, sizeA, sizeB

sizeA= size(arrayA)
sizeB = size(arrayB)

entero arrSalida(0 a sizeA + sizeB -1)


Hacer mientras (limite = 0)
   Hacer mientras (arrayA(j) => arrayB(k))
       arrSalida(n) = arrayA(j)
       n +=1
       j +=1
       si (j> sizeA)
           limite=1        // señalaría que el arrayB debe depositar lo que reste en salida
           // podría hacerse aquí, pero queda más claro si se hace fuera de ambos bucles.
           salir del bucle
       fin si  
   repetir  
   
   si limite = 0
       Hacer mientras (arrayB(k) > arrayA(j))
           arrSalida(n) = arrayA(k)
           n +=1
           k +=1
           si (k> sizeB)
               limite=2        // señalaría que el arrayB debe depositar lo que reste en salida
               // podría hacerse aquí, pero queda más claro si se hace fuera de ambos bucles.
               salir del bucle
           fin si  
       repetir
   fin si
repetir

Si limite = 1
   bucle para k desde k hasta sizeB
       arrSalida(n) = arrayb(k)
       n +=1
       k +=1
   siguiente
sino // limite = 2
   bucle para j desde j hasta sizeA
       arrSalida(n) = arrayA(j)
       n +=1
       j +=1
   siguiente
fin si


p.d.: Ascendente o descendente implica cambiar los operadores de comparación, tal como yo los he puesto se ordenan de mayor a menor...

[CalgaryCorpus]

El enunciado no indica que los vectores que se ingresan estan ordenados, que parece ser asumido por las soluciones presentadas.

[K-YreX]

El enunciado no indica que los vectores que se ingresan estan ordenados, que parece ser asumido por las soluciones presentadas.

Cierto. Fue una cosa que di por supuesto sin darme cuenta.
Mi implementación necesitaría ordenar primero cada uno de los vectores y después mezclarlos en uno.

[CalgaryCorpus]

Una alternativa a lo dicho: puesto que la restriccion solamente es que los datos esten en un vector, propongo que en vez de insertar los datos en posiciones sucesivas, y en vez de ordenar antes de comenzar a sacar elementos del inicio, podria irse creando un heapmin. Con esto, siempre se obtiene el elemento minimo en O(1), por lo que se parece a lo ya propuesto. Sucesivas remociones de este arreglo toman a lo mas O(log(n)) donde n es el tamano del arreglo de donde se obtiene ese minimo.

Puesto que se esta removiendo elementos, el tiempo deberia ser:
O(log(tamanoA)^2) + O(log(tamanoB)^2).

La creacion del arreglo final puede seguir la misma idea que se ha propuesto aqui.

[Serapis]

El enunciado no indica que los vectores que se ingresan estan ordenados, que parece ser asumido por las soluciones presentadas.

Refundir un contenido sin ordenar, supone una de tres cosas:
A ) Se concatena el contenido de ambios arrays y luego se ordena ese array.
E perfectamente válido pero no es lo que se solicita en el enunciado.
Es trivial este caso, siendo el ejercicio de un estudiante carece de interés, porque no ofrece nada más interesante que ordenar un array.
Si el estudiante está tratando de aprender a concatenar arrays, ordenarlo después es exigirle en tal momento demasiado.
Si el estudiante ya sabe ordenar un array, concatenar dos arrays, debe serle sencillo pero dicha trivialidad distrae de lo que realmente se trata de enseñar/aprender.



B ) Los arrays no están ordenados, pero todavía se refunde ordenadamente.
Este caso, es bastante más ineficaz de cara al rendimiento, pués para ordenar sobre la marcha, ambos arrays, no se presta fácilmente cualquier algoritmo.
Los más aptos son aquellos que en cada iteración van dejando ordenado uno de sus extremos, como es el caso por ejemplo del algoritmo 'Selection Sort'.
Mezclar el algortimo de refundición (que en sí mismo es un algoritmo de ordenamiento), con otro de ordenamiento, solo oscurece el código resultante al tiempo que se le priva de la eficacia de 'pasar' previamente los arrays por un algoritmo más eficiente.

De todos modos, para despejar dudas se propone una implementación en pseudocódigo para este caso, es básicamente el pseudocódigo anterior mezclado con el algoritmo selection sort.
El algoritmo 'Selection-sort' es el que mejor acomoda a la situación sin complicar en exceso el algoritmo final, dado que 'Selection' puede entenderse como un algoritmo de dos pasos:

Puede exhibirse un caso procediendo con la refundición estando aún los arrays desordenados, para ello, se procede a buscar los elementos mayores (o menores en sendos arrays).

Código [Seleccionar] Expandir


entero j, k, n, sizeA, sizeB
entero vA, vB, tmp

sizeA = size(arrayA)
sizeB = size(arrayB)

entero arrSalida(0 a sizeA + sizeB -1)

// buscar el mayor en el arrayB, entre la posición tmp (K) y sizeB, e intercambiar valores entre las posiciones tmp y k.
tmp = k
vB = BuscarValorMayor(arrayB, tmp, sizeB)
arrayB(tmp) = arrayB(k): arrayB(k) = vb // poco a poco se va ordenando el arrayB

Hacer mientras (limite = 0)
    // buscar el mayor en el arrayA, entre la posición tmp (j) y sizeA, e intercambiar valores entre las posiciones tmp y j.
    tmp = j
    vA = BuscarValorMayor(arrayA, tmp, sizeA)
    arrayA(tmp) = arrayA(j): arrayA(j) = vA  // poco a poco se va ordenando el arrayA

    Hacer mientras (vA => vB)
        arrSalida(n) = vA
        n +=1
        j +=1
        si (j> sizeA)
            limite=1        // señalaría que el arrayB debe depositar lo que reste en salida
            // podría hacerse aquí, pero queda más claro si se hace fuera de ambos bucles.
            salir del bucle
        fin si

        tmp = j
        vA = BuscarValorMayor(arrayA, tmp, sizeA)
        arrayA(tmp) = arrayA(j): arrayA(j) = vA   
    repetir   
   
    si limite = 0
        Hacer mientras (vB > vA)
            arrSalida(n) = vB
            n +=1
            k +=1
            si (k> sizeB)
                limite=2        // señalaría que el arrayB debe depositar lo que reste en salida
                // podría hacerse aquí, pero queda más claro si se hace fuera de ambos bucles.
                salir del bucle
            fin si

            tmp = k
            vB = BuscarValorMayor(arrayB, tmp, sizeB)
            arrayB(tmp) = arrayB(k): arrayB(k) = vb   
        repetir
    fin si
repetir

Si limite = 1
    bucle para k desde k hasta sizeB
        tmp = k
        vB = BuscarValorMayor(arrayB, tmp, sizeB)
        arrayB(tmp) = arrayB(k): arrayB(k) = vb
        arrSalida(n) = vB
        n +=1
        k +=1
    siguiente
sino // limite = 2
    bucle para j desde j hasta sizeA
        tmp = j
        vA = BuscarValorMayor(arrayA, tmp, sizeA)
        arrayA(tmp) = arrayA(j): arrayA(j) = vA

        arrSalida(n) = vA
        n +=1
        j +=1
    siguiente
fin si

A continuación se presenta el algoritmo SelectionSort  expuesto en la forma de dos pasos, para terminar de entender como opera.
No obstante se puede ver como complica innecesariamente acometer el ordenamiento de ambos arrays al tiempo que se procede con la refundición y como decía, al tiempo que se priva ordenar ambos arrays por un algoritmo mucho más eficiente.
La máxima 'divide y vencerás', no es trivial en programación...

He aquí el algoritmo expuesto en esos dos pasos...
Se propone al tiempo dos parámetros para ordenar solo un rango específico del array (pués no lo hace distintto ni más complejo), y que, en caso del rango completo sus valores serán 0 y el tamaño del array -1.

Código [Seleccionar] Expandir


Funcion Selectionsort(array de enteros Matriz(), entero Min, entero Max )
    entero k, t
   
    Hacer mientras (Min < Max)
        k = Min
        t = BuscarValorMayor(Matriz, k, Max)   // 'k' es pasado por referencia, con lo que a su vuelta es contiene el índice que ocupa el valor devuelto.
        Matriz(k) = Matriz(Min): Matriz(Min) = t
       
        Min += 1
    Siguiente
Fin funcion

Y aquí la funció que localiza el mayor en un array, que tampoco tiene más complejidad...
Baste decir que por eficiencia, devuelve tanto el valor como el índice de dicho valor.

Código [Seleccionar] Expandir


entero = Funcion BuscarValorMayor(array de enteros Matriz(), entero *Desde , entero Hasta)
    entero i, v
   
    v = Matriz(Desde)
    i = (Desde + 1)
    Hacer mientras (i <= Hasta)
        Si (Matriz(i) > v) Then      // si enésimo es mayor que el actual mayor...
            Desde = i: v = Matriz(i) // recordamos índice y valor.
        fin si
        i += 1
    Siguiente
   
    devolver v
Fin funcion

Por razones de eficiencia es habitual no separar el algoritmo en dos funciones sino hacer la búsqueda del mayor/menor en el rango restante, in situ, razón quizás por la que no se repare en su sencillez.




C ) Que ambos arrays deben estar ordenados antes de proceder a la refundición.
Así que sí, es razonablemente correcto asumir por defecto este caso.
Bien es cierto, que faltaba una aclaración al respecto al menos, aunque debiera ser deducible por el interesado.