Autor Tema: Estabilidad de un algoritmo

0 Usuarios y 1 Visitante están viendo este tema.

28 Mayo, 2014, 03:24 pm
Leído 1151 veces

alemunozgar

  • AlexD
  • Novato
  • Mensajes: 183
  • Karma: +0/-0
  • Sexo: Masculino
  • La esencia de la matemática reside en su libertad.
Saludos.
Me encuentro con el siguiente ejercicio para estabilizar un algoritmo:

Modi que la funcion partition de tal manera que el algoritmo de ordenamiento resultante sea estable. Solo puede utilizar, si es necesario, una cantidad constante de espacio adicional (en particular no puede usar otra lista auxiliar).

Entiendo que el algoritmo no es estable pues si al comienzo se tienen \( i<j \) y \( A[i]=A[j] \) entonces es posible que al final estos mismos objetos estén en posiciones \( k,l \) respectivamente con \( k>l \).

No sé cómo evitar que suceda esto, múltiples intentos me llevan a lo mismo.
Agradezco si alguien me puede dar un lienamiento o echar una mano.
Adjunto la imagen con el respectivo algoritmo, dado que se me dificulta realizar indentaciones en este editor.



Saludos.



Antes de imprimir este mensaje, reflexiona si es necesario hacerlo. 17 árboles mueren por 1TON papel