[ Foro de Pascal ]

ordenar un vector mediante un vector de indices

26-Mar-2011 21:35
oscar gomez
4 Respuestas

Coridal saludo Antonio y Nacho cabanes,les pido siu colaboracion en si me pueden dar una idea de como trabajar el siguiente programa:

Ordenar un vector mediante un vector de ?ndices. Se tiene un vector de enteros cualesquiera.
Obtener otro de forma que el contenido de cada elemento del nuevo vector sea un ?ndice que nos indique de menor a mayor los valores de la tabla de enteros.
Por ejemplo:

10 6 -7 0 12  vector valores


3 4 2 1 5   vector indices

NOTA: La tabla original no se podra modificar, ni se puede hacer una copia de la misma.

como veis en el ejemplo el vector indices muestra en primer lugar el 3 que corresponde al menor valor del vector valores y que corresponde al -7 y asi sucesivamente.

me ayudara mucho su orientacion en el mismo es que no entiendo muy bien a lo que se refieren en la nota.

mil gracias


27-Mar-2011 13:58
Antonio P.G.

Hola Óscar.

A ver, acabo de pensar en un algoritmo que, eficaz, es, pero quizá no sea el más eficiente. Me baso en estos supuestos:

1- Contamos con un vector de N "integer" de entrada, que denominaré "vector_input".
2- Podemos leer dicho vector.
3- La salida la iremos almacenando en un vector (si no, se va imprimiendo y ya está). Lo denominaré "vector_output".
4- Voy a utilizar 2 variables auxiliares:
---> ult_ind: (último índice) Indicará el último índice que he declarado en la vuelta anterior. En tu ejemplar de funcionamiento, tras terminar la tercera vuelta de mi algoritmo que ahora contaré, esta variable sería igual a 2.
---> ult_valor: (último valor) Análogamente con respecto de lo anterior, indicará el último valor. Tras la tercera vuelta de tu ejemplar, esta variable valdría 6.
5- También se utilizará una variable contador que llamaré "cont", para los bucles, y otra variable "cont_output", que almacenará la última posición de vector_output.

Paso a explicar el algoritmo:

1- Lees vector_input.
2- Arrancas ult_ind en 0.
3- Empiezas primera vuelta.
4- Tras esta vuelta, tienes que haber almacenado en vector_output[1] el índice del valor más bajo del vector y tener en la variable ult_valor ese valor más bajo.
5- Ahora, en las siguientes vueltas, buscas y almacenas el siguiente ínfimo valor en cada vuelta, y vas almacenándolo en vector_output. ¿Cómo lo haces? Pues bueno, ya sabes los valores que has metido porque vas almacenando los índices...

Espero que lo hayas entendido. Si tienes alguna duda, ya sabes.

Te recomiendo que utilices la técnica de programación descendente, que no sé si ya conoces. Ésta NO consiste en escribir de arriba abajo, sino que se trata de hacer como módulos y de luego ir completándolos. (Explicación burda).

¡Ciao!


27-Mar-2011 14:10
Antonio P.G.

Por cierto, crea el programa de forma que funcione para vectores cuyos valores son todos distintos. Luego, cuando ese funcione, hazlo para vectores que contengan valores repetidos.

¡Ciao!


27-Mar-2011 15:05
oscar gomez

Cordial saludo Antonio y de ante mano mil gracias por tu tiempo y ayuda.

Antonio no se por que me planteas el ejercicio luego con valores repetidos, pues la verdad en ese caso cual de los indices escogeria en caso de los repetidos para basarme en que es menor??? y asi ordenar el vector de indices???
por tu orientacion mil gracias de nuevo


27-Mar-2011 23:37
Nacho Cabanes (+31)

Por detallar un poco más la propuesta de Antonio...

Sin pensar mucho, se me ocurre que podría hacer algo así:

Si entiendes el algoritmo de ordenación por burbuja (en cada pasada, tomas el menor de los elementos restantes y lo llevas a la primera posición), se puede plantear de una forma muy similar, pero en vez de alterar el vector de datos, vuelcas en un segundo vector. La única diferencia "de verdad" es que en el algoritmo de burbuja los datos anteriores se van quedando ordenados, y aquí no, así que te interesa "memorizar" el último valor que has usado.

Podría ser algo como:

menorAnterior = -30000
Para i = 1 hasta maximo
 posicMenor = i
 Para j = i hasta maximo
    Si valores[j] < valores [posicMenor] y valores[j] > menorAnterior
      posicMenor = j
      menorAnterior = valores[j]
 indice[i] = menor
 Fin para
Fin para

Es decir:
- En cada pasada, presupones que el menor es el primero de los que quedan.
- Lo comparas con todos los demás, y para descubrir cual es el menor "de verdad" (pero que a su vez sea mayor que el último menor encontrado).
- Almacenas ese "menor" en la posición actual del vector de índices.
- Pasas a la siguiente posición

(Esta aproximación sólo sirve si todos los números distintos).






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)