[SOLUCIONADO] Algoritmo para ordenar matriz sin usar método .SORT, pero con problema.

Profesor_Lambetain · #1 (**permalink**) 04/10/2013, 17:34

Hola foreros,
Tengo un problemilla con esta sencilla rutina, y desde hace dos días que no puedo encontrar el fallo.

Se trata de una serie de vectores (p1 a p3) que conforman una matriz (perhermanos). Los elementos [2] de los vectores (elementos [i][2] de matriz perhermanos) son fechas en formato DDMMAAAA. Necesito ordenar dichos vectores dentro de perhermanos por fecha creciente (esto es: de más antigua a más reciente). Por razones que no vienen al caso, no puedo usar el método .sort del objeto Array. Para ello he escrito el siguiente código:

1. Trabajo con fechas redefinidas al formato AAAAMMDDXX, donde XX son los últimos dos dígitos de los elementos [0] de los vectores p.
1. Un for interior (índice i) detecta qué fecha es la más antigua dentro de matriz perhermanos.
2. A ese vector lo transfiero al final de la matriz perhermanosbis mediante el método .push.
3. Para no volver a detectar ese mismo vector de perhermanos en ciclo for externo posterior (índice j), le cambio el valor al elemento [2] del vector transferido a perhermanosbis (mediante la instrucción perhermanos[mayor][2]="xxxxxxxx";).
4. Supuestamente, con este código, al finalizar ambos bucles for, tendría que obtener la matriz perhermanosbis ordenada por fechas, y la matriz original perhermanos con todos sus elementos [i][2] iguales a "xxxxxxxx".

Pues no: obtengo los elementos [2] de los vectores de perhermanosbis iguales a "xxxxxxxx" también. Sé que el cambio de la fecha "DDMMAAAA" a "xxxxxxxx" en perhermanosbis ocurre ejecutando la instrucción perhermanos[mayor][2]="xxxxxxxx"; , pero esta instrucción no debería cambias perhermanosbis sino sólo perhermanos (como lo hace).

Sinceramente no sé dónde está el fallo, sé que será una tontería, pero no lo puedo hallar. A ver si algún forero puede verlo. Gracias anticipadas.

Código HTML:

<?xml version="1.0" encoding="UTF-8"?
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
	http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd>

<html xmlns=http://w3.org/1999/xhtml xml:lang="en">
<head>
<script type="text/javascript">
function arbol(){
	var p1=new Array("10001","2","10121952","3");
	var p2=new Array("10002","5","15121955","6");
	var p3=new Array("10003","8","23081947","9");
	var perhermanos=new Array(p1,p2,p3);
	var s=3;
	var perhermanosbis=new Array();

	var mayor=0;
	for(j=1;j<=s;j++){
		fechamasantigua="9999999999";
		for(i=0;i<=perhermanos.length-1;i++){
			fechaactual=perhermanos[i][2].substr(4,4)+perhermanos[i][2].substr(2,2)+perhermanos[i][2].substr(0,2)+perhermanos[i][0].substr(3,2);
			if(fechaactual<fechamasantigua && fechaactual.substr(0,8)!="xxxxxxxx"){
				fechamasantigua=fechaactual;
				mayor=i;
			}else{
				continue;
			}
		} // Fin for.
		perhermanosbis.push(perhermanos[mayor]);
// alert(mayor);
alert(perhermanosbis);
		perhermanos[mayor][2]="xxxxxxxx";
alert(perhermanosbis);
	} // Fin for.
} // Fin function arbol.
</script>
</head>

<body style="background-color:#FFFFFF" onLoad="javascript:arbol();">
Esto es una prueba...
</body>
</html>

Profesor_Lambetain · #2 (**permalink**) 05/10/2013, 05:50

Sigo sin poder encontrar el fallo.

En otras palabras, y sobre el código que puse arriba: ¿cómo es posible que la instrucción perhermanos[mayor][2]="xxxxxxxx" , que cambia el elemento indicado de la matriz perhermanos, cambie también la matriz perhermanosbis? (cosa que se puede comprobar con los alert inmediatamente antes e inmediatamente después de la instrucción).

¿Algún alma caritativa que pueda echarme una mano? Muchas gracias.

zerokilled · #3 (**permalink**) 05/10/2013, 17:55

buenas,
me arde la curiosidad

¿por qué no puedes usar el método sort? no le veo otra explicación a que posiblemente se trate de un ejercicio.

Profesor_Lambetain · #4 (**permalink**) 06/10/2013, 02:14

Cita:

Iniciado por zerokilled

buenas,
me arde la curiosidad

¿por qué no puedes usar el método sort? no le veo otra explicación a que posiblemente se trate de un ejercicio.

1. Porque me gusta la programación y me fijo como objetivo, dentro de una lógica, programar yo mismo las funciones que necesite, sin utilizar funciones predefinidas.

2. Porque a mis funciones les conozco muy bien sus límites (allá donde se dan condiciones de contorno específicas) que de las programadas por otros. Esto es: me fío más de mis funciones.

3. Porque, al ser un aficionado y no un profesional, no conozco los límites de los diferentes navegadores que pudieran no reconocer ciertas funciones predefinidas en JS.

... y para ser sincero: 4. Me da pereza ponerme a estudiar la funcionalidad de la instrucción sort para aplicarla a este caso, me es más fácil programarlas yo mismo... aunque en este caso particular no sé si debiera continuar con mi política

Aún no he podido encontrar la respuesta a mi pregunta... ¿ves algo que me pueda ayudar? Gracias.

zerokilled · #5 (**permalink**) 06/10/2013, 08:21

esta muy bien que te fijes como objetivo desarrollar tus propias funciones, aunque implique reinventar la rueda. de esta manera puedes desarrollar la logística para enfrentar nuevos retos u obstáculos. no obstante, en mi opinión, es preferible usar las funciones nativas del lenguaje siempre que sea posible. al ser nativo, éstas suelen tener un mejor rendimiento comparado con las definidas por el desarrollador. en el único caso que conviene crear su propia versión es cuando hay inconsistencia entre entornos (entiendase navegadores). en mi experiencia, las funciones del core de javascript, no me han presentado ninguna diferencia.

volviendo a tu código... el problema es que estas editando sobre una referencia. cuando invocas perhermanosbis.push(perhermanos[mayor]);, estas pasando una referencia del array mas no una copia. de modo que cualquier cambio que realices en perhermanos[N], perhermanosbis[N], o pN, ‒siendo N un número‒ se verá reflejado en todos ellos porque son una referencia al mismo array. en javascript, todos los objetos se pasan como referencia y los datos primitivos (string, boolean, number) como una copia.

¿qué puedes hacer? en lugar de editar la fecha del array movido a perhermanosbis, elimina el elemento del array original. así, además de evitar la edición, te ahorras tiempo de ejecucción y mejoras el rendimiento. con esto me refiero a que en cada ciclo del bucle, estás comparando un elemento que ya no tienes que comparar. cuando lo eliminas, tienes menos elementos a comparar. para implementar esta solución, tienes que corregir un par de cosas: modificar la condición if, modificar la condición del for externo para que itere hasta quedar el array vacio, cambiar la línea que escribe 'x's por la invocación de splice.

en lo personalmente, prefiero el método sort. sort me permite indicar la condición y ésta se encarga de ordenar el array. es mucho más cómodo y simple.

Código:

var array = [
["10001","2","10121952","3"],
["10002","5","15121955","6"],
["10003","8","23081947","9"]
];

array.sort(function(a, b){
// formatear string para Date.parse ;
a = a[2].match(/(\d{2})(\d{2})(\d{4})/).reverse();
b = b[2].match(/(\d{2})(\d{2})(\d{4})/).reverse();
a.pop(), b.pop();
return Date.parse(a.join('/')) - Date.parse(b.join('/'));
});

console.log(array.toString());

Profesor_Lambetain · #6 (**permalink**) 06/10/2013, 15:58

Cita:

Iniciado por zerokilled

esta muy bien que te fijes como objetivo desarrollar tus propias funciones, aunque implique reinventar la rueda. de esta manera puedes desarrollar la logística para enfrentar nuevos retos u obstáculos. no obstante, en mi opinión, es preferible usar las funciones nativas del lenguaje siempre que sea posible. al ser nativo, éstas suelen tener un mejor rendimiento comparado con las definidas por el desarrollador. en el único caso que conviene crear su propia versión es cuando hay inconsistencia entre entornos (entiendase navegadores). en mi experiencia, las funciones del core de javascript, no me han presentado ninguna diferencia.

volviendo a tu código... el problema es que estas editando sobre una referencia. cuando invocas perhermanosbis.push(perhermanos[mayor]);, estas pasando una referencia del array mas no una copia. de modo que cualquier cambio que realices en perhermanos[N], perhermanosbis[N], o pN, ‒siendo N un número‒ se verá reflejado en todos ellos porque son una referencia al mismo array. en javascript, todos los objetos se pasan como referencia y los datos primitivos (string, boolean, number) como una copia.

¿qué puedes hacer? en lugar de editar la fecha del array movido a perhermanosbis, elimina el elemento del array original. así, además de evitar la edición, te ahorras tiempo de ejecucción y mejoras el rendimiento. con esto me refiero a que en cada ciclo del bucle, estás comparando un elemento que ya no tienes que comparar. cuando lo eliminas, tienes menos elementos a comparar. para implementar esta solución, tienes que corregir un par de cosas: modificar la condición if, modificar la condición del for externo para que itere hasta quedar el array vacio, cambiar la línea que escribe 'x's por la invocación de splice.

en lo personalmente, prefiero el método sort. sort me permite indicar la condición y ésta se encarga de ordenar el array. es mucho más cómodo y simple.

Código:

var array = [
["10001","2","10121952","3"],
["10002","5","15121955","6"],
["10003","8","23081947","9"]
];

array.sort(function(a, b){
// formatear string para Date.parse ;
a = a[2].match(/(\d{2})(\d{2})(\d{4})/).reverse();
b = b[2].match(/(\d{2})(\d{2})(\d{4})/).reverse();
a.pop(), b.pop();
return Date.parse(a.join('/')) - Date.parse(b.join('/'));
});

console.log(array.toString());

Muchas gracias zerokilled, tu post es esclarecedor. Me pondré a estudiarlo en detalle, tanto la solución tuya en respuesta al método casero, como la función sort (tienes razón: ¿por qué no utilizar la rueda que inventaron otros? Y es que me has dado tranquilidad: "esta rueda" es de las buenas).

Cuando resuelva el código de arriba con las sugerencias de zerokilled postearé el definitivo para quien pueda interesar. La solución con sort supongo que ya la gente la conoce.

Mil gracias nuevamente zero.

Profesor_Lambetain · #7 (**permalink**) 06/10/2013, 17:13

El código casero (sin usar método sort) queda así:

Código HTML:

<?xml version="1.0" encoding="UTF-8"?
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
	http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd>

<html xmlns=http://w3.org/1999/xhtml xml:lang="en">
<head>
<script type="text/javascript">
function arbol(){
	var p1=new Array("10001","2","10121952","3");
	var p2=new Array("10002","5","15121955","6");
	var p3=new Array("10003","8","23081947","9");
	var perhermanos=new Array(p1,p2,p3);
	var s=3;
	var perhermanosbis=new Array();
	var fechamasantigua;
	var fechaactual;
	var chapuza;
	var mayor=0;
	for(j=0;j<=s-1;j++){
		fechamasantigua="9999999999";
		for(i=0;i<=perhermanos.length-1-j;i++){ /* observar el juego de índices, ya que matriz perhermanos es de longitud 
							variable (se reduce en un vector a cada ciclo de for(j)). */
			fechaactual=perhermanos[i][2].substr(4,4)+perhermanos[i][2].substr(2,2)+perhermanos[i][2].substr(0,2)+perhermanos[i][0].substr(3,2);
			if(fechaactual<fechamasantigua){
				fechamasantigua=fechaactual;
				mayor=i;
			}else{
				continue;
			}
		} // Fin for(i).
		chapuza=perhermanos[mayor]; // se carga variable temporal chapuza con el vector de fecha más antigua de perhermanos.
		perhermanosbis[j]=chapuza; // se agrega a perhermanosbis el vector anterior.
		perhermanos.splice(mayor,1); // se elimina el vector de fecha más antigua de perhermanos.
alert("Matriz perhermanos: \n"+perhermanos+"\n\nMatriz perhermanosbis: \n"+perhermanosbis);
	} // Fin for(j).
} // Fin function arbol.
</script>
</head>

<body style="background-color:#FFFFFF" onLoad="javascript:arbol();">
Esto es una prueba...
</body>
</html>

Se puede comprobar con el alert, a cada ciclo de for externo, cómo va reduciéndose la longitud de la matriz original (perhermanos) y cómo va creciendo la matriz ordenada (perhermanosbis).

Obviamente, y como bien dijo zerokilled arriba, el uso de sort es más racional... y elegante. Al respecto, un pensamiento:

[Off topic]Reinventar la rueda no tiene nada de malo, más bien veo cosas buenas en ello. Cuando le preguntas a un niño actual de dónde viene la leche, muchos responden "del Carrefour"... la Humanidad está olvidando cómo se usa el cerebro, esa maravilla, producto de eones de evolución, que surgió después de muchos intentos de prueba y error (esto es: a base de mutación y muerte) sin que ninguna inteligencia se lo haya propuesto. La mayoría de humanos perecería si se los abandonara en la selva, en el desierto o en el monte... porque ya ni saben hacer fuego ni cazar ni pescar. Y nos hemos sumido en una época en la que el uso del cerebro será primordial para poder sobrevivir a esta sinrazón a que nos han llevado gobiernos, élites y regímenes capitalistas y de los otros. Yo alterno mis ejercicios de lógica (programar) con el cultivo de mi huerta: el placer que causa un programa bien hecho es equivalente a la obtención de una minúscula cosecha de tomates. La lucha no debe ser contra los otros sino contra uno mismo: ¿por qué no voy a considerar un logro mío el haber corrido los 100 metros en 18 segundos, si yo nunca di esa marca? ¿Qué sentido tiene compararme con un negro o con un jamaicano... por qué no con una chita o una hormiga? El secreto es superarse uno a sí mismo, no superar a los demás.[/off]

zerokilled · #8 (**permalink**) 07/10/2013, 06:09

solo por simple coincidencia, el resultado aparenta estar bien... pero el código está mal. si agregas más elementos al array perhermanos o incluso si cambias el orden, por ejemplo Array(p2,p1,p3), vas a notar que el resultado no es el mismo. el error está en el bucle interno; estás cambiando la condición del bucle mediante una resta que no tiene sentido. especificamente, la resta con la variable j.

en fin, esta es mi adaptación al código utilizando como base el código inicial.

Código:

function arbol(){
var p1=new Array("10001","2","10121952","3");
var p2=new Array("10002","5","15121955","6");
var p3=new Array("10003","8","23081947","9");
var perhermanos=new Array(p2,p1,p3);
var perhermanosbis=new Array();
    var mayor=0;
	while (perhermanos.length){
	if (perhermanos.length == 1){ perhermanosbis.push(perhermanos.pop()); break; }
	var fechamasantigua="9999999999";
		for(var i=0, len=perhermanos.length; i<len; i++){
		// YYYYMMDDXX
		var fechaactual = perhermanos[i][2].substr(4,4) + perhermanos[i][2].substr(2,2) + perhermanos[i][2].substr(0,2) + perhermanos[i][0].substr(3,2);
			if (Number(fechaactual) < Number(fechamasantigua)){
			fechamasantigua=fechaactual;
			mayor=i;
			} else { continue; }
		} // Fin for.
	perhermanosbis.push(perhermanos.splice(mayor,1));
	} // Fin for.
console.log(perhermanosbis.toString());
} // Fin function arbol.

Profesor_Lambetain · #9 (**permalink**) 07/10/2013, 15:56

Cita:

Iniciado por zerokilled

solo por simple coincidencia, el resultado aparenta estar bien... pero el código está mal. si agregas más elementos al array perhermanos o incluso si cambias el orden, por ejemplo Array(p2,p1,p3), vas a notar que el resultado no es el mismo. el error está en el bucle interno; estás cambiando la condición del bucle mediante una resta que no tiene sentido. especificamente, la resta con la variable j.

en fin, esta es mi adaptación al código utilizando como base el código inicial.

Código:

function arbol(){
var p1=new Array("10001","2","10121952","3");
var p2=new Array("10002","5","15121955","6");
var p3=new Array("10003","8","23081947","9");
var perhermanos=new Array(p2,p1,p3);
var perhermanosbis=new Array();
    var mayor=0;
	while (perhermanos.length){
	if (perhermanos.length == 1){ perhermanosbis.push(perhermanos.pop()); break; }
	var fechamasantigua="9999999999";
		for(var i=0, len=perhermanos.length; i<len; i++){
		// YYYYMMDDXX
		var fechaactual = perhermanos[i][2].substr(4,4) + perhermanos[i][2].substr(2,2) + perhermanos[i][2].substr(0,2) + perhermanos[i][0].substr(3,2);
			if (Number(fechaactual) < Number(fechamasantigua)){
			fechamasantigua=fechaactual;
			mayor=i;
			} else { continue; }
		} // Fin for.
	perhermanosbis.push(perhermanos.splice(mayor,1));
	} // Fin for.
console.log(perhermanosbis.toString());
} // Fin function arbol.

Gracias por tu dedicación zerokilled. Ya me había dado cuenta de que mi código estaba errado. Y, para el caso que analizamos, ya lo había corregido (de todos modos estudiaré el tuyo que me parece más elegante y conciso, y del que creo que aprenderé aspectos que desconozco).

Pero la cosa no termina allí, porque el problema concreto que debo resolver es más complejo (el código que informé al principio es una adaptación simple para no liar al personal): de momento tengo más de 60 vectores pXX, y algunos de ellos pueden no traer el formato DDMMAAAA en su campo [2]. Con el código corregido fui a incorporar estos vectores con fecha fuera de formato a la matriz perhermanosbis... ¡y tuve problemas nuevamente! Así que me pongo a trabajar en ello y reportaré el resultado cuando esté seguro de que funciona (tu último código, por lo que pude probar, funciona de cine).

Ah, y además me pondré a estudiar sort (y lo que ello conlleva, creo que expresiones regulares), porque esto de reinventar la rueda a veces cansa un poco

Gracias nuevamente.

zerokilled · #10 (**permalink**) 07/10/2013, 19:22

Cita:

Ah, y además me pondré a estudiar sort (y lo que ello conlleva, creo que expresiones regulares)...

no, para usar sort no conlleva expresiones regulares. simplemente ahí lo utilicé porque me parecio más cómodo. en su lugar, pude haber utilizado substr tal como lo tienes en el código inicial. lo único que realmente requieres saber de sort es que le pasas una función como argumento. dicha función recibirá dos argumentos que serán dados por sort. si un elemento debe ir antes que otro, entonces la función tiene que devolver un número negativo. de forma similar, si un elemento debe ir después que otro, la función tiene que devolver un número positivo. si ambos elementos poseen el mismo valor, es decir no va antes ni después, la función debe devolver cero.

Profesor_Lambetain · #11 (**permalink**) 04/11/2013, 05:00

Finalmente, he estudiado el uso de sort y tengo que decirlo: su uso es sencillo y racional. No es necesario inventar ruedas

Aunque creo que, si hago los debidos esfuerzos, podría codificar un algoritmo para ordenar vectores sin el uso de sort, abandono mi intento en este caso particular; por ello doy el tema por solucionado (para que, de algún modo, el tema quede formalmente cerrado).

Gracias por tu apoyo zerokilled.