MULTIMEDIA, Video digital, Grabación, Diseño gráfico, Diseño web, Programación > Webmasters - Diseño Web - Programación - Diseño gráfico

algoritmo para ordenar un vector?

(1/2) > >>

netmar:
:?
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.

ALP:
Para ordenar vectores, puedes utilizar qsort(), que utiliza el algoritmo quicksort.

Prueba esto:

--- Código: ---#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);
}

--- Fin del código ---


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:

--- Código: ---struct punto puntitos[] = { {4, 6},  {0.5, 1},  {0.1, 7}, {3, 3} };
--- Fin del código ---

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í:

--- Código: --- return (100 * p1->x - 100 * p2->x);
--- Fin del código ---


un saludo.

Dabo:
bienvenido al foro amigo


alp  :lol:  que bone  8)

jirho:
...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...

BuHo:
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.

Navegación

[0] Índice de Mensajes

[#] Página Siguiente