Aventuras de DoHITB: DoHITB vs. JavaScript (IV)

Buenas!

Llegamos casi al clímax de esta aventura de programación... toca ver temas de ordenación. ¿Listos?

Algoritmo de ordenación

Como decía al principio de la aventura, una parte del trabajo era tratar el XML, y la otra era ordenar las listas de objetos, para su posterior tratado.

Así, diseñé este pequeño algoritmo de ordenación de propósito básico:

//en arr tenemos un array de los datos
itera arr desde 0 hasta la longitud de arr (contador = i)
    suponemos que el máximo (m) es el elemento actual, y guardamos su posición

    itera arr desde el siguiente elemento de i hasta la longitud de arr (contador = j)
        si el elemento de j es mayor o igual que el elemento de m
            la posición máxima (m) pasa a ser la actual posición de j
        is
    areti

    intercambia las posiciones de "i" y "m"
areti

Es decir, es un ordenado secuencial, en el que se recorre dos veces el array (aunque la segunda vez es cada vez menor), y se va colocando el mayor ítem en el lugar más cercano (y puesto que a la siguiente "vuelta" estará "fuera de rango", podemos seguir).

En JavaScript (el tema que nos concierne) es algo "tan sencillo" como esto:

function basicSort(arr){
  for(i=0;i<arr.length;i++){
    m=i;
 
    for(j=i+1;j<arr.length;j++){
      if(arr[j]>=arr[m]){
        m=j;
      }
    }
 
    a=arr[m];
    arr[m]=arr[i];
    arr[i]=a;
  }
}

Si se va a llamar de manera recursiva, tenemos que tener en cuenta la pila, ¿recordáis? jejeje

Incorporar en una clase

El siguiente paso lógico es incorporar esta funcionalidad en una clase. Para ello haremos lo siguiente:

var Sortable = function(){
this.toSort = false;

this.setToSort = function(toSort){
this.toSort = toSort;
};

function sort(){
if(!this.toSort){
return false;
}


 for(i=0;i<this.toSort.length;i++){
m = i;

for(j=i+1;j<this.toSort.length;j++){
 if(this.toSort[j] >= this.toSort[m]){
m = j;
 }
}

a = this.toSort[m];
this.toSort[m] = this.toSort[i];
this.toSort[i] = a;
 }
};
};

Si os fijáis, usamos el hecho de que los datos en JavaScript son variables para comprobar si el atributo "toSort" está informado.

Para ordenar un array no tendríamos más que crear un objeto "Sortable", ajustar el valor de "toSort" y llamar a "sort()". Después de eso, en "toSort" tendríamos el array ordenado, conservando el original fuera de la clase.

Ampliación de la ordenación

Lo siguiente que se me ocurrió fue: ¿y si en vez de ascendente se necesita una ordenación descendiente?

En este punto se plantean dos opciones, cada una con ventajas e inconvenientes:

• Uso de "eval()"
• Ventajas
• Máxima versatilidad
• No es necesario comprobar a posteriori
• Inconvenientes
• Existe una (falsa) máxima en JavaScript que dice "Eval is Evil". No está muy bien visto el uso de "eval()"
• Sintaxis más compleja
• Hacer ordenación ascendente, luego comprobar, y si es descendiente dar la vuelta
• Ventajas
• Si es ascendente tardamos la mitad
• Método "más correcto"
• Inconvenientes
• Menor versatilidad
• Si es descendente tardamos el doble

Me decanté por "eval()", ya que a la vez se me ocurrió que se podría comparar no solo números, sino incluso objetos (para lo que hace falta algo más que un "<=" o un ">=")

ASC/DESC

Así, vamos a ver cómo ampliaríamos la clase para que permita ordenación ascendente y descendente:

var Sortable = function(){
this.toSort = false;
this.isInverse = false;

this.setToSort = function(toSort){
this.toSort = toSort;
};

this.setIsInverse = function(isInverse){
this.isInverse = isInverse;
};

function sort(){
//clave de comparación de "j"
tokenJ = 'this.toSort[j]';
//clave de comparación de "m"
tokenM = 'this.toSort[m]';

if(!this.toSort){
return false;
}

if(this.isInverse){
r = ' <= ';
}else{
r = ' >= ';
}

 for(i=0;i<this.toSort.length;i++){
m = i;

for(j=i+1;j<this.toSort.length;j++){
 //evaluará: this.toSort[j] <= / >= this.toSort[m]
 if(eval(tokenJ + r + tokenM)){
m = j;
 }
}

a = this.toSort[m];
this.toSort[m] = this.toSort[i];
this.toSort[i] = a;
 }
};
};

Ahora, si queremos cambiar a descendiente, tendríamos que ajustar "isInverse" a verdadero (true), y listo.

Ítem/Objeto

Finalmente, es muy probable que queramos comparar no solo números, sino objetos. Para ello, ampliando la estructura de "eval()" y "sort()", deberíamos habilitar un método en la clase a comparar que retornase algún valor fácilmente comparable (el número de matrícula, por ejemplo; o un ID autonumérico).

var Sortable = function(){
this.toSort = false;
this.isInverse = false;
this.sortFunction = '';

this.setToSort = function(toSort){
this.toSort = toSort;
};

this.setIsInverse = function(isInverse){
this.isInverse = isInverse;
};

this.setSortFunction = function(sortFunction){
this.sortFunction = sortFunction;
};

function sort(){
tokenJ = 'this.toSort[j]';
tokenM = 'this.toSort[m]';

if(!this.toSort){
return false;
}

if(this.isInverse){
r = ' <= ';
}else{
r = ' >= ';
}

 for(i=0;i<this.toSort.length;i++){
m = i;

for(j=i+1;j<this.toSort.length;j++){
 //evaluará: this.toSort[j].*valor de sortfunction* <= / >= this.toSort[m].*valor de sortfunction*
 //nótsese que se ha de pasar el valor de la función con el "."
 if(eval(tokenJ + this.sortFunction + r + tokenM + this.sortFunction)){
m = j;
 }
}

a = this.toSort[m];
this.toSort[m] = this.toSort[i];
this.toSort[i] = a;
 }
};
};

Así, si ajustamos a "sortFunction" el valor ".myFunction()", comparará los valores devueltos en el array de dicha función.

Y hasta aquí, chicos, la parte de ordenación. La próxima y última será acerca de la eliminación de duplicados (cuyo algoritmo es mucho más sencillo si el array está ordenado ;-) )

Como siempre... ¡hasta la próxima!