• Jueves 28 de Marzo de 2024, 09:36

Autor Tema:  Lista Doble, Algoritmo De Ordenación - Optimizar  (Leído 2110 veces)

kike31416

  • Nuevo Miembro
  • *
  • Mensajes: 2
    • Ver Perfil
Lista Doble, Algoritmo De Ordenación - Optimizar
« en: Martes 14 de Septiembre de 2004, 23:04 »
0
¡Hola!  :D

Lista doble con cabecera circular.

Por favor, necesito ayuda con el algoritmo de ordenación de la lista, el algoritmo que diseñé funciona correctamente, pero busco reducir el número de iteraciones necesarias para ordenar la lista, o algún otro truco. Hasta el momento no he encontrado otro método para ordenar la lista.

Si alguien tiene una idea sobre como mejorar el desempeño del algoritmo, le estaría muy agradecido si me la comunica.

Incluyo el código de la biblioteca de la lista enlazada más un ejemplo.

Por su ayuda, Muchas gracias  :D :D

(Y si alguien encuentra algún error o posible mejora, le agradecería mucho me lo comentara   :P )

¡¡Hasta luego!!   :hola:
El mensaje contiene 1 archivo adjunto. Debes ingresar o registrarte para poder verlo y descargarlo.
[size=109]Be happy!![/size]

Ruben3d

  • Miembro HIPER activo
  • ****
  • Mensajes: 710
  • Nacionalidad: es
    • Ver Perfil
    • Web personal
Re: Lista Doble, Algoritmo De Ordenación - Optimizar
« Respuesta #1 en: Jueves 16 de Septiembre de 2004, 14:30 »
0
Ahora no tengo mucho tiempo para revisar tu código, así que sólo te pongo cómo lo haría yo.

La manera más rápida que se me ocurre de realizar una ordenación es en tiempo O(n · log n). Para ello usamos el algoritmo quicksort. Crea un array de punteros a los nodos [O(n)], y ordenalos en el array (sólo es cambiar punteros)[O(n · log n)]. A continuación, recorre el array y reenlaza los nodos en el orden en que te van apareciendo [O(n)]. De esta manera, habrías reordenado los nodos con bastante eficiencia, aunque necesitas un espacio adicional de 4 bytes por nodo durante la ordenación (en máquinas de 32 bits). La eficiencia final del algoritmo sería:

O(n) + O(n · log n) + O(n) -> O(n · log n)

No me paro a calcular las constantes.

Un saludo.

Ruben3d

kike31416

  • Nuevo Miembro
  • *
  • Mensajes: 2
    • Ver Perfil
Re: Lista Doble, Algoritmo De Ordenación - Optimizar
« Respuesta #2 en: Lunes 20 de Septiembre de 2004, 21:16 »
0
Agradezco mucho tu respuesta Ruben3d, pero he pasado varios días estudiando para poder comprenderla [O(n · log n)] :comp: , ahora ya comprendo tu simbología, y me da gusto, pues ahora puedo comparar los algoritmos con más que meras suposiciones. Lamentablemente, este “programa” no lo pienso utilizar sobre una plataforma de 32 bits con cientos de MB de RAM, sino sobre una de 8 bits con apenas 2k de RAM, sin embargo gracias a tu respuesta he podido hacer mejores preguntas y tengo ya un método, si bien no tan rápido, si lo suficiente, pues la cantidad de elementos en la lista no será (no puede ser) demasiado grande.

Muchas gracias.

P.D. notación asintótica :D

Gracias :hola:
[size=109]Be happy!![/size]