Foros de daboweb
MULTIMEDIA, Video digital, Grabación, Diseño gráfico, Diseño web, Programación => Webmasters - Diseño Web - Programación - Diseño gráfico => Mensaje iniciado por: netmar en 03 de Junio de 2004, 06:04:07 pm
-
:?
Tengo un vector de estructuras, y cada estructura está formada por 2 campos float: la
“coordenada x” ,y la “coordenada y” que representan un punto del espacio bidimensional.
Mi pregunta es si alguien sabe algun algoritmo para ordenar este vector como fila1,fila2,fila3,...filaN , considerando la esquina superior izquierda del plano como origen.
Por ejemplo el vector=[{coordenada_x=4,coordenada_y=6}, {coordenada_x=0,coordenada_y=1}, {coordenada_x=1,coordenada_y=7}, {coordenada_x=3,coordenada_y=3}]
deberia convertirse en [{coordenada_x=0,coordenada_y=1}, {coordenada_x=3,coordenada_y=3}, {coordenada_x=1,coordenada_y=7}, {coordenada_x=4,coordenada_y=6}]
Gracias por adelantado.
-
Para ordenar vectores, puedes utilizar qsort(), que utiliza el algoritmo quicksort.
Prueba esto:
#include <stdio.h>
#include <stdlib.h>
struct punto {
float x;
float y;
};
void imprime_puntos(struct punto*, int);
int fn_ordena(const void*, const void*);
/*------------------------------------------------*/
int main()
{
struct punto puntitos[] = { {4,6}, {0,1}, {1,7}, {3,3} };
int n_elem;
n_elem = sizeof(puntitos)/sizeof(puntitos[0]);
printf("\nAntes:\n");
imprime_puntos(puntitos, n_elem);
qsort(puntitos, n_elem, sizeof(struct punto), fn_ordena);
printf("\nDespu‚s:\n");
imprime_puntos(puntitos, n_elem);
return 0;
}
/*------------------------------------------------*/
void imprime_puntos(struct punto *p, int n_elem)
{
int i;
for (i = 0; i < n_elem; i++)
printf("x: %5.2f\ty: %5.2f\n", p[i].x, p[i].y);
}
/*------------------------------------------------*/
/*
Esta es la función que ordena el vector.
Debe devolver:
< 0 si 'uno' es menor que 'dos'
== 0 si 'uno' es igual a 'dos'
> 0 si 'uno' es mayor que 'dos'
*/
int fn_ordena(const void *uno, const void *dos)
{
struct punto *p1, *p2;
p1 = (struct punto *)uno;
p2 = (struct punto *)dos;
return (p1->x - p2->x);
}
La función que ordena, devuelve un entero indicando la relación de menor, igual o mayor de los dos elementos que se están comparando.
Como estamos comparando valores float, podríamos tener problemas, ya que el valor de retorno se moldea a int.
Si tenemos el siguiente vector:
struct punto puntitos[] = { {4, 6}, {0.5, 1}, {0.1, 7}, {3, 3} };
verás que no se ordena correctamente, esto es porque 0.5 - 0.1 = 0.4, que al pasarlo a int es 0. Se puede solucionar multiplicando por una potencia de 10 antes de restar. Por ejemplo, si queremos establecer una precisión de centésimas, multiplicamos por 100. Así: 0.5 * 100 - 0.1 * 100 = 50.0 - 10.0 = 40.0 que al pasarlo a int es 40. La comparación quedaría así:
return (100 * p1->x - 100 * p2->x);
un saludo.
-
bienvenido al foro amigo
alp :lol: que bone 8)
-
...el qsort es el mas rapido que conozco, es muy bueno entre mas desordenados esten los datos...es uyna buena eleccion, pero en que nivel vas???...es que por la pregunta, veo que aun no sabes de los metodos de ordenamiento...bueno sino funciona ya nos dices...mejor dicho si crees que no lo entiendes...por que ALP es un experto...
-
En algoritmia tienes varios metodos de ordenacion, incluido quicksort, que como ya te han dicho, es de lo más eficaz que hay. No obstante, te dejo el link.
http://www.algoritmia.net/articles.php?id=31
Está muy interesante, es lo que estoy haciendo yo ahora mismo en clase.
-
...por que ALP es un experto...
no soy ningún experto... simplemente llevo bastantes años programando en C, y me he pasado muchas horas "peleando" con estas cosas.... si yo hubiera tenido internet antes....
-
...no amigo nada de eso...sabes bastante y eso hay que respetarlo...por otro lado... :evil: si yo tuviewra internet ahora... :evil: ... :wink: ...
-
http://inforsist.net/apuntes.php
Ahí tienes unos apuntes de métodos de ordenación, explicados con ejemplos. Espero que te sirvan.
Saludos!
-
...saludos y bienvenido fg...gracias por los apuntes...