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;
}
Pon el código entre etiquetas de Código GeSHi (en lenguaje C).
La solución en pseudocódigo sería algo así:
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
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.
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...
El enunciado no indica que los vectores que se ingresan estan ordenados, que parece ser asumido por las soluciones presentadas.
Cita de: CalgaryCorpus en 7 Noviembre 2019, 22:34 PM
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.
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.
Cita de: CalgaryCorpus en 7 Noviembre 2019, 22:34 PM
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).
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 siA 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.
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 funcionY 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.
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.