Recorrer Aray y ordenarlo

[locoxchacho]

Hola a todos!

Necesito hacer un ejercicio para la facultad, y no logro resolver de la manera adecuada:

"Escribir un funcion en C que reciba dos arrays ordenados de enteros, y devuelva un nuevo array con la mezcla ordenada de los arrays dados."

Como se puede resolver esto?

Primero que nada, es posible sin saber el tamaño de los arrays? O deben ser fijos? Porque buscando, siempre para recorrer un array, se hace sabiendo su tamaño, y no logro hacerlo de otra forma que no sea asi (es decir, que segun la ocasion, el tamaño del array cambie).

Por otra parte, en Python, yo lo habia resuelto de esta forma: agrego las dos listas a una tercer lista, llamada resultado, y a esta lista le aplico la funcion Quicksort, que programe, que lo que hace es ordenar una lista a partir de un pivot, recursivamente.

Creen que haya una forma mas facil? Y en C?

Desde ya, muchas gracias, y espero que puedan ayudarme!

Pablo.

[tistklehoff]

Hola...

En C, hasta donde yo sé, necesitarás un parámetro que te indique cuál es el tamaño del array si éste es dinámico, cosa que obtienes de la misma manera que vas leyendo los datos que te pasan por pantalla, en un fichero o en lo que sea.


Además, ¿estás diciendo que te dan dos arrays que ya están ordenados? Entonces estás desperdiciando tiempo brutalmente pasando un quicksort.

Si ambos arrays están ordenados, sólo necesitas mezclarlos. Para mí que tu profesor está intentando enseñaros a manear el algoritmo mergesort.

Lo que tienes que hacer es lo siguiente:


indice_array1 -> a la primera posicion del array1
indice_array2 -> a la primera posicion del array2

compara los números apuntados por los índices.

Si el número de indice_array1 <= indice_array2 => copia en el resultado el número de indice_array1 y apunta indice_array1 a la siguiente posición.

Si no, copia en el resultado el número de indice_array2 y apunta indice_array2 a la siguiente posición.

Cuando uno de los arrays se haya terminado, copialo que te queda del otro en el resultado desde su indice hasta el final.


Espero que te sirva.

Un saludo.

[locoxchacho]

Claro, es lo que pensaba.... lo que hice fue hacer un while de ambos len, que mientras por lo menos uno sea distinto de el verdadero len (lo inicializo en 0, y voy subiendo a medidad que agrego uno a la lista), se siga ejecutando el codigo.

Luego adentro, un if que comprueba cual de los dos valores es menor, y se agrega a la lista. Todo funciona correctamente hasta que llego al ultimo elemento de un array: siempre en el if, luego de agregarlo, se apunta como el minimo de esa lista al siguiente de esa misma lista. En el ultimo, efectivamente, eso no puede pasar, ya que no hay proximo!

Y ahi me lanza el error, y no encuentro solucion con que darle, y mira que he estado casi un dia entero, aplicando condiciones que se tengan que cumplir para apuntar al siguiente (si el len-1 es igual a la posicion de el actual, no se tendria que cambiar), pero no logro que funcione.

Por lo menos, desde el vamos, mi logica esta correcta? O hay algo que pense mal?

Y si no se entiende lo que digo, por favor, decime que trato de expresarme mejor!

Gracias,

Pablo.

[tistklehoff]

Hola...

Efectivamente, tu lógica no es correcta.

No es 'por lo menos uno distinto del verdadero len' sino, 'ambos distintos del verdadero len'

En este algoritmo hay 2 casos base:

lista 1 sin elementos -> copia la lista 2 en el resultado
lista 2 sin elementos -> copia la lista 1 en el resultado

caso de repetición:

ambas listas contienen elementos -> copia en el resultado el menor de los elementos y avanza en esa lista (o borralo de la lista, o como más te guste)


Espero que te sirva.


Un saludo.